785.md (32262B)
1 Source: https://codeforces.com/blog/entry/50996 2 3 This is an editorial for the problems of the today's contest. I tried my best to describe the solutions for the problems as detailed as possible, but if something is not understandable for you, you can write in comments! :) 4 5 [785A - Anton and Polyhedrons](/contest/785/problem/A "Codeforces Round 404 (Div. 2)") 6 7 **Hint** 8 9 404 Not Found 10 11 **Tutorial** 12 13 Tutorial is loading... 14 15 **C++ code** 16 17 ``` 18 #include <iostream> 19 #include <map> 20 21 using namespace std; 22 23 int main() { 24 ios_base::sync_with_stdio(false); 25 map<string, int> vals; 26 vals["Tetrahedron"] = 4; 27 vals["Cube"] = 6; 28 vals["Octahedron"] = 8; 29 vals["Dodecahedron"] = 12; 30 vals["Icosahedron"] = 20; 31 int n; cin >> n; 32 int res = 0; 33 for (int i = 0; i < n; i++) { 34 string s; cin >> s; 35 res += vals[s]; 36 } 37 cout << res << endl; 38 return 0; 39 } 40 ``` 41 42 **Java code** 43 44 ``` 45 import java.io.*; 46 import java.util.*; 47 48 public class PolyhedronSums { 49 public static void main(String[] args) throws Exception { 50 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 51 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); 52 HashMap<String, Integer> vals = new HashMap<String, Integer>(); 53 vals.put("Tetrahedron", 4); 54 vals.put("Cube", 6); 55 vals.put("Octahedron", 8); 56 vals.put("Dodecahedron", 12); 57 vals.put("Icosahedron", 20); 58 int n = Integer.parseInt(reader.readLine()); 59 int res = 0; 60 for (int i = 0; i < n; i++) { 61 res += vals.get(reader.readLine()); 62 } 63 writer.write(Integer.toString(res)); 64 reader.close(); 65 writer.close(); 66 } 67 } 68 ``` 69 70 **Python code** 71 72 ``` 73 vals = { 74 'Tetrahedron': 4, 75 'Cube': 6, 76 'Octahedron': 8, 77 'Dodecahedron': 12, 78 'Icosahedron': 20 79 } 80 81 n = int(input()) 82 ans = 0 83 for i in range(0, n): 84 ans += vals[input()] 85 print(ans) 86 ``` 87 88 [785B - Anton and Classes](/contest/785/problem/B "Codeforces Round 404 (Div. 2)") 89 90 **Hint** 91 92 Think of what periods to take if Anton attends chess classes earlier than programming classes and vice versa. 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **C++ code** 99 100 ``` 101 #include <iostream> 102 #include <algorithm> 103 104 const int infinity = 1234567890; 105 106 using namespace std; 107 108 int main() { 109 ios_base::sync_with_stdio(false); 110 int n; cin >> n; 111 vector<pair<int, int> > a(n); 112 for (int i = 0; i < n; i++) { 113 cin >> a[i].first >> a[i].second; 114 } 115 int m; cin >> m; 116 vector<pair<int, int> > b(m); 117 for (int i = 0; i < m; i++) { 118 cin >> b[i].first >> b[i].second; 119 } 120 int minR1 = infinity, maxL1 = -infinity; 121 int minR2 = infinity, maxL2 = -infinity; 122 for (int i = 0; i < n; i++) { 123 maxL1 = max(maxL1, a[i].first); 124 minR1 = min(minR1, a[i].second); 125 } 126 for (int i = 0; i < m; i++) { 127 maxL2 = max(maxL2, b[i].first); 128 minR2 = min(minR2, b[i].second); 129 } 130 int res = max(maxL2 - minR1, maxL1 - minR2); 131 cout << max(res, 0) << endl; 132 return 0; 133 } 134 ``` 135 136 **Java code** 137 138 ``` 139 import java.io.*; 140 import java.util.*; 141 142 public class TwoSegments { 143 public static final int infinity = 1234567890; 144 145 public static class Segment { 146 public int l; 147 public int r; 148 149 public Segment(int aL, int aR) { 150 l = aL; 151 r = aR; 152 } 153 } 154 155 private static Segment[] readList(BufferedReader reader) throws Exception { 156 int n = Integer.parseInt(reader.readLine()); 157 Segment[] res = new Segment[n]; 158 for (int i = 0; i < n; i++) { 159 StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); 160 int l = Integer.parseInt(tokenizer.nextToken()); 161 int r = Integer.parseInt(tokenizer.nextToken()); 162 res[i] = new Segment(l, r); 163 } 164 return res; 165 } 166 167 public static void main(String[] args) throws Exception { 168 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 169 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); 170 Segment[] a = readList(reader); 171 Segment[] b = readList(reader); 172 int minR1 = infinity, maxL1 = -infinity; 173 int minR2 = infinity, maxL2 = -infinity; 174 for (int i = 0; i < a.length; i++) { 175 maxL1 = Math.max(maxL1, a[i].l); 176 minR1 = Math.min(minR1, a[i].r); 177 } 178 for (int i = 0; i < b.length; i++) { 179 maxL2 = Math.max(maxL2, b[i].l); 180 minR2 = Math.min(minR2, b[i].r); 181 } 182 int res = Math.max(maxL2 - minR1, maxL1 - minR2); 183 writer.write(Integer.toString(Math.max(res, 0))); 184 reader.close(); 185 writer.close(); 186 } 187 } 188 ``` 189 190 **Python code** 191 192 ``` 193 infinity = 1234567890 194 minR1 = minR2 = infinity 195 maxL1 = maxL2 = -infinity 196 n = int(input()) 197 for i in range(0, n): 198 (l, r) = map(int, input().split()) 199 maxL1 = max(maxL1, l) 200 minR1 = min(minR1, r) 201 m = int(input()) 202 for i in range(0, m): 203 (l, r) = map(int, input().split()) 204 maxL2 = max(maxL2, l) 205 minR2 = min(minR2, r) 206 res = max(maxL2 - minR1, maxL1 - minR2); 207 print(max(res, 0)) 208 ``` 209 210 [785C - Anton and Fairy Tale](/contest/785/problem/C "Codeforces Round 404 (Div. 2)") 211 212 This problem had weak pretests. It was made intentionally to cause more hacks. And I have warned you about it in the announcement :) 213 214 **Hint** 215 216 Model the process to determine how the number of corns in the barn changes. 217 218 **Tutorial** 219 220 Tutorial is loading... 221 222 **C++ code** 223 224 ``` 225 #include <iostream> 226 #include <cstdint> 227 228 using namespace std; 229 230 int main() { 231 ios_base::sync_with_stdio(false); 232 int64_t n, m; 233 cin >> n >> m; 234 if (n <= m) { 235 cout << n << endl; 236 } else { 237 n -= m; 238 int64_t l = 0, r = 2e9; 239 while (l < r) { 240 int64_t m = (l + r) / 2; 241 int64_t val = m * (m+1) / 2; 242 if (val >= n) { 243 r = m; 244 } else { 245 l = m+1; 246 } 247 } 248 cout << l + m << endl; 249 } 250 return 0; 251 } 252 ``` 253 254 **Java code** 255 256 ``` 257 import java.io.*; 258 import java.util.*; 259 260 public class SparrowsJava { 261 public static void main(String[] args) throws Exception { 262 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 263 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); 264 StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); 265 long n = Long.parseLong(tokenizer.nextToken()); 266 long m = Long.parseLong(tokenizer.nextToken()); 267 if (n <= m) { 268 writer.write(Long.toString(n)); 269 } else { 270 n -= m; 271 long l = 0, r = (long)2e9; 272 while (l < r) { 273 long med = (l + r) / 2; 274 long val = med * (med+1) / 2; 275 if (val >= n) { 276 r = med; 277 } else { 278 l = med+1; 279 } 280 } 281 writer.write(Long.toString(l + m)); 282 } 283 reader.close(); 284 writer.close(); 285 } 286 } 287 ``` 288 289 **Python code** 290 291 ``` 292 (n, m) = map(int, input().split()) 293 if n <= m: 294 print(n) 295 else: 296 aM = m 297 n -= m 298 (l, r) = (0, int(2e9)) 299 while l < r: 300 m = (l + r) // 2; 301 val = m * (m+1) // 2; 302 if val >= n: 303 r = m 304 else: 305 l = m+1 306 print(l + aM) 307 ``` 308 309 [785D - Anton and School - 2](/contest/785/problem/D "Codeforces Round 404 (Div. 2)") 310 311 **Hint** 312 313 Solve a simplified version of the problem. Let our sequence first contains *x* opening brackets and then contains *y* closing brackets, and the last opening bracket must necessarily appear in our RSBS. Use a naive solution to see how the answer looks. Think what to do next. 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **C++ code** 320 321 ``` 322 #include <iostream> 323 #include <vector> 324 #include <cstdint> 325 326 using namespace std; 327 328 int mod = (int)1e9 + 7; 329 330 int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) { 331 if (!a) { 332 x = 0; 333 y = 1; 334 return b; 335 } 336 int64_t x1, y1; 337 int64_t d = extGcd(b % a, a, x1, y1); 338 x = y1 - (b / a) * x1; 339 y = x1; 340 return d; 341 } 342 343 inline int addMod(int a, int b, int m = mod) { 344 return ((int64_t)a + b) % m; 345 } 346 347 inline int mulMod(int a, int b, int m = mod) { 348 return ((int64_t)a * b) % m; 349 } 350 351 inline int divMod(int a, int b, int m = mod) { 352 int64_t x, y; 353 int64_t g = extGcd(b, m, x, y); 354 if (g != 1) { 355 cerr << "Bad gcd!" << endl; 356 for (;;); 357 } 358 x = (x % m + m) % m; 359 return mulMod(a, x, m); 360 } 361 362 const int factRange = 1000000; 363 int fact[factRange]; 364 365 inline void precalcFactorials() { 366 fact[0] = 1; 367 for (int i = 1; i < factRange; i++) { 368 fact[i] = mulMod(fact[i-1], i); 369 } 370 } 371 372 inline int F(int n) { 373 return (n < 0) ? 0 : fact[n]; 374 } 375 376 inline int C(int k, int n) { 377 return divMod(F(n), mulMod(F(n-k), F(k))); 378 } 379 380 int main() { 381 ios_base::sync_with_stdio(false); 382 string s; 383 cin >> s; 384 int len = s.size(); 385 precalcFactorials(); 386 vector<int> opnLeft(len), clsRight(len); 387 opnLeft[0] = (s[0] == '(') ? 1 : 0; 388 for (int i = 1; i < len; i++) { 389 opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0); 390 } 391 clsRight[len-1] = (s[len-1] == ')') ? 1 : 0; 392 for (int i = len-2; i >= 0; i--) { 393 clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0); 394 } 395 int res = 0; 396 for (int i = 0; i < len; i++) { 397 if (s[i] != '(' || clsRight[i] == 0) { 398 continue; 399 } 400 int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1); 401 res = addMod(res, add); 402 } 403 cout << res << endl; 404 return 0; 405 } 406 ``` 407 408 **Java code** 409 410 ``` 411 import java.io.*; 412 import java.util.*; 413 414 public class BracketsJava { 415 public static int mod = (int)1e9 + 7; 416 417 public static class ExtGcdResult { 418 long x; 419 long y; 420 } 421 422 public static long extGcd(long a, long b, ExtGcdResult res) { 423 if (a == 0) { 424 res.x = 0L; 425 res.y = 1L; 426 return b; 427 } 428 ExtGcdResult newRes = new ExtGcdResult(); 429 long d = extGcd(b % a, a, newRes); 430 res.x = newRes.y - (b / a) * newRes.x; 431 res.y = newRes.x; 432 return d; 433 } 434 435 public static final int addMod(int a, int b) { 436 return (int)(((long)a + b) % mod); 437 } 438 439 public static final int mulMod(int a, int b) { 440 return (int)(((long)a * b) % mod); 441 } 442 443 public static final int divMod(int a, int b) { 444 ExtGcdResult res = new ExtGcdResult(); 445 long g = extGcd(b, mod, res); 446 if (g != 1) { 447 System.out.println("Bad gcd!"); 448 for (;;); 449 } 450 int q = (int)((res.x % mod + mod) % mod); 451 return mulMod(a, q); 452 } 453 454 public static final int[] precalcFactorials() { 455 int[] fact = new int[factRange]; 456 fact[0] = 1; 457 for (int i = 1; i < factRange; i++) { 458 fact[i] = mulMod(fact[i-1], i); 459 } 460 return fact; 461 } 462 463 public static final int factRange = 1000000; 464 public static final int[] fact = precalcFactorials(); 465 466 public static final int F(int n) { 467 return (n < 0) ? 0 : fact[n]; 468 } 469 470 public static final int C(int k, int n) { 471 int res = divMod(F(n), mulMod(F(n-k), F(k))); 472 return divMod(F(n), mulMod(F(n-k), F(k))); 473 } 474 475 public static void main(String[] args) throws Exception { 476 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 477 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); 478 String s = reader.readLine(); 479 int len = s.length(); 480 int[] opnLeft = new int[len], clsRight = new int[len]; 481 opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0; 482 for (int i = 1; i < len; i++) { 483 opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0); 484 } 485 clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0; 486 for (int i = len-2; i >= 0; i--) { 487 clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0); 488 } 489 int res = 0; 490 for (int i = 0; i < len; i++) { 491 if (s.charAt(i) != '(' || clsRight[i] == 0) { 492 continue; 493 } 494 int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1); 495 res = addMod(res, add); 496 } 497 writer.write(Integer.toString(res)); 498 reader.close(); 499 writer.close(); 500 } 501 } 502 ``` 503 504 [785E - Anton and Permutation](/contest/785/problem/E "Codeforces Round 404 (Div. 2)") 505 506 I'm sorry that this problem was not original. I will try my best to prevent this from happening again. 507 508 If you have TL or ML in this problem, don't think that the time/memory limits are too strict. The model solution works in 1.2 seconds and consumes 9 MB memory. 509 510 **Hint** 511 512 Divide all the queries in  blocks. Then divide the positions to the mobile (those ones that will change in this block) and immoblile. Think what to do next. 513 514 **Tutorial** 515 516 Tutorial is loading... 517 518 **C++ code** 519 520 ``` 521 // Thanks to netman for the idea for this wonderful solution :) 522 #include <iostream> 523 #include <fstream> 524 #include <vector> 525 #include <cstdint> 526 #include <algorithm> 527 528 using namespace std; 529 530 class SQRTDecomposition { 531 private: 532 int n, sz; 533 vector<int> val; 534 vector<int> blocks; 535 public: 536 inline void add(int v, int delta) { 537 val[v] += delta; 538 blocks[v / sz] += delta; 539 } 540 541 inline int sum(int l, int r) { 542 if (l < 0) { 543 l = 0; 544 } 545 if (r >= n) { 546 r = n; 547 } 548 r++; 549 int res = 0; 550 int lBlock = (l + sz - 1) / sz, rBlock = r / sz; 551 for (int i = lBlock; i < rBlock; i++) { 552 res += blocks[i]; 553 } 554 int lBlockR = lBlock * sz, rBlockR = rBlock * sz; 555 if (lBlockR >= rBlockR) { 556 for (int i = l; i < r; i++) { 557 res += val[i]; 558 } 559 } else { 560 for (int i = l; i < lBlockR; i++) { 561 res += val[i]; 562 } 563 for (int i = rBlockR; i < r; i++) { 564 res += val[i]; 565 } 566 } 567 return res; 568 } 569 570 inline void clear() { 571 val.assign(val.size(), 0); 572 blocks.assign(blocks.size(), 0); 573 } 574 575 SQRTDecomposition(int n, int sz) 576 : n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) { 577 } 578 }; 579 580 struct ToProcess { 581 int x, y1, y2, sgn, id; 582 }; 583 584 const int BLOCK_SZ_Q = 256; 585 const int BLOCK_SZ_N = 512; 586 const int MAX_N = 200000; 587 588 int n, q; 589 vector<ToProcess> sortedL[MAX_N], sortedR[MAX_N]; 590 SQRTDecomposition sum(MAX_N, BLOCK_SZ_N); 591 int64_t ans[MAX_N], preAns[MAX_N]; 592 pair<int, int> queries[MAX_N]; 593 vector<int> goods; 594 int p[MAX_N]; 595 bool good[MAX_N]; 596 597 inline void add(int q, int sgn, int id) { 598 if (q-1 >= 0) { 599 sortedL[q-1].push_back({q-1, p[q]+1, n-1, sgn, id}); 600 } 601 if (q+1 < n) { 602 sortedR[q+1].push_back({q+1, 0, p[q]-1, sgn, id}); 603 } 604 } 605 606 int main() { 607 ios_base::sync_with_stdio(false); 608 cin >> n >> q; 609 for (int i = 0; i < n; i++) { 610 p[i] = i; 611 } 612 for (int i = 0; i < q; i++) { 613 cin >> queries[i].first >> queries[i].second; 614 queries[i].first--; queries[i].second--; 615 } 616 int64_t cnt = 0; 617 for (int i = 0; i < q; i += BLOCK_SZ_Q) { 618 int iEnd = min(q, i + BLOCK_SZ_Q); 619 for (int j = 0; j < n; j++) { 620 good[j] = false; 621 } 622 for (int j = i; j < iEnd; j++) { 623 good[queries[j].first] = true; 624 good[queries[j].second] = true; 625 } 626 goods.clear(); 627 for (int j = 0; j < n; j++) { 628 if (good[j]) { 629 goods.push_back(j); 630 } 631 } 632 int64_t goodCnt = 0; 633 for (int j = 0; j < n; j++) { 634 sortedL[j].clear(); 635 sortedR[j].clear(); 636 } 637 for (int j = i; j < iEnd; j++) { 638 int a = queries[j].first, b = queries[j].second; 639 if (a == b) { 640 ans[j] += goodCnt; 641 continue; 642 } 643 for (int k = 0; k < (int)goods.size(); k++) { 644 int q = goods[k]; 645 if (q == a || q == b) { 646 continue; 647 } 648 if ((p[q] < p[a] && q > a) || 649 (p[q] > p[a] && q < a)) { 650 goodCnt--; 651 } 652 if ((p[q] < p[b] && q > b) || 653 (p[q] > p[b] && q < b)) { 654 goodCnt--; 655 } 656 if ((p[q] < p[b] && q > a) || 657 (p[q] > p[b] && q < a)) { 658 goodCnt++; 659 } 660 if ((p[q] < p[a] && q > b) || 661 (p[q] > p[a] && q < b)) { 662 goodCnt++; 663 } 664 } 665 if ((a < b && p[a] > p[b]) || 666 (a > b && p[a] < p[b])) { 667 goodCnt--; 668 } else { 669 goodCnt++; 670 } 671 ans[j] += goodCnt; 672 add(a, -1, j); 673 add(b, -1, j); 674 swap(p[a], p[b]); 675 add(a, +1, j); 676 add(b, +1, j); 677 } 678 sum.clear(); 679 for (int j = 0; j < n; j++) { 680 if (!good[j]) { 681 sum.add(p[j], 1); 682 } 683 for (int k = 0; k < (int)sortedL[j].size(); k++) { 684 ToProcess &cur = sortedL[j][k]; 685 int64_t res = sum.sum(cur.y1, cur.y2); 686 res *= cur.sgn; 687 preAns[cur.id] += res; 688 } 689 } 690 sum.clear(); 691 for (int j = n-1; j >= 0; j--) { 692 if (!good[j]) { 693 sum.add(p[j], 1); 694 } 695 for (int k = 0; k < (int)sortedR[j].size(); k++) { 696 ToProcess &cur = sortedR[j][k]; 697 int64_t res = sum.sum(cur.y1, cur.y2); 698 res *= cur.sgn; 699 preAns[cur.id] += res; 700 } 701 } 702 for (int j = i; j < iEnd; j++) { 703 if (j != i) { 704 preAns[j] += preAns[j-1]; 705 } 706 ans[j] += cnt + preAns[j]; 707 } 708 cnt = ans[iEnd - 1]; 709 } 710 for (int i = 0; i < q; i++) { 711 cout << ans[i] << "\n"; 712 } 713 return 0; 714 } 715 ``` 716 717 **Java code** 718 719 ``` 720 import java.io.*; 721 import java.util.*; 722 723 public class InversionNSqrtNNoVectors { 724 private static final int BLOCK_SZ_Q = 256; 725 private static final int BLOCK_SZ_N = 512; 726 727 public static class ToProcess { 728 public int x, y1, y2, sgn, id; 729 730 public void set(int pX, int pY1, int pY2, int pSgn, int pId) { 731 x = pX; 732 y1 = pY1; 733 y2 = pY2; 734 sgn = pSgn; 735 id = pId; 736 } 737 738 public ToProcess() { 739 } 740 } 741 742 public static class ToProcessCompareAsc implements Comparator<ToProcess> { 743 @Override 744 public int compare(ToProcess o1, ToProcess o2) { 745 return o1.x - o2.x; 746 } 747 } 748 749 public static class ToProcessCompareDesc implements Comparator<ToProcess> { 750 @Override 751 public int compare(ToProcess o1, ToProcess o2) { 752 return o2.x - o1.x; 753 } 754 } 755 756 static int n, q; 757 static int[] p; 758 static ToProcess[] queryL, queryR; 759 static int queryLCnt, queryRCnt; 760 static SQRTDecomposition sum; 761 static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc(); 762 static ToProcessCompareDesc descCmp = new ToProcessCompareDesc(); 763 764 public static final void add(int q, int sgn, int id) { 765 if (q-1 >= 0) { 766 queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id); 767 } 768 if (q+1 < n) { 769 queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id); 770 } 771 } 772 773 public static void main(String[] args) throws Exception { 774 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 775 BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); 776 StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); 777 n = Integer.parseInt(tokenizer.nextToken()); 778 q = Integer.parseInt(tokenizer.nextToken()); 779 int[] qL = new int[q], qR = new int[q]; 780 long[] ans = new long[q], preAns = new long[q]; 781 p = new int[n]; 782 for (int i = 0; i < n; i++) { 783 p[i] = i; 784 } 785 for (int i = 0; i < q; i++) { 786 tokenizer = new StringTokenizer(reader.readLine()); 787 qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1; 788 qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1; 789 } 790 long cnt = 0; 791 boolean[] good = new boolean[n]; 792 int[] goods = new int[n]; 793 int goodsSize = 0; 794 queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q]; 795 for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) { 796 queryL[j] = new ToProcess(); 797 queryR[j] = new ToProcess(); 798 } 799 SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N); 800 for (int i = 0; i < q; i += BLOCK_SZ_Q) { 801 int iEnd = Math.min(q, i + BLOCK_SZ_Q); 802 Arrays.fill(good, false); 803 for (int j = i; j < iEnd; j++) { 804 good[qL[j]] = true; 805 good[qR[j]] = true; 806 } 807 goodsSize = 0; 808 for (int j = 0; j < n; j++) { 809 if (good[j]) { 810 goods[goodsSize++] = j; 811 } 812 } 813 long goodCnt = 0; 814 queryLCnt = 0; 815 queryRCnt = 0; 816 for (int j = i; j < iEnd; j++) { 817 int a = qL[j], b = qR[j]; 818 if (a == b) { 819 ans[j] += goodCnt; 820 continue; 821 } 822 for (int k = 0; k < goodsSize; k++) { 823 int q = goods[k]; 824 if (q == a || q == b) { 825 continue; 826 } 827 if ((p[q] < p[a] && q > a) || 828 (p[q] > p[a] && q < a)) { 829 goodCnt--; 830 } 831 if ((p[q] < p[b] && q > b) || 832 (p[q] > p[b] && q < b)) { 833 goodCnt--; 834 } 835 if ((p[q] < p[b] && q > a) || 836 (p[q] > p[b] && q < a)) { 837 goodCnt++; 838 } 839 if ((p[q] < p[a] && q > b) || 840 (p[q] > p[a] && q < b)) { 841 goodCnt++; 842 } 843 } 844 if ((a < b && p[a] > p[b]) || 845 (a > b && p[a] < p[b])) { 846 goodCnt--; 847 } else { 848 goodCnt++; 849 } 850 ans[j] += goodCnt; 851 add(a, -1, j); 852 add(b, -1, j); 853 int tmp = p[a]; 854 p[a] = p[b]; 855 p[b] = tmp; 856 add(a, +1, j); 857 add(b, +1, j); 858 } 859 sum.clear(); 860 Arrays.sort(queryL, 0, queryLCnt, ascCmp); 861 int curL = 0; 862 for (int j = 0; j < n; j++) { 863 if (!good[j]) { 864 sum.add(p[j], 1); 865 } 866 for (; curL < queryLCnt; curL++) { 867 ToProcess cur = queryL[curL]; 868 if (cur.x != j) { 869 break; 870 } 871 int res = sum.sum(cur.y1, cur.y2); 872 res *= cur.sgn; 873 preAns[cur.id] += res; 874 } 875 } 876 sum.clear(); 877 Arrays.sort(queryR, 0, queryRCnt, descCmp); 878 int curR = 0; 879 for (int j = n-1; j >= 0; j--) { 880 if (!good[j]) { 881 sum.add(p[j], 1); 882 } 883 for (; curR < queryRCnt; curR++) { 884 ToProcess cur = queryR[curR]; 885 if (cur.x != j) { 886 break; 887 } 888 int res = sum.sum(cur.y1, cur.y2); 889 res *= cur.sgn; 890 preAns[cur.id] += res; 891 } 892 } 893 for (int j = i; j < iEnd; j++) { 894 if (j != i) { 895 preAns[j] += preAns[j-1]; 896 } 897 ans[j] += cnt + preAns[j]; 898 } 899 cnt = ans[iEnd - 1]; 900 } 901 for (int i = 0; i < q; i++) { 902 writer.write(Long.toString(ans[i])); 903 writer.newLine(); 904 } 905 reader.close(); 906 writer.close(); 907 } 908 } 909 910 class SQRTDecomposition { 911 private int n; 912 private int sz; 913 private int[] val; 914 private int[] blocks; 915 916 public final void add(int v, int delta) { 917 val[v] += delta; 918 blocks[v / sz] += delta; 919 } 920 921 public final int sum(int l, int r) { 922 if (l < 0) { 923 l = 0; 924 } 925 if (r >= n) { 926 r = n; 927 } 928 r++; 929 int res = 0; 930 int lBlock = (l + sz - 1) / sz, rBlock = r / sz; 931 for (int i = lBlock; i < rBlock; i++) { 932 res += blocks[i]; 933 } 934 int lBlockR = lBlock * sz, rBlockR = rBlock * sz; 935 if (lBlockR >= rBlockR) { 936 for (int i = l; i < r; i++) { 937 res += val[i]; 938 } 939 } else { 940 for (int i = l; i < lBlockR; i++) { 941 res += val[i]; 942 } 943 for (int i = rBlockR; i < r; i++) { 944 res += val[i]; 945 } 946 } 947 return res; 948 } 949 950 public void clear() { 951 Arrays.fill(val, 0); 952 Arrays.fill(blocks, 0); 953 } 954 955 SQRTDecomposition(int pN, int pSz) { 956 n = pN; 957 sz = pSz; 958 val = new int[n]; 959 blocks = new int[(n + sz - 1) / sz]; 960 } 961 } 962 ``` 963 964 Alternative solution from [Vladik](/profile/Vladik "Candidate Master Vladik"): 965 966 **C++ code** 967 968 ``` 969 #include <iostream> 970 #include <cstdio> 971 #include <algorithm> 972 #include <cmath> 973 #include <set> 974 #include <map> 975 #include <vector> 976 #include <iomanip> 977 978 #define sqr(a) (a)*(a) 979 #define all(a) (a).begin(), (a).end() 980 using namespace std; 981 982 template <typename T> 983 T next_int() { 984 T ans = 0, t = 1; 985 char ch; 986 do { ch = getchar(); } while(ch <= ' ') ; 987 if(ch == '-') { 988 t = -1; 989 ch = getchar(); 990 } 991 while(ch >= '0' && ch <= '9') { 992 ans = ans * 10 + (ch - '0'); 993 ch = getchar(); 994 } 995 return ans * t; 996 } 997 998 string next_token() { 999 char ch; 1000 string ans = ""; 1001 do { ch = getchar(); } while(ch <= ' ') ; 1002 while(ch >= ' ') { 1003 ans += ch; 1004 ch = getchar(); 1005 } 1006 return ans; 1007 } 1008 1009 const long long INF = (long long)1e18 + 227 + 1; 1010 const int INFINT = (int)1e9 + 227 + 1; 1011 const int MAXN = (int)2e5 + 227 + 1; 1012 const int MOD = (int)1e9 + 7; 1013 const long double EPS = 1e-9; 1014 1015 long long bin_pow(long long n, long long k) { 1016 if(!k) return 1; 1017 long long ans = bin_pow(n, k / 2); 1018 ans = ans * ans % MOD; 1019 if(k % 2) ans = ans * n % MOD; 1020 return ans; 1021 } 1022 1023 struct tree { 1024 int size_block; 1025 int len; 1026 1027 tree(int len) : len(len) { 1028 size_block = sqrt(len); 1029 1030 kek.resize(len / size_block + 1, vector<int>(size_block, 0)); 1031 1032 pr_block.resize(len / size_block + 1, 0); 1033 } 1034 1035 vector<int> pr_block; 1036 vector<vector<int> > kek; 1037 1038 void inc(int pos, int num) { 1039 int x = pos / size_block; 1040 1041 for(int i = pos % size_block; i < size_block; i++) { 1042 kek[x][i] += num; 1043 } 1044 1045 for(int i = 0; i <= len / size_block; i++) 1046 if(i == 0) { 1047 pr_block[i] = kek[i][size_block - 1]; 1048 } else { 1049 pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; 1050 } 1051 } 1052 1053 int f(int a) { 1054 return a / size_block; 1055 } 1056 1057 long long get(vector<int> &a, int l, int r, bool ok = 1) { 1058 if(ok == 1) { 1059 l %= size_block; 1060 r %= size_block; 1061 } 1062 1063 return a[r] - (l ? a[l - 1] : 0); 1064 } 1065 1066 int get(int l, int r) { 1067 if(l > r) return 0; 1068 1069 r = min(r, len); 1070 1071 if(f(l) == f(r)) 1072 return get(kek[f(l)], l, r); 1073 1074 int ans = 0; 1075 1076 if(l % size_block) { 1077 ans += get(kek[f(l)], l, size_block - 1); 1078 1079 l += size_block - l % size_block; 1080 } 1081 1082 if(r % size_block != size_block - 1) { 1083 ans += get(kek[f(r)], 0, r); 1084 1085 r -= r % size_block + 1; 1086 } 1087 1088 ans += get(pr_block, f(l), f(r), 0); 1089 1090 return ans; 1091 } 1092 1093 int get_pref(int p) { 1094 return get(1, p - 1); 1095 } 1096 1097 int get_suff(int p) { 1098 return get(p + 1, len); 1099 } 1100 } ; 1101 1102 struct mda { 1103 vector<int> a; 1104 vector<tree> t; 1105 int len, sz; 1106 long long ans; 1107 1108 mda(int len) : len(len) { 1109 sz = 2000; 1110 ans = 0; 1111 1112 a.resize(len + 1); 1113 for(int i = 1; i <= len; i++) 1114 a[i] = i; 1115 1116 for(int i = 1; i <= len; i += sz) { 1117 t.push_back(tree(len)); 1118 for(int j = i; j < i + sz && j <= len; j++) 1119 add(j, j); 1120 } 1121 } 1122 1123 int get_pref(int L, int R, int k) { 1124 int ans = 0; 1125 1126 for(int l = 1; l <= R; l += sz) { 1127 int r = l + sz - 1; 1128 1129 if(r < L || l > R) continue; 1130 1131 if(L <= l && r <= R) 1132 ans += t[(l - 1) / sz].get_pref(k); 1133 else 1134 for(int i = max(l, L); i <= min(r, R); i++) 1135 ans += (a[i] < k); 1136 } 1137 1138 return ans; 1139 } 1140 1141 int get_suff(int L, int R, int k) { 1142 int ans = 0; 1143 1144 for(int l = 1; l <= R; l += sz) { 1145 int r = l + sz - 1; 1146 1147 if(r < L || l > R) continue; 1148 1149 if(L <= l && r <= R) 1150 ans += t[(l - 1) / sz].get_suff(k); 1151 else 1152 for(int i = max(l, L); i <= min(r, R); i++) 1153 ans += (a[i] > k); 1154 } 1155 1156 return ans; 1157 } 1158 1159 void del(int p, int k) { 1160 p = (p - 1) / sz; 1161 t[p].inc(k, -1); 1162 } 1163 1164 void add(int p, int k) { 1165 p = (p - 1) / sz; 1166 t[p].inc(k, 1); 1167 } 1168 1169 void sw(int i, int j) { 1170 if(i == j) return; 1171 if(i > j) swap(i, j); 1172 1173 ans -= get_pref(i, j, a[i]); 1174 ans -= get_suff(i, j, a[j]); 1175 1176 if(a[i] > a[j]) ans++; 1177 1178 del(i, a[i]); 1179 del(j, a[j]); 1180 swap(a[i], a[j]); 1181 add(i, a[i]); 1182 add(j, a[j]); 1183 1184 ans += get_pref(i, j, a[i]); 1185 ans += get_suff(i, j, a[j]); 1186 1187 if(a[i] > a[j]) ans--; 1188 } 1189 } ; 1190 1191 int main() { 1192 // freopen(".in", "r", stdin); 1193 1194 int n, m; cin >> n >> m; 1195 1196 mda t(n); 1197 1198 for(int i = 0; i < m; i++) { 1199 int x, y; cin >> x >> y; 1200 1201 t.sw(x, y); 1202 1203 cout << t.ans << "\n"; 1204 } 1205 } 1206 ``` 1207 1208 Alternative solution from [netman](/profile/netman "Master netman"): 1209 1210 **Java code** 1211 1212 ``` 1213 import java.io.*; 1214 import java.util.*; 1215 1216 public class NsqrtNlogNnetman implements Runnable { 1217 static class InputReader { 1218 BufferedReader reader; 1219 StringTokenizer tokenizer; 1220 InputReader(InputStream in) { 1221 reader = new BufferedReader(new InputStreamReader(in), 32768); 1222 tokenizer = null; 1223 } 1224 String next() { 1225 while (tokenizer == null || !tokenizer.hasMoreTokens()) { 1226 try { 1227 tokenizer = new StringTokenizer(reader.readLine()); 1228 } catch (IOException e) { 1229 e.printStackTrace(); 1230 throw new RuntimeException(e); 1231 } 1232 } 1233 return tokenizer.nextToken(); 1234 } 1235 int nextInt() { 1236 return Integer.parseInt(next()); 1237 } 1238 long nextLong() { 1239 return Long.parseLong(next()); 1240 } 1241 double nextDouble() { 1242 return Double.parseDouble(next()); 1243 } 1244 } 1245 1246 static class Fenwick { 1247 int[] ft; 1248 Fenwick(int n) { 1249 ft = new int[n]; 1250 } 1251 void add(int r, int val) { 1252 while (r < ft.length) { 1253 ft[r] += val; 1254 r |= r + 1; 1255 } 1256 } 1257 int sum(int r) { 1258 int res = 0; 1259 while (r >= 0) { 1260 res += ft[r]; 1261 r = (r & (r + 1)) - 1; 1262 } 1263 return res; 1264 } 1265 void clear() { 1266 Arrays.fill(ft, 0); 1267 } 1268 } 1269 1270 static class Query { 1271 int x, bound, sign, id; 1272 Query(int x, int bound, int sign, int id) { 1273 this.x = x; 1274 this.bound = bound; 1275 this.sign = sign; 1276 this.id = id; 1277 } 1278 } 1279 1280 static void getOnPrefSmaller(List<Query> qrs, int r, int y, int id, int sign) { 1281 qrs.add(new Query(r, y, sign, id)); 1282 } 1283 1284 static void getOnPrefBetween(List<Query> qrs, int r, int x, int y, int id, int sign) { 1285 getOnPrefSmaller(qrs, r, y, id, sign); 1286 getOnPrefSmaller(qrs, r, x, id, -sign); 1287 } 1288 1289 static void getOnSegmentBetween(List<Query> qrs, int l, int r, int x, int y, int id, int sign) { 1290 if (x > y) return; 1291 getOnPrefBetween(qrs, r, x, y, id, sign); 1292 getOnPrefBetween(qrs, l, x, y, id, -sign); 1293 } 1294 1295 @Override 1296 public void run() { 1297 1298 InputReader in = new InputReader(System.in); 1299 PrintWriter out = new PrintWriter(System.out); 1300 1301 int n = in.nextInt(); 1302 int q = in.nextInt(); 1303 1304 int[] l = new int[q]; 1305 int[] r = new int[q]; 1306 1307 for (int i = 0; i < q; i++) { 1308 l[i] = in.nextInt() - 1; 1309 r[i] = in.nextInt() - 1; 1310 } 1311 1312 int[] perm = new int[n]; 1313 1314 for (int i = 0; i < n; i++) { 1315 perm[i] = n - i - 1; 1316 } 1317 1318 final int BLOCK = 300; 1319 1320 long inv = 0L; 1321 1322 boolean[] isInteresting = new boolean[n]; 1323 1324 long[] add = new long[q]; 1325 1326 Fenwick f = new Fenwick(n); 1327 1328 for (int i = 0; i < q; i += BLOCK) { 1329 int from = i, to = Math.min(i + BLOCK, q) - 1; 1330 List<Integer> lst = new ArrayList<>(); 1331 for (int j = from; j <= to; j++) { 1332 lst.add(l[j]); 1333 lst.add(r[j]); 1334 } 1335 lst.sort(Integer::compareTo); 1336 lst = new ArrayList<>(new HashSet<>(lst)); 1337 int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray(); 1338 for (int pos : interestingPositions) { 1339 isInteresting[pos] = true; 1340 } 1341 List<Query> qrs = new ArrayList<>(); 1342 for (int j = from; j <= to; j++) { 1343 if (l[j] == r[j]) continue; 1344 if (l[j] > r[j]) { 1345 int tmp = l[j]; 1346 l[j] = r[j]; 1347 r[j] = tmp; 1348 } 1349 if (perm[l[j]] < perm[r[j]]) { 1350 getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1); 1351 int leftValue = perm[l[j]]; 1352 int rightValue = perm[r[j]]; 1353 for (int pos : interestingPositions) { 1354 if (pos > l[j] && pos < r[j] && perm[pos] > leftValue && perm[pos] < rightValue) { 1355 add[j] -= 2; 1356 } 1357 } 1358 add[j]--; 1359 } else { 1360 getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1); 1361 int leftValue = perm[l[j]]; 1362 int rightValue = perm[r[j]]; 1363 for (int pos : interestingPositions) { 1364 if (pos > l[j] && pos < r[j] && perm[pos] > rightValue && perm[pos] < leftValue) { 1365 add[j] += 2; 1366 } 1367 } 1368 add[j]++; 1369 } 1370 int tmp = perm[l[j]]; 1371 perm[l[j]] = perm[r[j]]; 1372 perm[r[j]] = tmp; 1373 } 1374 qrs.sort(Comparator.comparingInt(a -> -a.x)); 1375 1376 f.clear(); 1377 for (int pos = 0; pos < n; pos++) { 1378 if (!isInteresting[pos]) { 1379 f.add(perm[pos], 1); 1380 } 1381 while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) { 1382 Query t = qrs.get(qrs.size() - 1); 1383 qrs.remove(qrs.size() - 1); 1384 add[t.id] += 2 * t.sign * f.sum(t.bound); 1385 } 1386 } 1387 for (int j = from; j <= to; j++) { 1388 inv += add[j]; 1389 out.println(inv); 1390 } 1391 for (int pos : interestingPositions) { 1392 isInteresting[pos] = false; 1393 } 1394 } 1395 1396 out.close(); 1397 } 1398 1399 public static void main(String[] args) { 1400 new Thread(null, new NsqrtNlogNnetman(), "1", 1L << 28).run(); 1401 } 1402 } 1403 ```