codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 &mdash; 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 &mdash; 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 ![Editoral_img1.png](/predownloaded/11/d0/11d08c615fc0d4be57b9a9f2303212362912e5df.png "Editoral_img1.png")
    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 ![Editorial_img2.png](/predownloaded/92/07/9207e347d75754835ff7388cb2f1436c93c3977f.png "Editorial_img2.png")
    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 ![Editorial_img3.jpg](/predownloaded/fb/2a/fb2aa8aa0b48181b77a95e984f33158c77f9e63b.jpg "Editorial_img3.jpg")
   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! (*╹▽╹*)