1864.md (48099B)
1 Source: https://codeforces.com/blog/entry/119772 2 3 Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/. 4 5 During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused. 6 7 In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) [Invitation to TheForces Round #22 (Interesting-Forces)](https://mirror.codeforces.com/blog/entry/119771) 8 9 ### [1864A-Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A) 10 11 Idea : [wuhudsm](/profile/wuhudsm "Master wuhudsm") 12 13 **Tutorial** 14 15 We use the following greedy construction: 16 17 For all $i$ ($1 \lt i \lt n$), set $a_i=a_{i+1}-(n-i)$. If $a_2-a_1 \geq n-1$, we've found a solution, otherwise there is no solution. 18 19 Proof. Assume there's a solution which includes an index $i$ ($1 \lt i \lt n$) such that $a_{i+1}-a_i \gt n-i$. We can make $a_j:=a_j+\Delta$ for all $j$ ($2 \le j \le i$), where $\Delta=a_{i+1}-a_i-(n-i)$. After several processes like this, we get a solution the same as greedy construction gives. This leads to a contradiction. 20 21 **solution** 22 23 ``` 24 #include <bits/stdc++.h> 25 26 #define all(a) (a).begin(), (a).end() 27 #define sz(a) (int)(a).size() 28 #define pb push_back 29 #define mp make_pair 30 31 using namespace std; 32 33 typedef long long ll; 34 typedef long double ld; 35 typedef pair<int, int> pii; 36 37 int main() { 38 39 ios_base::sync_with_stdio(false); 40 cin.tie(0); 41 cout.tie(0); 42 43 int tt; 44 cin >> tt; 45 while (tt--) { 46 int x, y, n; 47 cin >> x >> y >> n; 48 vector<int> a(n); 49 a[0] = x, a[n - 1] = y; 50 int d = 1; 51 for (int i = n - 2; i >= 1; --i) { 52 a[i] = a[i + 1] - d; 53 ++d; 54 } 55 bool ok = true; 56 for (int i = 0; i + 1 < n; ++i) { 57 if (a[i + 1] <= a[i]) { 58 ok = false; 59 } 60 } 61 for (int i = 0; i + 2 < n; ++i) { 62 int p = a[i + 1] - a[i]; 63 int q = a[i + 2] - a[i + 1]; 64 if (p <= q) { 65 ok = false; 66 } 67 } 68 if (!ok) { 69 cout << "-1\n"; 70 continue; 71 } 72 for (int i = 0; i < n; ++i) { 73 cout << a[i] << " "; 74 } 75 cout << "\n"; 76 } 77 78 } 79 ``` 80 81 ### [1864B-Swap and Reverse](https://mirror.codeforces.com/contest/1864/problem/B) 82 83 Idea : [Amir_Parsa](/profile/Amir_Parsa "Master Amir_Parsa"), [chromate00](/profile/chromate00 "Expert chromate00") 84 85 **Tutorial** 86 87 By the first kind of operation, we already know that every odd index (same for the even ones) can be swapped with each other freely. Therefore, let us write down the values of the indices modulo $2$. For example, if $n$ is $10$, the indices modulo $2$ are $[1,0,1,0,1,0,1,0,1,0]$. Now, we consider the two cases. 88 89 * When $k$ is odd. 90 91 We can find out that after reversing any subarray of length $k$, the indices modulo $2$ do not change. So in this case, any series of the second operation is identical to some series of the first operation. Therefore, you should sort the odd indices and the even indices separately, and output the result of merging them into one string. 92 93 * When $k$ is even. 94 95 Let us observe how we can swap two adjacent indices in this case. First, reverse $[i,i+k-1]$, and then reverse $[i+1,i+k]$. If we do this on $[1,0,1,0,1,0,1,0,1,0]$, assuming $i=1$ and $k=6$, the indices modulo $2$ turn into $[0,1,0,1,0,1,1,0,1,0]$, and then $[0,1,1,0,1,0,1,0,1,0]$. Using these two steps and some series of the first operation, we can see that we can swap any two adjacent indices as a result. And such a series of operation is always possible, as $k \lt n$. Therefore, we can sort the entire string, and output the result. 96 97 **solution** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 #define all(a) (a).begin(), (a).end() 103 #define sz(a) (int)(a).size() 104 #define pb push_back 105 #define mp make_pair 106 107 using namespace std; 108 109 typedef long long ll; 110 typedef long double ld; 111 typedef pair<int, int> pii; 112 113 int main() { 114 115 ios_base::sync_with_stdio(false); 116 cin.tie(0); 117 cout.tie(0); 118 119 int tt; 120 cin >> tt; 121 while (tt--) { 122 int n, k; 123 cin >> n >> k; 124 string s; 125 cin >> s; 126 vector<char> odd, even; 127 for (int i = 0; i < n; ++i) { 128 if (i % 2 == 0) { 129 even.pb(s[i]); 130 } else { 131 odd.pb(s[i]); 132 } 133 } 134 sort(all(even)); 135 sort(all(odd)); 136 string ans1 = ""; 137 for (int i = 0, j = 0; i < sz(even) || j < sz(odd); ++i, ++j) { 138 if (i < sz(even)) { 139 ans1 += even[i]; 140 } 141 if (j < sz(odd)) { 142 ans1 += odd[i]; 143 } 144 } 145 if (k % 2 == 0) { 146 sort(all(s)); 147 cout << s << "\n"; 148 continue; 149 } 150 cout << ans1 << "\n"; 151 } 152 153 } 154 ``` 155 156 **bonus** 157 158 Try to solve the problem if $n = k$ was allowed. 159 160 ### [1864C-Divisor Chain](https://mirror.codeforces.com/contest/1864/problem/C) 161 162 Idea : [wuhudsm](/profile/wuhudsm "Master wuhudsm") 163 164 **Tutorial** 165 166 Let us divide the task into two steps, on each step we will use each divisor at most once. For convenience, let us denote $L$ as the largest value, such that $2^L \le x$ holds. The two steps are as follows. 167 168 * Reduce $x$ to $2^L$. 169 170 Given any integer $x$, we can see that its lowest significant bit is a divisor of $x$. If $x$ has more than one bit, we can repeatedly subtract the value corresponding to the lowest significant bit of $x$. When $x$ finally has only one bit, finish the first step. In this step, we have only used each significant bit of $x$ at most once. 171 172 * Reduce $2^L$ to $1$. 173 174 We can find a way to reduce $2^L$ to $1$ by using each bit exactly once. Formally, if $k \ge 0$, then $2^{k+1}-2^k=2^k$, and $2^k$ is a divisor of $2^{k+1}$. Thus, by subtracting $2^{L-1},2^{L-2},\ldots,1$ in order, we reach $1$ from $2^L$ by using each bit from the $0$-th bit to the $(L-1)$-st bit exactly once. 175 176 As a result, we can reduce $x$ to $1$ by using each power of $2$ at most twice (once from the first step, once from the second step). Since we used each bit at most twice, the time complexity for solving one test case is $O(\log x)$. 177 178 Due to the lenient constraints, some solutions with $O(\sqrt x)$ time complexity should pass as well (as long as they fit into the $1000$ operations limit). 179 180 **solution** 181 182 ``` 183 #include <bits/stdc++.h> 184 185 #define all(a) (a).begin(), (a).end() 186 #define sz(a) (int)(a).size() 187 #define pb push_back 188 #define mp make_pair 189 190 using namespace std; 191 192 typedef long long ll; 193 typedef long double ld; 194 typedef pair<int, int> pii; 195 196 bool bit(int mask, int pos) { 197 return (mask >> pos) & 1; 198 } 199 200 int main() { 201 202 ios_base::sync_with_stdio(false); 203 cin.tie(0); 204 cout.tie(0); 205 206 int tt; 207 cin >> tt; 208 while (tt--) { 209 int x; 210 cin >> x; 211 int p; 212 vector<int> ans; 213 ans.pb(x); 214 for (int i = 0; ; ++i) { 215 if (bit(x, i)) { 216 if (x == (1 << i)) { 217 p = i; 218 break; 219 } 220 x -= (1 << i); 221 ans.pb(x); 222 } 223 } 224 while (p > 0) { 225 x -= (1 << (p - 1)); 226 ans.pb(x); 227 --p; 228 } 229 cout << sz(ans) << "\n"; 230 for (int y : ans) { 231 cout << y << " "; 232 } 233 cout << "\n"; 234 } 235 236 } 237 ``` 238 239 ### [1864D-Matrix Cascade](https://mirror.codeforces.com/contest/1864/problem/D) 240 241 Idea : [AquaMoon](/profile/AquaMoon "International Master AquaMoon") 242 243 **Tutorial** 244 245 Firstly, the first row has some elements that are $\text{1}$ s and some elements that are $\text{0}$ s. The elements that are $\text{1}$ can only be turned into $\text{0}$ by operating on the corresponding cell an odd number of times, and the elements that are $\text{0}$ can only be turned into $\text{0}$ by operating on the corresponding cell an even number of times. Two operations on the same cell are equivalent to no operation, so only one operation is performed on the corresponding cell of the element that is $\text{1}$ in the first row. Thus, the operation on the first row is deterministic. Subsequent rows are affected by the operations in the first row, so it is sufficient to proceed to consider rows $2$ to $n$ in the same way. 246 247 Now consider how to quickly deal with the effect of the preceding rows on the following rows. An operation on position $(x,y)$ will simultaneously invert all the elements from column $y-1$ to column $y+1$ in row $x+1$, and from column $y-2$ to column $y+2$ in row $x+2$, and son on. Thus, the elements being inverted are exactly the portion of the matrix sandwiched between lines passing through $(x,y)$ with slopes $1$ and $-1$. Let $b$ denote the effect of the line with slope $1$ from all predecing rows, and let $c$ denote the effect of the line with slope $-1$ from all preceding rows. % To optimize complexity, $b$, $c$ are both obtained using difference arrays to the current line using prefix sums to obtain the $b,c$ values at that time. 248 249 After an operation on $(i,j)$, $b[i+1][j-1]$ is marked, and $c[i+1][j+2]$ is marked. Next, $b[i][j]$ inherits $b[i-1][j+1]$, and $c[i][j]$ inherits $c[i-1][j-1]$. For the current row, the effect of the previous rows is obtained by maintaining the prefix sums on $b$ and $c$. The total complexity is $O(n^2)$. 250 251 **solution** 252 253 ``` 254 #include <bits/stdc++.h> 255 256 #define all(a) (a).begin(), (a).end() 257 #define sz(a) (int)(a).size() 258 #define pb push_back 259 #define mp make_pair 260 261 using namespace std; 262 263 typedef long long ll; 264 typedef long double ld; 265 typedef pair<int, int> pii; 266 267 int main() { 268 269 ios_base::sync_with_stdio(false); 270 cin.tie(0); 271 cout.tie(0); 272 273 int tt; 274 cin >> tt; 275 276 while (tt--) { 277 int n; 278 cin >> n; 279 vector<string> a(n); 280 for (int i = 0; i < n; ++i) { 281 cin >> a[i]; 282 } 283 int ans = 0; 284 vector<vector<int> > val(n, vector<int>(n, 0)); 285 vector<vector<int> > sum(n, vector<int>(n, 0)); 286 for (int i = 0; i < n; ++i) { 287 for (int j = 0; j < n; ++j) { 288 if (i == 0) { 289 290 } else if (i == 1) { 291 for (int k = max(0, j - 1); k <= min(j + 1, n - 1); ++k) { 292 sum[i][j] ^= sum[i - 1][k]; 293 } 294 } else { 295 if (j == 0) { 296 sum[i][j] ^= sum[i - 2][j]; 297 } else { 298 sum[i][j] ^= sum[i - 1][j - 1]; 299 } 300 if (j == n - 1) { 301 sum[i][j] ^= sum[i - 2][j]; 302 } else { 303 sum[i][j] ^= sum[i - 1][j + 1]; 304 } 305 sum[i][j] ^= sum[i - 2][j]; 306 sum[i][j] ^= val[i - 1][j]; 307 } 308 if (sum[i][j] ^ (a[i][j] - '0')) { 309 ++ans; 310 sum[i][j] ^= 1; 311 val[i][j] = 1; 312 } 313 } 314 } 315 cout << ans << "\n"; 316 } 317 318 } 319 ``` 320 321 ### [1864E-Guess Game](https://mirror.codeforces.com/contest/1864/problem/E) 322 323 Idea : [wuhudsm](/profile/wuhudsm "Master wuhudsm") 324 325 **Tutorial** 326 327 First, let's analize a single game for fixed $a$, $b$, and how many turns it takes. 328 329 Consider the binary representation of $a \mid b$. We consider bits from highest to lowest. For bits with a value of $0$, we can ignore it because it firmly tells us that both bits of $a$ and $b$ are $0$. For convenience, we assume that all bits of $a \mid b$ are $1$. 330 331 In the first round, if the highest bit of $a$ is $0$, then Alice can immediately say that $a \lt b$. Otherwise, in the second round of the game, Bob knows that the highest bit of $a$ is not $0$. If the highest or the second highest bit of b is $0$, then Bob can immediately say that $a \gt b$. Otherwise, in the third round of the game, Alice knows that the highest and the second highest bits of $b$ are not $0$, and so on. 332 333 Consider only set bits in $a \mid b$. Let's enumerate these bits from highest to lowest. After some observation, we can conclude that: 334 335 * If $a \lt b$ and the $i$-th bit in $a$ is zero, then the answer is $i+1−(i\%2 == 1)$; 336 * If $a=b$, then the answer is $k+1$, where $k$ is the number of set bits in $a \mid b$; 337 * If $a \gt b$ and the $i$-th bit in $b$ is zero, then the answer is $i+(i\%2 == 1)$. 338 339 Now that we have a brute force algorithm for $O (n^2 \log A)$, how can we optimize it? 340 341 We can build a bit trie and traverse all nodes. We can easily calculate the number of $1$s that pass from a node to the root node, as well as the number of numbers prefixed with it and followed by $0$ (or $1$). Use this information to calculate the answer. 342 343 **solution** 344 345 ``` 346 #include <bits/stdc++.h> 347 348 #define all(a) (a).begin(), (a).end() 349 #define sz(a) (int)(a).size() 350 #define pb push_back 351 #define mp make_pair 352 353 using namespace std; 354 355 typedef long long ll; 356 typedef long double ld; 357 typedef pair<int, int> pii; 358 359 struct node { 360 int to[2]; 361 int cnt; 362 node() { 363 to[0] = to[1] = -1; 364 cnt = 0; 365 } 366 }; 367 368 bool bit(int mask, int pos) { 369 return (mask >> pos) & 1; 370 } 371 372 vector<node> t; 373 374 void add(int x) { 375 int v = 0; 376 for (int i = 29; i >= 0; --i) { 377 int b = bit(x, i); 378 if (t[v].to[b] == -1) { 379 t[v].to[b] = sz(t); 380 t.pb(node()); 381 } 382 ++t[v].cnt; 383 v = t[v].to[b]; 384 } 385 ++t[v].cnt; 386 } 387 388 const int mod = 998244353; 389 390 void mul(int& a, int b) { 391 ll c = ll(a) * b; 392 if (c >= mod) { 393 c %= mod; 394 } 395 a = c; 396 } 397 398 int binpow(int a, int n) { 399 int ans = 1; 400 while (n) { 401 if (n & 1) { 402 mul(ans, a); 403 } 404 mul(a, a); 405 n >>= 1; 406 } 407 return ans; 408 } 409 410 void solve(int v, int k, ll& ans) { 411 if (t[v].to[0] != -1 && t[v].to[1] != -1) { 412 ll i = k + 1; 413 ans += (2 * (i / 2) + 1) * t[t[v].to[0]].cnt * t[t[v].to[1]].cnt; 414 ans += 2 * ((i + 1) / 2) * t[t[v].to[0]].cnt * t[t[v].to[1]].cnt; 415 } 416 if (t[v].to[0] == -1 && t[v].to[1] == -1) { 417 ll i = k + 1; 418 ans += i * t[v].cnt * t[v].cnt; 419 } 420 if (t[v].to[0] != -1) { 421 solve(t[v].to[0], k, ans); 422 } 423 if (t[v].to[1] != -1) { 424 solve(t[v].to[1], k + 1, ans); 425 } 426 } 427 428 int main() { 429 430 ios_base::sync_with_stdio(false); 431 cin.tie(0); 432 cout.tie(0); 433 434 int tt; 435 cin >> tt; 436 while (tt--) { 437 t.clear(); 438 t.pb(node()); 439 int n; 440 cin >> n; 441 for (int i = 0; i < n; ++i) { 442 int a; 443 cin >> a; 444 add(a); 445 } 446 ll x = 0; 447 solve(0, 0, x); 448 int ans = x % mod; 449 mul(ans, binpow(n, mod - 2)); 450 mul(ans, binpow(n, mod - 2)); 451 cout << ans << "\n"; 452 } 453 454 } 455 ``` 456 457 ### [1864F-Exotic Queries](https://mirror.codeforces.com/contest/1864/problem/F) 458 459 Idea : [ODT](/profile/ODT "Master ODT"), [AquaMoon](/profile/AquaMoon "International Master AquaMoon") 460 461 **Hint** 462 463 The final solution is irrelevant to Cartesian trees. 464 465 **Tutorial** 466 467 First, we consider only the sequence of elements to be manipulated. We claim that it is optimal to operate on the whole sequence so that the minimum elements are all decreased to $0$, and then solve the problem on the segments separated by the $0$s recursively. 468 469 A straightforward corollary of the claim is that two equal elements between which there are no smaller elements are handled in a single operation, so the final answer is $\ell$ (the number of elements to be manipulated) minus the number of such adjacent pairs. 470 471 Proof: Define $S(l, r)$ to be the answer for the segment $[l, r]$. Do induction on the length of the segment. If the first operation does not manipulate the whole segment, the segment will be separated into several independent parts by the first operation, for the non-inclusive operations cannot intersect, and the final answer, which is the sum of $S$ of the parts, will not be less than the initial answer according to the corollary, for some of the equal pairs are separated. 472 473 Now the original problem is converted into a data structure task. Consider all adjacent equal pairs $(l, r)$, and $m$ is the maximum element between $(l, r)$, $m < a_l$. $(l, r)$ decrease the answer if and only if $m \lt L \le a_l = a_r \le R$, which can be easily calculated with a segment tree and sweeping lines. 474 475 **solution** 476 477 ``` 478 #include <bits/stdc++.h> 479 480 #define all(a) (a).begin(), (a).end() 481 #define sz(a) (int)(a).size() 482 #define pb push_back 483 #define mp make_pair 484 485 using namespace std; 486 487 typedef long long ll; 488 typedef long double ld; 489 typedef pair<int, int> pii; 490 491 vector<int> sum; 492 int N; 493 494 void updSumTree(int pos) { 495 for (pos += N; pos; pos >>= 1) { 496 ++sum[pos]; 497 } 498 } 499 500 int getSumTree(int l, int r) { 501 int ans = 0; 502 for (l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r — 1) >> 1) { 503 if (l & 1) { 504 ans += sum[l]; 505 } 506 if (!(r & 1)) { 507 ans += sum[r]; 508 } 509 } 510 return ans; 511 } 512 513 vector<int> t; 514 int n; 515 516 void updTree(int pos, int val) { 517 for (pos += n; pos; pos >>= 1) { 518 t[pos] = max(t[pos], val); 519 } 520 } 521 522 int getTree(int l, int r) { 523 int ans = 0; 524 for (l += n, r += n; l <= r; l = (l + 1) >> 1, r = (r — 1) >> 1) { 525 if (l & 1) { 526 ans = max(ans, t[l]); 527 } 528 if (!(r & 1)) { 529 ans = max(ans, t[r]); 530 } 531 } 532 return ans; 533 } 534 535 const int nmax = 1e6 + 100; 536 537 vector<int> pos[nmax]; 538 int cnt[nmax]; 539 int distinct[nmax]; 540 541 struct query { 542 int l, r, id; 543 bool operator<(const query& other) const { 544 return l < other.l; 545 } 546 }; 547 548 int main() { 549 550 ios_base::sync_with_stdio(false); 551 cin.tie(0); 552 cout.tie(0); 553 554 int q; 555 cin >> n >> q; 556 vector<int> a(n); 557 for (int i = 0; i < n; ++i) { 558 cin >> a[i]; 559 } 560 561 t.assign(4 * n, 0); 562 563 for (int i = 0; i < n; ++i) { 564 pos[a[i]].pb(i); 565 } 566 567 vector<pii> pts; 568 for (int x = 1; x <= n; ++x) { 569 for (int i = 0; i + 1 < sz(pos[x]); ++i) { 570 int lf = pos[x][i], rg = pos[x][i + 1]; 571 ++lf, --rg; 572 if (lf > rg) { 573 continue; 574 } 575 int y = getTree(lf, rg); 576 //cout << x << " " << y << endl; 577 if (y == 0) { 578 continue; 579 } 580 pts.pb({n - y, x}); 581 } 582 for (int p : pos[x]) { 583 updTree(p, x); 584 } 585 } 586 587 cnt[0] = 0; 588 distinct[0] = 0; 589 for (int x = 1; x <= n; ++x) { 590 cnt[x] = cnt[x - 1] + sz(pos[x]); 591 distinct[x] = distinct[x - 1] + (!pos[x].empty()); 592 } 593 594 sort(all(pts)); 595 int ptr = 0; 596 597 vector<query> queries(q); 598 vector<int> ans(q); 599 for (int i = 0; i < q; ++i) { 600 int l, r; 601 cin >> l >> r; 602 queries[i] = {n - l, r, i}; 603 ans[i] = distinct[r] - distinct[l - 1]; 604 } 605 606 sort(all(queries)); 607 608 N = n + 1; 609 sum.assign(2 * N, 0); 610 611 for (int i = 0; i < q; ++i) { 612 while (ptr < sz(pts) && pts[ptr].first <= queries[i].l) { 613 updSumTree(pts[ptr].second); 614 ++ptr; 615 } 616 ans[queries[i].id] += getSumTree(0, queries[i].r); 617 } 618 619 for (int i = 0; i < q; ++i) { 620 cout << ans[i] << "\n"; 621 } 622 623 } 624 ``` 625 626 ### [1864G-Magic Square](https://mirror.codeforces.com/contest/1864/problem/G) 627 628 Idea : [AquaMoon](/profile/AquaMoon "International Master AquaMoon") 629 630 **Hint1** 631 632 Theorem 1: After a row shift, all numbers moved are in the correct column. 633 634 Proof 1: Suppose a number moved after a row shift is not in the correct column, if it is not in the correct row, it needs at least two more moves to its target position, otherwise it needs at least three more moves because the row cannot be shifted again. 635 636 Also, after a column shift, all numbers moved are in the correct row. 637 638 **Hint2** 639 640 Theorem 2: If both row shift and column shift are performed, two rows cannot have equal shift distance. 641 642 Proof 2: If row $i$ is shifted by $x$ and column $j$ is shifted by $y$, regardless of their order, then there is a number with offset $(y, x)$. If row $i_1$ and row $i_2$ are shifted by $x$ and column $j$ is shifted by $y$, regardless of their order, then there are two numbers with the same offset $(y, x)$ (if two number coincide, it was moved at least three times). 643 644 In the same way, if both row shift and column shift are performed, two columns cannot have equal shift distance. 645 646 If after a row shift, all numbers moved are in the correct column, we call such rows available. Similarly, if after a column shift, all numbers moved are in the correct row, we call such columns available. 647 648 **Hint3** 649 650 Theorem 3: If there is an available row and an available column at the same time, then there is no solution. 651 652 Proof 3: If row $i$ can be shifted by $x$ and column $j$ can be shifted by $y$, the number in $(i, j)$ has offset $(y, x)$. Assume that the number in $(i, j)$ is moved to $(i+y, j)$ and then to $(i+y, j+x)$. Row $i+y$ is shifted by $x$, no other row can be shifted by $x$. Consider the number in $(i,j+1)$, it needs to be shifted by $x$ in some row, so it must be moved to row $i+y$ before row $i+y$ shifts. Then the numbers in $(i, j)$ and $(i+1, j)$ have the same offset $(y, x)$. Similarly, if the number in $(i, j)$ is moved to $(i, j+x)$ and then to $(i+y, j+x)$, there is no solution. 653 654 **Tutorial** 655 656 We can use the following method to solve this problem: 657 658 For each row and each column, check if it is available. 659 660 If there are both available rows and available columns, there is no solution. 661 662 If no rows or columns are available, the matrix is already equal to the target one, or there is no solution. 663 664 If there are only available rows or available columns, their order doesn't matter, so if there $s$ choices, the answer should be multiplied by $s!$. Apply all available operations and check again. 665 666 Total complexity: $O(n^3)$ or $O(n^2)$ if maintaining row/column offsets in each row/column. 667 668 **solution** 669 670 ``` 671 #include <bits/stdc++.h> 672 673 #define all(a) (a).begin(), (a).end() 674 #define sz(a) (int)(a).size() 675 #define pb push_back 676 #define mp make_pair 677 678 using namespace std; 679 680 typedef long long ll; 681 typedef long double ld; 682 typedef pair<int, int> pii; 683 684 const int mod = 998244353; 685 const int nmax = 600; 686 687 int fact[nmax]; 688 689 int main() { 690 691 ios_base::sync_with_stdio(false); 692 cin.tie(0); 693 cout.tie(0); 694 695 fact[0] = 1; 696 for (int i = 1; i < nmax; ++i) { 697 fact[i] = ll(fact[i - 1]) * i % mod; 698 } 699 700 int tt; 701 cin >> tt; 702 703 while (tt--) { 704 int n; 705 cin >> n; 706 vector<vector<int> > a(n, vector<int>(n)); 707 set<int> seta; 708 for (int i = 0; i < n; ++i) { 709 for (int j = 0; j < n; ++j) { 710 cin >> a[i][j]; 711 seta.insert(a[i][j]); 712 } 713 } 714 assert(sz(seta) == n * n); 715 716 vector<vector<int> > b(n, vector<int>(n)); 717 set<int> setb; 718 for (int i = 0; i < n; ++i) { 719 for (int j = 0; j < n; ++j) { 720 cin >> b[i][j]; 721 setb.insert(b[i][j]); 722 } 723 } 724 assert(sz(setb) == n * n); 725 assert(seta == setb); 726 vector<int> vct; 727 for (int x : seta) { 728 vct.pb(x); 729 } 730 731 for (int i = 0; i < n; ++i) { 732 for (int j = 0; j < n; ++j) { 733 a[i][j] = lower_bound(all(vct), a[i][j]) - vct.begin(); 734 b[i][j] = lower_bound(all(vct), b[i][j]) - vct.begin(); 735 } 736 } 737 738 vector<pii> posa(n * n); 739 vector<pii> posb(n * n); 740 741 set<pii> off; 742 743 for (int i = 0; i < n; ++i) { 744 for (int j = 0; j < n; ++j) { 745 posa[a[i][j]] = {i, j}; 746 posb[b[i][j]] = {i, j}; 747 } 748 } 749 bool valid = true; 750 for (int x = 0; x < n * n; ++x) { 751 pii p = posa[x], q = posb[x]; 752 if (p.first != q.first && p.second != q.second) { 753 pii s = {(q.first - p.first + n) % n, (q.second - p.second + n) % n}; 754 if (off.count(s)) { 755 valid = false; 756 } else { 757 off.insert(s); 758 } 759 } 760 } 761 if (!valid) { 762 cout << "0\n"; 763 continue; 764 } 765 766 int cnt = 0; 767 ll ans = 1; 768 769 while (a != b) { 770 vector<pii> rows; 771 for (int i = 0; i < n; ++i) { 772 int shift = posb[a[i][0]].second; 773 bool ok = true; 774 for (int j = 0; j < n; ++j) { 775 int x = a[i][j]; 776 if (posb[x].second != (j + shift) % n) { 777 ok = false; 778 break; 779 } 780 } 781 if (ok && shift) { 782 rows.pb({i, shift}); 783 } 784 } 785 vector<pii> cols; 786 for (int j = 0; j < n; ++j) { 787 int shift = posb[a[0][j]].first; 788 bool ok = true; 789 for (int i = 0; i < n; ++i) { 790 int x = a[i][j]; 791 if (posb[x].first != (i + shift) % n) { 792 ok = false; 793 break; 794 } 795 } 796 if (ok && shift) { 797 cols.pb({j, shift}); 798 } 799 } 800 if (cols.empty() && rows.empty()) { 801 valid = false; 802 break; 803 } 804 if (!(cols.empty() ^ rows.empty())) { 805 valid = false; 806 break; 807 } 808 if (!rows.empty()) { 809 cnt += sz(rows); 810 ans *= fact[sz(rows)]; 811 ans %= mod; 812 for (pii p : rows) { 813 int i = p.first; 814 int shift = p.second; 815 vector<int> v = a[i]; 816 for (int j = 0; j < n; ++j) { 817 int x = v[j]; 818 a[i][(j + shift) % n] = x; 819 posa[x] = {i, (j + shift) % n}; 820 } 821 } 822 } else { 823 cnt += sz(cols); 824 ans *= fact[sz(cols)]; 825 ans %= mod; 826 for (pii p : cols) { 827 int j = p.first; 828 int shift = p.second; 829 vector<int> v; 830 for (int i = 0; i < n; ++i) { 831 v.pb(a[i][j]); 832 } 833 for (int i = 0; i < n; ++i) { 834 int x = v[i]; 835 a[(i + shift) % n][j] = x; 836 posa[x] = {(i + shift) % n, j}; 837 } 838 } 839 } 840 } 841 if (!valid) { 842 cout << "0\n"; 843 continue; 844 } 845 cout << ans << '\n'; 846 // cout << cnt << " " << ans << "\n"; 847 } 848 849 } 850 ``` 851 852 ### [1864H-Asterism Stream](https://mirror.codeforces.com/contest/1864/problem/H) 853 854 Idea : [WrongAnswerOnTest3](/profile/WrongAnswerOnTest3 "Expert WrongAnswerOnTest3") Solution: [Psychotic_D](/profile/Psychotic_D "International Master Psychotic_D"), [amenotiomoi](/profile/amenotiomoi "International Grandmaster amenotiomoi") 855 856 **Tutorial** 857 858 Here is a basic $\Theta(n)$ dp solution. 859 860 Before that let $k = \frac{1}{2}$. At the same time, because a special geometric sequence $f(x)=ak^{bx}$ will be frequently used next, it is defined as $\{a,b\}$. 861 862 Let $f(x)$ be the expected number of moves needed if we start with $x$. Obviously, there is the following formula: 863 864 $f(x)=\begin{cases}0&n\leqslant x\\k(f(x+1)+f(2x))+1&x \lt n\end{cases}$ 865 866 It's easy to see that for the interval $[n, 2n]$ value of $f(x)$ is $0$. 867 868 If for an interval $[2l,2r]$, it can already be represented by the sum of several ${a,b}$, then it can be represented by a small number of new $\{a,b\}$ for all $f(x)$, where $x\in[l,r]$ 869 870 First there is $f(r)=kf(r+1)+kf(2r)+1$. So, $r-1$ can be represented as $f(r-1)=k^2f(r+1)+ kf(2r-2)+k^2f(2r)+k+1$. 871 872 By analogy, one can get 873 874 $f(r-x)=k^{x+1}f(r+1)+\sum\limits_{i=0}^xk^{i+1}f(2r-2x+2i)+\sum\limits_{i=0}^xk^i$ 875 876 by substitution, it can be shown as 877 878 $f(x)=k^{r-x+1}f(r+1)+\sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)+\sum\limits_{i=0}^{r-x}k^i$ 879 880 Because $\{a,b\}$ of the interval where $f(r+1)$ is already known, the value of $f(r+1)$ can be calculated quickly. So, the first term of $f(x)$ can be represented as below: 881 882 $k^{r-x+1}f(r+1)=k^{r+1}f(r+1)·k^{-x}=\{k^{r+1}f(r+1),-1\}$ 883 884 Then the last term of $f(x)$, $\sum\limits_{i=0}^{r-x}k^i$ is sum of an ordinary geometric sequence. So, after applying the formula it can represented as $\{2,0\}+\{-k^r,-1\}$. 885 886 For the second term $\sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)$, it has been assumed that $f(2x+2i)$ is $\sum\{a,b\}$, so split it into the following form (the derivation process depends on $k^{2b+1}\neq1$): 887 888 $ \!\begin{aligned} \sum\limits_{i=0}^{r-x}k^{i+1}f(2x+2i)&=\sum\limits_{i=0}^{r-x}k^{i+1}\sum\limits_f\{a,b\}\\ &=\sum\limits_{i=0}^{r-x}k^{i+1}\sum\limits_fak^{b(2x+2i)}\\ &=\sum\limits_f\sum\limits_{i=0}^{r-x}k^{i+1}ak^{b(2x+2i)}\\ &=\sum\limits_f\sum\limits_{i=0}^{r-x}ak^{2bx+1}·k^{i+2bi}\\ &=\sum\limits_fak^{2bx+1}\sum\limits_{i=0}^{r-x}(k^{2b+1})^i\\ &=\sum\limits_fak^{2bx+1}\cdot\frac{k^{(2b+1)(r-x+1)}-1}{k^{2b+1}-1}\\ &=\sum\limits_f\frac{ak^{(2b+1)(n+1)+1}}{k^{2b+1}-1}\cdot k^{-x}+\frac{-ak}{k^{2b+1}-1}\cdot k^{2bx}\\ &=\sum\limits_f\{\frac{ak^{(2b+1)(n+1)+1}}{k^{2b+1}-1},-1\}+\{\frac{-ak}{k^{2b+1}-1},2b\} \end{aligned} $ 889 890 Because of the obvious combination law $\{a,b\}+\{c,b\}=\{a+c,b\}$, the number of its geometric series is linear with the number of recursions. 891 892 For $x\in[n,2n], f(x)=0$, which can be represented as $f(x)=\{0,0\}$, so this recursive rule can always be used, Until the $x\in[1,1]$ is obtained, to get the result. 893 894 The complexity varies depending on the implementation $\Theta(T\log^3n)$ or $\Theta(T\log^2n)$. 895 896 **solution** 897 898 ``` 899 #include <bits/stdc++.h> 900 using namespace std; 901 #pragma GCC optimize("Ofast", "inline", "-ffast-math") 902 #pragma GCC target("avx,sse2,sse3,sse4,mmx") 903 #define int long long 904 const int MOD = 998244353; 905 int n, k; 906 long long power(int x, int p) 907 { 908 if (p < 0) 909 return power(power(x, MOD - 2), -p); 910 int answer = 1; 911 x %= MOD; 912 while (p) 913 { 914 if (p & 1) 915 answer = answer * x % MOD; 916 x = x * x % MOD; 917 p >>= 1; 918 } 919 return answer; 920 } 921 void Delta() 922 { 923 cin >> n; 924 k = power(2, MOD - 2); 925 int l = n, r = max(1ll, (n - 1) * 2), n0 = 0, s; 926 vector<int> Q; 927 while (l > 1) 928 { 929 vector<int> P; 930 l = (l + 1) / 2; 931 r /= 2; 932 s = n0; 933 for (int i = 0, t = k - 1; i < (int)Q.size(); ++i) 934 { 935 s = (s + Q[i] * power(power(k, -(1ll << i)), r + 1)) % MOD; 936 t = t * t % MOD; 937 } 938 P.push_back(((power(k, r + 1) * s - power(k, r)) % MOD + MOD) % MOD); 939 for (int i = 0; i < (int)Q.size(); ++i) 940 { 941 P[0] += power(power(k, 1 - (1ll << (i + 1))) - 1, MOD - 2) * Q[i] % MOD * power(power(k, 1 - (1ll << (i + 1))), r + 1) % MOD * k % MOD; 942 P.push_back(((MOD - Q[i] * k % MOD * power(power(k, 1 - (1ll << (i + 1))) - 1, MOD - 2) % MOD) % MOD + MOD) % MOD); 943 } 944 P[0] += (MOD - n0) * power(k, r + 1) % MOD; 945 for (int &i : P) 946 i %= MOD; 947 Q = P; 948 n0 += 2; 949 } 950 s = n0; 951 for (int i = 0, t = k - 1; i < (int)Q.size(); ++i) 952 { 953 s = (s + Q[i] * power(power(k, -(1ll << i)), 1)) % MOD; 954 t = t * t % MOD; 955 } 956 cout << s << endl; 957 } 958 signed main() 959 { 960 ios_base::sync_with_stdio(0); 961 cin.tie(0); 962 cout.tie(0); 963 int T; 964 cin >> T; 965 while (T--) 966 Delta(); 967 } 968 ``` 969 970 ### [1864I-Future Dominators](https://mirror.codeforces.com/contest/1864/problem/I) 971 972 Idea : [Psychotic_D](/profile/Psychotic_D "International Master Psychotic_D"), [amenotiomoi](/profile/amenotiomoi "International Grandmaster amenotiomoi") 973 974 **Tutorial** 975 976 This problem is based on a method of online edge deletion and querying connectivity of a planar graph. 977 978 Firstly, if this vertex is not an articulation point, it will not cause any change in connectivity. Therefore, the algorithm needs to determine whether a certain vertex is an articulation point. 979 980 Thinking about using a data structure called union-find to keep track of the deleted points, we can identify a clear condition: if a vertex has two neighbors with the same union-find value among its $8$-connected neighbors, then it becomes an articulation point. This is easy to understand: 981 982  983 984 When the values in the union-find are the same, it means there's a loop forming, and this messes up how things are connected inside and outside the loop. But if all the values in the union-find are different, no loops will form, and we can find a way to connect these points to each other. 985 986 For points which are not articulation points, the greedy way to do it is to put the biggest number in the component of points that are already connected. This helps keep things organized and efficient. 987 988 Now, let's think about the case of articulation points. If we've already decided to put a $1$ in the connected group before the articulation point, it's pretty clear that, in order to get the largest overall value, we should put the $1$ in the smallest connected component. And the remaining connected components will then share the largest value. In other words, when we pick the largest number for one component, the largest numbers for the other components will decrease at the same time. 989 990 If we're sure that a particular component won't have the number $1$ placed in it, then the point we're looking at can only hold the value which is one more than the maximum value in the connected component formed by removing this point. It might sound a bit complicated, but I'll show you a picture to make it clearer. 991 992  993 994 In simpler words, the value we put in that point is fixed. It's just the right amount to make sure it matches the sum of all the values in the connected group above it, instead of picking the smallest group. To make this work, we have to keep track of where the smallest value is located inside that connected component. 995 996 The method we discussed is quite slow, around $O(n^3)$. Now, let's talk about how to make it much faster, around $O(n^2 log n)$. 997 998 Firstly, for every cell, we keep a pointer that points to the information about its connected component. So, whenever we update any cell, the entire connected component gets updated automatically. 999 1000 When dealing with articulation points, it's important to quickly update the pointer information. One effective way is to use a clever merging technique. This involves simultaneously performing a breadth-first search on multiple connected components. If only one connected component remains incomplete in the search, we immediately stop all calculations. 1001 1002 One of the things we need to do is to launch the BFS from the new connected components which arise after fixing a certain cell. In particular, we don't want to launch two parallel BFS which start in different cells but sooner or later are merged into one component. So among the $4$ side-neighbors of the cell being fixed, we need to segregate them based on the remaining connectivity, considering the removal of the current cell. To facilitate this segregation, we examine the 8 corner- or side-neighbors and analyze their DSU values. For instance, if all these DSU values are distinct from each other, it implies that the empty neighboring cells belong to a unified component. 1003 1004  1005 1006 Conversely, if certain DSU values occur multiple times, it signifies the existence of a planar cycle that becomes linked through the cell being fixed. Consequently, cells within and outside this cycle must be assigned to separate connected components. To manage this, we iterate through pairs of $8-$neighbors sharing the same DSU value and classify the $4-$neighbors into those situated within the cycle and those outside it. 1007 1008 During the pointer update process, we handle smaller connected components by updating their pointers in a straightforward manner. For larger connected components, we retain their original pointers and make necessary adjustments. It's easy to show that this approach updates pointers efficiently (each time a connected group is encountered in the search, its size at least doubles). This helps us achieve a time complexity of $O(n^2 log n)$. 1009 1010 Next, we also need to determine whether two cells are part of the same connected component. This is necessary for calculating the situation represented in the previous image. This step is quite simple because we ensured earlier that pointers of different connected components are always different. So, all we need to do is compare the pointer values to check if two cells belong to the same connected component. 1011 1012 For the connected components that share the largest value, there are several ways to handle them. One approach is to use the `*int` data type for the maximum value, so changing one value directly changes the shared value. Another method is to use a `vector` to store the pointers that share the value, and when updating, you iterate through this vector to update them. 1013 1014 It's easy to prove that the maximum shared values can only exist in a maximum of $O(1)$ components simultaneously. This is because they only arise when cutting an articulation point in a connected component where the value is not $1$, and these components cannot merge together. 1015 1016 So, the total time complexity will be $O(n^2logn)$. 1017 1018 **solution** 1019 1020 ``` 1021 #include<bits/stdc++.h> 1022 using namespace std; 1023 #pragma GCC optimize("Ofast","inline","-ffast-math") 1024 #pragma GCC target("avx,sse2,sse3,sse4,mmx") 1025 struct node { 1026 int mx,sz;bool bg; 1027 pair<int,int> mn; 1028 vector<node*> cp; 1029 void cln(){for(node* i:cp)i->cp.erase(find(i->cp.begin(),i->cp.end(),this));cp.clear();} 1030 void fresh() { 1031 if(!bg) return; 1032 bg=false;int sum=0;node* lt=nullptr; 1033 for(node* i:cp)if(i->bg){lt=i;sum++;} 1034 if(sum==1){lt->mx=lt->sz;lt->bg=false;lt->cln();} 1035 } 1036 ~node(){cln();} 1037 }; 1038 int prevAns; 1039 pair<int,int> fa[1002][1002]; 1040 pair<int,int> getfa(pair<int,int> x) { 1041 if(fa[x.first][x.second]==x) return x; 1042 return fa[x.first][x.second]=getfa(fa[x.first][x.second]); 1043 } 1044 void merge(pair<int,int> x,pair<int,int> y) { 1045 pair<int,int> t=getfa(x); 1046 fa[t.first][t.second]=getfa(y); 1047 } 1048 1049 int n,q; 1050 node* bk[1002][1002]; 1051 bool vis[1002][1002]; 1052 vector<pair<int,int>> dxy={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}},xy={{-1,0},{0,1},{1,0},{0,-1}}; 1053 void Delta() { 1054 cin >> n >> q; 1055 bk[1][1]=new node{n*n,n*n,false,{0,0},{}}; 1056 for(int i=0;i<=n+1;++i) 1057 for(int j=0;j<=n+1;++j) { 1058 fa[i][j]={i,j}; 1059 if(i==0||j==0||i==n+1||j==n+1) { 1060 fa[i][j]={0,0}; 1061 vis[i][j]=true; 1062 bk[i][j]=nullptr; 1063 } else { 1064 bk[i][j]=bk[1][1]; 1065 vis[i][j]=false; 1066 } 1067 } 1068 prevAns=0; 1069 while(q--) { 1070 int x,y,cnt=1;cin >> x >> y; 1071 x^=prevAns; 1072 y^=prevAns; 1073 pair<int,int> Q[8]; 1074 int P[4]={0,0,0,0}; 1075 for(int i=0;i<8;++i) 1076 Q[i]=getfa({x+dxy[i].first,y+dxy[i].second}); 1077 for(int i=0;i<8;++i) 1078 for(int j=1;j<8;++j) 1079 if(Q[i]==Q[(i+j)%8]) { 1080 cnt++; 1081 for(int k=(i+1)%8;k!=(i+j)%8;k=(k+1)%8) 1082 if(k%2==1) 1083 P[k/2]+=1ll<<cnt; 1084 break; 1085 } 1086 vis[x][y]=true; 1087 for(pair<int,int> i:dxy) 1088 if(vis[x+i.first][y+i.second]) 1089 merge({x,y},{x+i.first,y+i.second}); 1090 bk[x][y]->fresh(); 1091 if((P[0]&P[1]&P[2]&P[3])==max({P[0],P[1],P[2],P[3]})) { 1092 prevAns=bk[x][y]->mx; 1093 cout << prevAns << ' '; 1094 bk[x][y]->mx--;bk[x][y]->sz--; 1095 for(node* i:bk[x][y]->cp) i->mx--; 1096 if(bk[x][y]->sz==0) delete bk[x][y]; 1097 } else { 1098 vector<pair<int,int>> s[4]; 1099 queue<pair<int,int>> q[4]; 1100 pair<int,int> id[4]; 1101 int cnt,dc=0; 1102 { 1103 vector<int> R; 1104 for(int i=0;i<4;++i) R.push_back(P[i]); 1105 sort(R.begin(),R.end()); 1106 R.resize(unique(R.begin(),R.end())-R.begin()); 1107 cnt=R.size(); 1108 for(int i=0;i<4;++i) 1109 P[i]=lower_bound(R.begin(),R.end(),P[i])-R.begin(); 1110 } 1111 for(int i=0;i<cnt;++i) { 1112 for(int j=0;j<4;++j) 1113 if(P[j]==i&&!vis[x+xy[j].first][y+xy[j].second]) { 1114 id[i]={x+xy[j].first,y+xy[j].second}; 1115 if(!vis[id[i].first][id[i].second]) { 1116 q[i].push(id[i]); 1117 s[i].push_back(id[i]); 1118 vis[id[i].first][id[i].second]=true; 1119 dc++; 1120 } 1121 break; 1122 } 1123 } 1124 while(dc>1) 1125 for(int i=0;i<4;++i) 1126 if(q[i].size()!=0) { 1127 pair<int,int> t=q[i].front();q[i].pop(); 1128 for(int j=0;j<4;++j) { 1129 pair<int,int> p={t.first+xy[j].first,t.second+xy[j].second}; 1130 if(!vis[p.first][p.second]) { 1131 q[i].push(p);s[i].push_back(p); 1132 vis[p.first][p.second]=true; 1133 } 1134 } 1135 if(q[i].empty()) --dc; 1136 } 1137 vector<int> sm,bg;node* tp[4]; 1138 if(bk[x][y]->mx==bk[x][y]->sz) { 1139 if(dc==1) { 1140 for(int i=0;i<4;++i) 1141 if(!q[i].empty()) bg.push_back(i); 1142 else if(!s[i].empty()) sm.push_back(i); 1143 for(int i:sm) { 1144 tp[i]=new node{bk[x][y]->mx,(int)s[i].size(),false,{x,y},{}}; 1145 for(pair<int,int> j:s[i]) 1146 bk[j.first][j.second]=tp[i]; 1147 } 1148 for(int i:sm) { 1149 for(int j:sm) 1150 if(i!=j) tp[i]->cp.push_back(tp[j]); 1151 bk[x][y]->sz-=s[i].size(); 1152 } 1153 prevAns=bk[x][y]->sz; 1154 cout<< prevAns << ' '; 1155 bk[x][y]->sz--;bk[x][y]->mx=bk[x][y]->sz; 1156 } else { 1157 int mxz=0; 1158 for(int i=0;i<4;++i) 1159 if(!s[i].empty()) { 1160 sm.push_back(i); 1161 mxz=max(mxz,(int)s[i].size()); 1162 } 1163 prevAns=mxz+1; 1164 cout << prevAns << ' '; 1165 for(int i:sm) { 1166 tp[i]=new node{bk[x][y]->mx,(int)s[i].size(),(int)s[i].size()==mxz,{x,y},{}}; 1167 for(pair<int,int> j:s[i]) 1168 bk[j.first][j.second]=tp[i]; 1169 } 1170 for(int i:sm) 1171 for(int j:sm) 1172 if(i!=j) tp[i]->cp.push_back(tp[j]); 1173 delete bk[x][y]; 1174 } 1175 } else { 1176 vector<node*> ar;vector<int> lt,ult; 1177 if(dc==1) { 1178 int sult=1,ty=bk[x][y]->mx; 1179 pair<int,int> pmn=bk[x][y]->mn; 1180 bk[x][y]->mn={x,y};bk[x][y]->sz--; 1181 for(int i=0;i<4;++i) 1182 if(!s[i].empty()) { 1183 if(!q[i].empty()) { 1184 bg.push_back(i); 1185 tp[i]=bk[x][y]; 1186 } 1187 else { 1188 tp[i]=new node{bk[x][y]->mx,(int)s[i].size(),false,{x,y},{}}; 1189 sm.push_back(i); 1190 bk[x][y]->sz-=(int)s[i].size(); 1191 for(pair<int,int> j:s[i]) 1192 bk[j.first][j.second]=tp[i]; 1193 } 1194 } 1195 pair<int,int> tmp=pmn; 1196 for(pair<int,int> i:xy) { 1197 node* t=bk[i.first+tmp.first][i.second+tmp.second]; 1198 if(t!=nullptr&&pair<int,int>{i.first+tmp.first,i.second+tmp.second}!=pair<int,int>{x,y}) { 1199 ar.push_back(t); 1200 } 1201 } 1202 vector<node*> cp=bk[x][y]->cp; 1203 for(node* i:cp) i->cp.erase(find(i->cp.begin(),i->cp.end(),bk[x][y])); 1204 bk[x][y]->cp.clear(); 1205 for(int i=0;i<4;++i) { 1206 if(!s[i].empty()) { 1207 if(id[i]==tmp||find(ar.begin(),ar.end(),bk[id[i].first][id[i].second])!=ar.end()) { 1208 tp[i]->mn=pmn; 1209 lt.push_back(i); 1210 } else { 1211 ult.push_back(i); 1212 sult+=tp[i]->sz; 1213 } 1214 } 1215 } 1216 for(int i:ult) 1217 for(int j:ult) 1218 if(i!=j) tp[i]->cp.push_back(tp[j]); 1219 for(node* i:cp) { 1220 for(int j:lt) { 1221 i->cp.push_back(tp[j]); 1222 tp[j]->cp.push_back(i); 1223 } 1224 i->mx-=sult; 1225 } 1226 prevAns=ty-sult+1; 1227 cout << prevAns << ' '; 1228 for(int i:lt) { 1229 for(int j:lt) 1230 if(i!=j) tp[i]->cp.push_back(tp[j]); 1231 tp[i]->mx-=sult; 1232 } 1233 } else { 1234 pair<int,int> pmn=bk[x][y]->mn; 1235 int sult=1; 1236 for(int i=0;i<4;++i) 1237 if(!s[i].empty()) { 1238 tp[i]=new node{bk[x][y]->mx,(int)s[i].size(),false,{x,y},{}}; 1239 for(pair<int,int> j:s[i]) 1240 bk[j.first][j.second]=tp[i]; 1241 } 1242 pair<int,int> tmp=bk[x][y]->mn; 1243 for(pair<int,int> i:xy) { 1244 node* t=bk[i.first+tmp.first][i.second+tmp.second]; 1245 if(t!=nullptr&&pair<int,int>{i.first+tmp.first,i.second+tmp.second}!=pair<int,int>{x,y}) 1246 ar.push_back(t); 1247 } 1248 for(int i=0;i<4;++i) 1249 if(!s[i].empty()) { 1250 if(id[i]==tmp||find(ar.begin(),ar.end(),bk[id[i].first][id[i].second])!=ar.end()) { 1251 tp[i]->mn=pmn; 1252 lt.push_back(i); 1253 } else { 1254 ult.push_back(i); 1255 sult+=(int)s[i].size(); 1256 } 1257 } 1258 for(int i:ult) 1259 for(int j:ult) 1260 if(i!=j) tp[i]->cp.push_back(tp[j]); 1261 for(node* i:bk[x][y]->cp) { 1262 for(int j:lt) { 1263 i->cp.push_back(tp[j]); 1264 tp[j]->cp.push_back(i); 1265 } 1266 i->mx-=sult; 1267 } 1268 for(int i:lt) { 1269 for(int j:lt) 1270 if(i!=j) tp[i]->cp.push_back(tp[j]); 1271 tp[i]->mx-=sult; 1272 } 1273 prevAns=bk[x][y]->mx-sult+1; 1274 cout << prevAns << ' '; 1275 delete bk[x][y]; 1276 } 1277 } 1278 for(int i=0;i<4;++i) 1279 for(pair<int,int> j:s[i]) 1280 vis[j.first][j.second]=false; 1281 } 1282 bk[x][y]=nullptr; 1283 } 1284 set<node*> _; 1285 for(int i=1;i<=n;++i) 1286 for(int j=1;j<=n;++j) 1287 _.insert(bk[i][j]); 1288 for(node* i:_) 1289 if(i!=nullptr) delete i; 1290 cout << endl; 1291 } 1292 signed main() { 1293 ios_base::sync_with_stdio(0); 1294 cin.tie(0);cout.tie(0); 1295 int T;cin >> T; 1296 while(T--) Delta(); 1297 } 1298 ``` 1299 1300 Feel free to ask if you have any questions! (*╹▽╹*)