codeforces-scrape

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

2268.md (46489B)


      1 Source: https://codeforces.com/blog/entry/157140
      2 
      3 ### ⭐ **Hope you enjoyed the problems!** ⭐
      4 
      5 [2269A - SauSaGe Bank](/contest/2269/problem/A "Codeforces Round 1124 (Div. 2)")
      6 
      7 **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari")  
      8  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari")
      9 
     10 **Hints**
     11 
     12 **Hint 1**
     13 
     14 If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$.
     15 
     16 **Hint 2**
     17 
     18 For fixed $a+b$, is $2^a+2^b$ larger when $a,b$ are close together, or when one is as large as possible?
     19 
     20 **Solution**
     21 
     22 If Hamed waits $d$ days before withdrawing, the amount of money in his card increases by exactly $2^d$.
     23 
     24 Therefore the problem becomes: Split $n$ into exactly $k$ positive integers $a_1,\dots,a_k$, and maximize
     25 
     26 $2^{a_1}+2^{a_2}+...+2^{a_k}$
     27 
     28 For fixed $a+b$, $2^a+2^b$ is larger when one of them is as large as possible.
     29 
     30 **Proof**
     31 
     32 Suppose two segment lengths are $a\le b$, with $a \gt 1$. Move one day from the smaller segment to the larger one:
     33 
     34 $(a,b) \to (a-1,b+1)$
     35 
     36 Compare the contributions:
     37 
     38 $2^{a-1} + 2^{b+1} - (2^a + 2^b) = 2^b - 2^{a-1} \gt 0$
     39 
     40 So this change always increases the answer.
     41 
     42 Hence, in an optimal solution, we cannot have two segments with length greater than $1$. We keep transferring days from smaller segments to the largest one until all but one segment have length $1$.
     43 
     44 Thus the optimal lengths are
     45 
     46 $n-k+1,\underbrace{1,1,\ldots,1}_{k-1\text{ times}}$
     47 
     48 So the maximum amount is $2^{n-k+1}+2(k-1)$
     49 
     50 **Code**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54 using namespace std;
     55 int main() {
     56     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
     57     int tc;
     58     cin >> tc;
     59     while(tc--) {
     60         int n, k;
     61         cin >> n >> k;
     62         cout << (1<<(n-k+1)) + 2*(k-1) << '\n';
     63     }
     64     return 0;
     65 }
     66 ```
     67 
     68 ---
     69 
     70 [2269B - KiaKio and Squared Numbers](/contest/2269/problem/B "Codeforces Round 1124 (Div. 2)")
     71 
     72 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel")  
     73  **Preparation:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel")
     74 
     75 **Hints**
     76 
     77 **Hint 1**
     78 
     79 What is the maximum possible value of (f(x)), where (f(x)) is the sum of the squares of the decimal digits of (x)?
     80 
     81 Notice that after just one operation, every value becomes at most (729).
     82 
     83 **Hint 2**
     84 
     85 Since all values eventually become small, what happens if we repeatedly apply the operation?
     86 
     87 Try to detect the cycles of the function (f). Can two numbers that enter the same cycle still behave differently?
     88 
     89 **Solution**
     90 
     91 **Fact**
     92 
     93 The only cycles of the function $f(x)$ are
     94 
     95 $ 1 \to 1 $
     96 
     97 and
     98 
     99 $ 4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4. $
    100 
    101 Every positive integer eventually reaches exactly one of these two cycles.
    102 
    103 **Solution**
    104 
    105 For each initial value $a_i$, we simulate the process until it reaches one of the two cycles.
    106 
    107 If it reaches $1$, we assign it the signature $8$.
    108 
    109 Otherwise, suppose it takes $s$ operations to reach the element at position $k$ of the 8-cycle, where the positions are numbered from $0$ to $7$.
    110 
    111 Its position after $t$ operations is
    112 
    113 $ (k+t-s) \bmod 8. $
    114 
    115 Therefore, two numbers entering the 8-cycle will eventually have identical values at every step if and only if:
    116 
    117 $ (k_1-s_1) \equiv (k_2-s_2) \pmod 8. $
    118 
    119 We use this value as the signature of each number.
    120 
    121 Thus, two initial values are in tune if and only if their signatures are equal.
    122 
    123 Let $cnt[x]$ be the number of elements with signature $x$. The answer is
    124 
    125 $ \boxed{ \sum_{x=0}^{8} \frac{cnt[x](cnt[x]-1)}{2} } $
    126 
    127 Since every number reaches a cycle after a constant number of operations, we can calculate all signatures and count the pairs in $\mathcal{O}(n)$ time per test case.
    128 
    129 **Code**
    130 
    131 ```
    132 #include <bits/stdc++.h>
    133 
    134 using namespace std;
    135 
    136 typedef long long ll;
    137 typedef long double ld;
    138 typedef pair<int,int> pii;
    139 typedef pair<ll,ll> pll;
    140 
    141 #define F first
    142 #define S second
    143 #define endl '\n'
    144 #define Mp make_pair
    145 #define pb push_back
    146 #define pf push_front
    147 #define size(x) (ll)x.size()
    148 #define all(x) x.begin(), x.end()
    149 #define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
    150 
    151 const int N = 2e5 + 100, lg = 18;
    152 const ll Mod = 1e9 + 7;
    153 const ll inf = 1e18 + 10;
    154 
    155 // The unique non-trivial cycle of the "sum of squared decimal digits" map.
    156 // 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...
    157 const ll CYC[8] = {4, 16, 37, 58, 89, 145, 42, 20};
    158 
    159 int t, n;
    160 ll cnt[9];
    161 
    162 // Signature of a lighthouse:
    163 //   8       -> "calm": the value reaches 1 and stays there forever.
    164 //   0..7    -> "restless": the phase of the lighthouse on the 8-cycle.
    165 // Two lighthouses are in tune iff their signatures are equal.
    166 int sig(ll x) {
    167     ll s = 0;
    168     while (true) {
    169         if (x == 1) return 8;
    170         for (int k = 0; k < 8; k++)
    171             if (x == CYC[k]) return (int)(((k - s) % 8 + 8) % 8);
    172         ll y = 0;
    173         while (x > 0) { ll r = x % 10; y += r * r; x /= 10; }
    174         x = y;
    175         s++;
    176     }
    177 }
    178 
    179 void work() {
    180     cin >> n;
    181 
    182     for (int i = 0; i <= 8; i++) cnt[i] = 0;
    183 
    184     for (int i = 1; i <= n; i++) {
    185         ll a; cin >> a;
    186         cnt[sig(a)] ++;
    187     }
    188 
    189     ll ans = 0;
    190     for (int i = 0; i <= 8; i++) ans += cnt[i] * (cnt[i] - 1) / 2;
    191 
    192     cout << ans << endl;
    193 }
    194 
    195 void reset_work() {
    196     return;
    197 }
    198 
    199 int main() {
    200     ios_base::sync_with_stdio(false), cin.tie(0);
    201 
    202     cin >> t;
    203     while (t --) {
    204         work();
    205         reset_work();
    206     }
    207 
    208     return 0;
    209 }
    210 ```
    211 
    212 ---
    213 
    214 [2269C - K Is Important](/contest/2269/problem/C "Codeforces Round 1124 (Div. 2)") / [2268A - K Is Important](/contest/2268/problem/A "Codeforces Round 1124 (Div. 1)")
    215 
    216 **Idea:** [eren__](/profile/eren__ "Grandmaster eren__")  
    217  **Preparation:** [eren__](/profile/eren__ "Grandmaster eren__")
    218 
    219 **Hints**
    220 
    221 **Hint 1**
    222 
    223 Consider the special case where $2k = n$. Which elements are competing against each other to be deleted?
    224 
    225 **Hint 2**
    226 
    227 You can prove that for a specific index $i$, we are forced to delete exactly one element from the symmetric pair $(a_i, a_{n-i+1})$. Therefore, to maximize the sum, we should greedily take $\max(a_i, a_{n-i+1})$.
    228 
    229 **Solution**
    230 
    231 We can analyze the problem by splitting it into two cases based on the relationship between $2k$ and $n$:
    232 
    233 **Case 1: $2k \le n$** The elements in the middle, where $k \le i \le n - k + 1$, are inevitably going to be deleted. No matter what sequence of operations we choose, these elements will eventually land on the $k$-th position from either the left or the right side. Thus, we unconditionally add all of them to our total sum.
    234 
    235 After removing the middle section, we are left with a prefix of length $k-1$ and a suffix of length $k-1$.
    236 
    237 **Proof of the pairing relation:** Notice that when the remaining array shrinks to exactly length $k + i - 1$ (for $1 \le i \le k - 1$), the $k$-th element from the left and the $k$-th element from the right correspond exactly to the original elements $a_{n-i+1}$ and $a_i$ (or what remains of their relative positions). At this specific length, the operation forces us to delete exactly one of them.
    238 
    239 Therefore, for each $1 \le i \le k - 1$, we must choose exactly one element from the pair $(a_i, a_{n-i+1})$. To maximize our score, we greedily add $\max(a_i, a_{n-i+1})$ to our answer.
    240 
    241 **Case 2: $2k \gt n$** This case is very similar, but the roles are inverted. The elements in the middle, where $n - k + 2 \le i \le k - 1$, are completely fixed and safe. The total length of the array will drop below $k$ before these elements can ever reach the $k$-th position from either boundary. Thus, they can *never* be deleted.
    242 
    243 For the remaining valid elements on the two boundaries, the exact same symmetric relationship holds. We form pairs from the two ends: $(a_i, a_{n-i+1})$ for $1 \le i \le n - k + 1$. Just like in the first case, we can delete exactly one element from each pair, so we greedily add $\max(a_i, a_{n-i+1})$ to our sum.
    244 
    245 Using two pointers (`l` and `r`) allows us to implement both cases cleanly in $\mathcal{O}(n)$.
    246 
    247 **Code**
    248 
    249 ```
    250 #include <bits/stdc++.h> 
    251 #define pb push_back 
    252 #define F first 
    253 #define S second 
    254 #define all(a) a.begin(),a.end() 
    255 #define sz(a) (int)a.size() 
    256 #define pii pair<ll,ll>
    257 #define ll long long
    258 #define ld long double
    259 #define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
    260 #define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
    261 using namespace std ;
    262 const int maxn = 5e5 + 10  ;
    263 int a[maxn] ;
    264 signed main(){
    265   ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    266   int t ;cin >> t ; 
    267   while(t--){
    268     int n , k ; cin >> n  >> k; 
    269     for(int i = 1 ;i <= n ; i++){
    270        cin >> a[i] ; 
    271     }
    272     ll sum = 0 ;
    273     vector <int> vec;   
    274     for(int i = 1 ; i <= n ; i++){
    275       if(i >= k && i <= n-k+1){
    276         sum += a[i] ;
    277         continue ; 
    278       } 
    279       vec.pb(a[i]) ; 
    280     }
    281     int t2 = max(0 , sz(vec)- (k-1)) ;
    282     int l = 0 , r= sz(vec)-1 ;
    283     while(t2--){
    284       sum += max(vec[l] , vec[r]) ;
    285       l++;
    286       r--;  
    287     }
    288     cout << sum << "\n" ;
    289   }
    290 }
    291 ```
    292 
    293 ---
    294 
    295 [2269D - What a SauSaGe! It's All Meat](/contest/2269/problem/D "Codeforces Round 1124 (Div. 2)") / [2268B - What a SauSaGe! It's All Meat](/contest/2268/problem/B "Codeforces Round 1124 (Div. 1)")
    296 
    297 **Idea:** [_R00T](/profile/_R00T "Master _R00T")  
    298  **Preparation:** [_R00T](/profile/_R00T "Master _R00T")
    299 
    300 **Hints**
    301 
    302 **Hint 1**
    303 
    304 Write all possible values of $3k$ in binary. What property of each $a_i$ is preserved after every operation?
    305 
    306 **Hint 2**
    307 
    308 Show that instead of two adjacent elements, we can apply the same XOR mask to any pair $a_i,a_j$.
    309 
    310 **Hint 3**
    311 
    312 By combining several operations, we can XOR two chosen elements by any four-bit number with an even number of set bits.
    313 
    314 **Hint 4**
    315 
    316 An element with an odd number of set bits can never become All-Meat. To prove that every other element can become All-Meat, consider these two cases separately: - There is an element with odd popcount. - All elements have even popcount.
    317 
    318 **Solution**
    319 
    320 The possible XOR masks in one operation are:
    321 
    322 $ 3,6,9,12,15. $
    323 
    324 Their binary representations are:
    325 
    326 $ 0011,\ 0110,\ 1001,\ 1100,\ 1111. $
    327 
    328 All these masks have an even number of set bits. XORing a number with such a mask flips an even number of its bits, so the parity of its popcount does not change.
    329 
    330 The All-Meat values smaller than $16$ are:
    331 
    332 $ 0,3,6,9,12,15, $
    333 
    334 or in binary:
    335 
    336 $ 0000,\ 0011,\ 0110,\ 1001,\ 1100,\ 1111. $
    337 
    338 They all have even popcount. Therefore, an element with odd popcount can never become All-Meat. This gives us the following upper bound:
    339 
    340 $ \text{answer}\leq \#\{i\mid \operatorname{popcount}(a_i)\text{ is even}\}. $
    341 
    342 Now we prove that this upper bound can always be achieved.
    343 
    344 First, we can apply the same mask to any two elements, not necessarily adjacent ones. Suppose we want to apply a mask to $a_i$ and $a_j$, where $i \lt j$. Apply it to every adjacent pair:
    345 
    346 $ (i,i+1),(i+1,i+2),\ldots,(j-1,j). $
    347 
    348 Every element strictly between $i$ and $j$ is XORed twice, so it remains unchanged. Only $a_i$ and $a_j$ are XORed once.
    349 
    350 We can also combine multiple operations on the same pair. The set of all four-bit values with even popcount is:
    351 
    352 $ E=\{0,3,5,6,9,10,12,15\}. $
    353 
    354 All of them are already valid masks except $5$ and $10$, and:
    355 
    356 $ 5=3\oplus6,\qquad 10=3\oplus9. $
    357 
    358 Thus, we can XOR any two chosen elements by any mask with even popcount.
    359 
    360 Equivalently, if we write the array as an $n\times4$ grid of bits, we may choose any two rows and any two columns and flip the four corner bits.
    361 
    362 We now consider two cases.
    363 
    364 **Case 1: There is an element with odd popcount.**
    365 
    366 Choose one such element as a buffer.
    367 
    368 For every element $a_i$ with even popcount, XOR both $a_i$ and the buffer by $a_i$. This is possible because $a_i$ itself has even popcount.
    369 
    370 After this operation:
    371 
    372 $ a_i\oplus a_i=0, $
    373 
    374 so $a_i$ becomes All-Meat. The buffer still has odd popcount because we only XOR it with even-popcount masks.
    375 
    376 Therefore, every element with even popcount becomes All-Meat, while the elements with odd popcount cannot contribute to the answer anyway.
    377 
    378 **Case 2: All elements have even popcount.**
    379 
    380 Use $a_1$ as a buffer. For every $2\leq i\leq n$, XOR $a_1$ and $a_i$ by $a_i$. This makes every $a_i$ for $i\geq2$ equal to zero.
    381 
    382 After these operations, the array has the form:
    383 
    384 $ [x,0,0,\ldots,0], $
    385 
    386 where:
    387 
    388 $ x=a_1\oplus a_2\oplus\cdots\oplus a_n. $
    389 
    390 Since all original elements have even popcount, $x$ also has even popcount. If $x$ is one of:
    391 
    392 $ 0,3,6,9,12,15, $
    393 
    394 then every element is already All-Meat.
    395 
    396 The only remaining possibilities are $x=5$ and $x=10$. In both cases, apply XOR with $3$ to the first two elements:
    397 
    398 $ (5,0)\longrightarrow(6,3), $ $ (10,0)\longrightarrow(9,3). $
    399 
    400 Again, every element becomes All-Meat.
    401 
    402 Therefore, the upper bound is always achievable, and the answer is exactly:
    403 
    404 $ \boxed{\#\{i\mid \operatorname{popcount}(a_i)\text{ is even}\}}. $
    405 
    406 For each update, we only need to remove the contribution of the old value and add the contribution of the new value.
    407 
    408 The initial array is processed in $\mathcal{O}(n)$, and every update is processed in $\mathcal{O}(1)$. Therefore, the total time complexity is $\mathcal{O}(n+q)$.
    409 
    410 **Code**
    411 
    412 ```
    413 #include <bits/stdc++.h>
    414 using namespace std;
    415 
    416 inline bool good(int x) {
    417     return __builtin_popcount(x) % 2 == 0;
    418 }
    419 
    420 int32_t main() {
    421     cin.tie(0);
    422     cout.tie(0);
    423     ios_base::sync_with_stdio(0);
    424 
    425     int tc;
    426     cin >> tc;
    427 
    428     while (tc--) {
    429         int n, q;
    430         cin >> n >> q;
    431 
    432         vector<int> a(n);
    433         int answer = 0;
    434 
    435         for (int &x : a) {
    436             cin >> x;
    437             answer += good(x);
    438         }
    439 
    440         cout << answer;
    441 
    442         while (q--) {
    443             int p, x;
    444             cin >> p >> x;
    445             --p;
    446 
    447             answer -= good(a[p]);
    448             a[p] = x;
    449             answer += good(a[p]);
    450 
    451             cout << ' ' << answer;
    452         }
    453 
    454         cout << '\n';
    455     }
    456 
    457     return 0;
    458 }
    459 ```
    460 
    461 ---
    462 
    463 [2269E - KiaKio and Energy Intervals](/contest/2269/problem/E "Codeforces Round 1124 (Div. 2)") / [2268C - KiaKio and Energy Intervals](/contest/2268/problem/C "Codeforces Round 1124 (Div. 1)")
    464 
    465 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel")  
    466  **Preparation:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel")
    467 
    468 **Hints**
    469 
    470 **Hint 1**
    471 
    472 Let:
    473 
    474 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $
    475 
    476 If $m=\max(a_l,a_{l+1},\ldots,a_r)$, show that the value of the interval is:
    477 
    478 $ (p_{l-1}\oplus p_r)\mathbin{\&}m. $
    479 
    480 **Hint 2**
    481 
    482 Build the maximum Cartesian tree of the original array.
    483 
    484 What is the relation between $\operatorname{LCA}(l,r)$ and the maximum element of $a_l,a_{l+1},\ldots,a_r$?
    485 
    486 **Hint 3**
    487 
    488 Construct the answer greedily from the highest bit to the lowest bit.
    489 
    490 For a candidate mask $M$, we only need to determine whether there exists an interval whose value contains every bit of $M$.
    491 
    492 **Hint 4**
    493 
    494 For a fixed candidate $M$, define:
    495 
    496 $ b_i=a_i\mathbin{\&}M $
    497 
    498 and let $s_i$ be the prefix XOR of $b$.
    499 
    500 An interval represented by a Cartesian-tree vertex $v$ is valid for $M$ if:
    501 
    502 $ (a_v\mathbin{\&}M)=M $
    503 
    504 and:
    505 
    506 $ s_{l-1}\oplus s_r=M. $
    507 
    508 **Hint 5**
    509 
    510 Suppose the subtree of $v$ represents the segment $[L,R]$.
    511 
    512 For an interval whose Cartesian-tree LCA is $v$, its two prefix endpoints satisfy:
    513 
    514 $ l-1\in[L-1,v-1],\qquad r\in[v,R]. $
    515 
    516 Be careful with the pair $(v-1,v)$: it represents the forbidden one-element interval $[v,v]$.
    517 
    518 **Hint 6**
    519 
    520 Process the smaller child first, remove its prefix XORs from the frequency array, and then process the larger child.
    521 
    522 Keep the larger side in the frequency array, iterate over the smaller side, and search for the required complementary prefix XOR.
    523 
    524 **Solution**
    525 
    526 Define the prefix XORs of the original array as:
    527 
    528 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $
    529 
    530 Suppose we choose an interval $[l,r]$, and let:
    531 
    532 $ m=\max(a_l,a_{l+1},\ldots,a_r). $
    533 
    534 Bitwise AND distributes over XOR, so:
    535 
    536 $ \begin{aligned} &(a_l\mathbin{\&}m)\oplus (a_{l+1}\mathbin{\&}m)\oplus\cdots\oplus (a_r\mathbin{\&}m)\\ &= (a_l\oplus a_{l+1}\oplus\cdots\oplus a_r) \mathbin{\&}m\\ &= (p_{l-1}\oplus p_r)\mathbin{\&}m. \end{aligned} $
    537 
    538 Therefore, the answer depends only on the XOR of two prefix endpoints and the maximum of the interval.
    539 
    540 ### Cartesian tree
    541 
    542 Build the maximum Cartesian tree of the original array $a$. Ties may be handled in any consistent way.
    543 
    544 This tree has two useful properties:
    545 
    546 * The subtree of every vertex $v$ corresponds to a continuous segment $[L_v,R_v]$.
    547 * For every interval $[l,r]$:
    548 
    549 $ a_{\operatorname{LCA}(l,r)} = \max(a_l,a_{l+1},\ldots,a_r). $
    550 
    551 Thus, if $v=\operatorname{LCA}(l,r)$, the value of the interval is:
    552 
    553 $ (p_{l-1}\oplus p_r)\mathbin{\&}a_v. $
    554 
    555 ### Constructing the answer bit by bit
    556 
    557 Suppose some higher bits of the answer have already been fixed, and we want to test a candidate mask $M$.
    558 
    559 The candidate is feasible if there exists an interval whose value contains every bit of $M$.
    560 
    561 For this check, define:
    562 
    563 $ b_i=a_i\mathbin{\&}M $
    564 
    565 and its prefix XORs:
    566 
    567 $ s_0=0,\qquad s_i=b_1\oplus b_2\oplus\cdots\oplus b_i. $
    568 
    569 Equivalently:
    570 
    571 $ s_i=p_i\mathbin{\&}M. $
    572 
    573 For an interval whose Cartesian-tree LCA is $v$, all bits of $M$ occur in its value if and only if:
    574 
    575 $ (a_v\mathbin{\&}M)=M $
    576 
    577 and:
    578 
    579 $ s_{l-1}\oplus s_r=M. $
    580 
    581 The second condition can be rewritten as:
    582 
    583 $ s_r=s_{l-1}\oplus M. $
    584 
    585 Therefore, after fixing one endpoint, we only need a frequency array to determine whether the required other endpoint exists.
    586 
    587 Notice that the Cartesian tree is always built from the original values. Only the prefix XORs are masked during a feasibility check.
    588 
    589 ### Processing one Cartesian-tree vertex
    590 
    591 Suppose the subtree of $v$ corresponds to $[L,R]$.
    592 
    593 Every interval whose LCA is exactly $v$ can be represented by two prefix endpoints:
    594 
    595 $ x=l-1\in[L-1,v-1], $ $ y=r\in[v,R]. $
    596 
    597 We need to find a pair satisfying:
    598 
    599 $ s_x\oplus s_y=M. $
    600 
    601 There is one important exception. The pair:
    602 
    603 $ (x,y)=(v-1,v) $
    604 
    605 represents the interval $[v,v]$, which is forbidden because the statement requires $l \lt r$.
    606 
    607 Moreover, whenever $a_v & M=M$, this pair automatically satisfies:
    608 
    609 $ s_{v-1}\oplus s_v=a_v\mathbin{\&}M=M. $
    610 
    611 So failing to exclude this exact pair would produce a false positive at every suitable vertex.
    612 
    613 ### Small-to-large traversal
    614 
    615 For every processed subtree $[L,R]$, we maintain the following invariant:
    616 
    617 > The frequency array contains $s_L,s_{L+1},\ldots,s_R$.
    618 
    619 At a vertex $v$:
    620 
    621 1. Recursively check both child subtrees.
    622 2. Keep the prefix XORs of the larger child in the frequency array.
    623 3. Iterate over the endpoints belonging to the smaller side.
    624 4. For every value $s_x$, check whether $s_x\oplus M$ exists on the other side.
    625 5. Merge the smaller side into the frequency array.
    626 
    627 The boundary prefix $s_{L-1}$ is inserted temporarily when needed.
    628 
    629 The pair $(v-1,v)$ is excluded by checking one boundary endpoint before inserting the other one. Since the frequency array stores counts rather than only presence, equal prefix XOR values at different indices are still handled correctly.
    630 
    631 Whenever an index is scanned as part of the smaller side, the size of the subtree containing it at least doubles before it can be scanned again. Hence, every index is scanned at most $\mathcal{O}(\log n)$ times.
    632 
    633 One feasibility check takes:
    634 
    635 $ \mathcal{O}(n\log n). $
    636 
    637 There are $18$ bits, so the total time complexity is:
    638 
    639 $ \mathcal{O}(18n\log n). $
    640 
    641 The memory complexity is:
    642 
    643 $ \mathcal{O}(n+2^{18}). $
    644 
    645 The implementation below uses an explicit stack because a Cartesian tree can have depth $n$ for a sorted array.
    646 
    647 **Code**
    648 
    649 ```
    650 #include <bits/stdc++.h>
    651  
    652 using namespace std;
    653  
    654 typedef long long ll;
    655 typedef long double ld;
    656 typedef pair<int,int> pii;
    657 typedef pair<ll,ll> pll;
    658  
    659 #define F first
    660 #define S second
    661 #define endl '\n'
    662 #define Mp make_pair
    663 #define pb push_back
    664 #define pf push_front
    665 #define size(x) (ll)x.size()
    666 #define all(x) x.begin(), x.end()
    667  
    668 const int N = 2e5 + 100, lg = 18;
    669 const ll Mod = 1e9 + 7;
    670 const ll inf = 1e18 + 10;
    671  
    672 ll MOD(ll a, ll mod=Mod) {
    673     a%=mod; (a<0)&&(a+=mod); return a;
    674 }
    675 ll poww(ll a, ll b, ll mod=Mod) {
    676     ll res = 1;
    677     while(b > 0) {
    678         if(b%2 == 1) res = MOD(res * a, mod);
    679         b /= 2;
    680         a = MOD(a * a, mod);
    681     }
    682     return res;
    683 }
    684  
    685 int t, n, a[N], par[lg][N], pref[N], cnt[N * 2], answ = 0, maxi = 0;
    686  
    687 int getmx(int l, int r) {
    688     int res = l;
    689     for(int i=lg-1; i>=0; i--) {
    690         if(l + (1<<i) - 1 <= r) {
    691             res = (a[par[i][l]] > a[res] ? par[i][l] : res);
    692             l += (1<<i);
    693         }
    694     }
    695     return res;
    696 }
    697  
    698 void divide(int l, int r) {
    699     if(l > r) return;
    700     if(l == r) {
    701         cnt[pref[l]] ++;
    702         return;
    703     }
    704     if(l == r-1) {
    705         cnt[pref[l]] ++;
    706         cnt[pref[r]] ++;
    707         if((max(a[l], a[r]) & answ) == answ) {
    708             maxi = max(maxi, pref[l-1] ^ pref[r]);
    709         }
    710         return;
    711     }
    712  
    713     int mid = getmx(l, r);
    714  
    715     if(r-mid > mid-l) {
    716         divide(l, mid-1);
    717         for(int i=l; i<mid; i++) cnt[pref[i]] --;
    718         divide(mid+1, r);
    719 
    720         for(int i=mid-1; i>=l-1; i--) {
    721             if(cnt[(answ ^ pref[i])] > 0 && (a[mid]&answ) == answ) maxi = answ;
    722             if (i == mid-1) cnt[pref[mid]] ++;
    723         }
    724         for(int i=mid-1; i>=l; i--) cnt[pref[i]] ++;
    725     } else {
    726         divide(mid+1, r);
    727         for(int i=mid+1; i<=r; i++) cnt[pref[i]] --;
    728         divide(l, mid-1);
    729  
    730         cnt[pref[mid-1]] --;
    731         cnt[pref[l-1]] ++;
    732         for(int i=mid; i<=r; i++) {
    733             if(cnt[(answ ^ pref[i])] > 0  && (a[mid]&answ) == answ) maxi = answ;
    734             if(i == mid) cnt[pref[mid-1]] ++;
    735         }
    736         cnt[pref[l-1]] --;
    737  
    738         for(int i=mid; i<=r; i++) cnt[pref[i]] ++; 
    739     }
    740 }
    741  
    742 bool check() {
    743     maxi = 0;
    744     for(int j=1; j<=n; j++) {
    745         pref[j] = pref[j-1] ^ (a[j] & answ);
    746     }
    747  
    748     divide(1, n);
    749  
    750     for(int i=1; i<=n; i++) {
    751         cnt[pref[i]] = 0;
    752     }
    753  
    754     if(maxi == answ) return 1;
    755     return 0;
    756 }
    757  
    758 void work() {
    759     cin>>n;
    760  
    761     int mxtmp = 0, anstmp = 0;
    762     for(int i=1; i<=n; i++) {
    763         cin>>a[i];
    764         mxtmp = max(mxtmp, a[i]);
    765         par[0][i] = i;
    766     }
    767  
    768     for(int i=1; i<=n; i++) anstmp ^= (a[i] & mxtmp);
    769  
    770     for(int i=n; i>=1; i--) {
    771         for(int j=1; j<lg; j++) {
    772             int x = par[j-1][i], y = par[j-1][min(n, i + (1<<(j-1)))];
    773             if(a[x] > a[y]) par[j][i] = x;
    774             else par[j][i] = y;
    775         }
    776     }
    777  
    778     for(int i=lg-1; i>=0; i--) {
    779         answ += (1 << i);
    780  
    781         if(check() == 0) {
    782             answ -= (1 << i);
    783         }
    784     }
    785  
    786     cout<<max(answ, anstmp)<<endl;
    787 }
    788  
    789 void reset_work() {
    790     answ = 0;
    791     for(int i=1; i<=n; i++) a[i] = 0, pref[i] = 0;
    792     return;
    793 }
    794  
    795 int main() {
    796     ios_base::sync_with_stdio(false), cin.tie(0);
    797  
    798     // freopen("inp.txt", "r", stdin);
    799     // freopen("out-m.txt", "w", stdout);
    800  
    801  
    802     cin>>t;
    803     // t = 1;
    804     while(t --) {
    805         work();
    806         reset_work();
    807     }
    808  
    809     return 0;
    810 }
    811 ```
    812 
    813 ---
    814 
    815 [2269F - AghaBalaSar and Hamed](/contest/2269/problem/F "Codeforces Round 1124 (Div. 2)") / [2268D - AghaBalaSar and Hamed](/contest/2268/problem/D "Codeforces Round 1124 (Div. 1)")
    816 
    817 **Idea:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari")  
    818  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari")
    819 
    820 **What is AghaBalaSar?**
    821 
    822 AghaBalaSar (آقابالاسر) is a term commonly used in the Iranian CP community for the nearest greater/smaller element on either side.
    823 
    824 I also used it in a previous contest as well :D [2127F - Hamed and AghaBalaSar](/contest/2127/problem/F)
    825 
    826 **Hints**
    827 
    828 **Hint 1**
    829 
    830 For a fixed $i$, try to describe the shape of a shortest path. In particular, how many times do we really need to move left?
    831 
    832 **Hint 2**
    833 
    834 For a fixed $i$, what can we say about the positions $j$ whose $f(i, j)$ are $1$, $2$, or greater than $2$?
    835 
    836 **Solution**
    837 
    838 The important observation is that a shortest path has the form
    839 
    840 $L,R,R,\ldots,R,L$
    841 
    842 So after at most one initial left move, all right moves are forced.
    843 
    844 Let $R_i=\text{the first }j \gt i\text{ such that }p_j \gt p_i$ or $n+1$ if it does not exist.
    845 
    846 We split the permutation into blocks ending at positions $r$ with $R_r=n+1$, because we cannot move from one block to any of the blocks to its right.
    847 
    848 Let $dp_i$ be the sum of distances from $i$ to all positions in the current block.
    849 
    850 Let $x$ be the rightmost position reachable from $i$ in at most two moves.
    851 
    852 There are two cases.
    853 
    854 **Case 1: ($x=R[i]$)**
    855 
    856 Then there is no way to reach anything beyond $R_i$ in two moves.
    857 
    858 Therefore, for every $j \gt R_i$, every shortest path starts with $i\to R_i$, hence $f(i,j)=1+f(R_i,j)$.
    859 
    860 Now compare the contributions of $i$ and $R_i$.
    861 
    862 * For $j \lt i$, both distances are $1$.
    863 * For $j=i$, we gain $-1$.
    864 * For $j \gt i$, the distance from (i) is exactly one larger than the corresponding distance from $R_i$.
    865 
    866 The total difference simplifies to $dp_i-dp_{R_i}=r-i-1$. Thus
    867 
    868 $dp_i=dp_{R_i}+r-i-1$
    869 
    870 Where $r$ is the end of the current block.
    871 
    872 **Case 2: ($x \gt R_i$)**
    873 
    874 Now $x$ is reachable in two moves, and $x$ is the furthest position with this property.
    875 
    876 For every $j \gt x$, $f(i,j)=2+f(x,j)$.
    877 
    878 Why? We can reach $x$ in two moves and then follow an optimal path from $x$. Also, by definition of $x$, no position farther right can be reached from $i$ in two moves, so we cannot do better.
    879 
    880 Thus, for everything after $x$, we can simply use $dp_x$.
    881 
    882 It remains to handle the positions between $i$ and $x$.
    883 
    884 Since $x$ is reachable in at most two moves, every position $j\in(i,x]$ has distance either $2$ or $3$ from $i$.
    885 
    886 Let $c_2$ be the number of $j \in (i,x]$ such that $f(i,j)=2$.
    887 
    888 There are $x-i-1$ positions strictly between $i$ and $x$. Among them, $c_2-1$ have distance $2$, because $x$ itself is also counted by $c_2$. Therefore the remaining $x-i-c_2$ positions have distance $3$. Comparing their contributions with $dp_x$, we get
    889 
    890 $dp_i=dp_x+2(r-i)-2-c_2$
    891 
    892 So the only remaining problem is computing $x$ and $c_2$ efficiently.
    893 
    894 **Finding the positions reachable in two moves**
    895 
    896 A position $j \gt i$ can be reached in two moves in exactly these ways:
    897 
    898 * $i \lt j \lt R_i$, by $i\to R_i\to j$;
    899 * $j=R_{R_i}$;
    900 * There is some $k\le i$ such that $R_k=j$, because we can do $i\to k\to j$.
    901 
    902 Let $L_j$ be the minimum $k$ such that $R_k = j$, then third case is simply $L_j\le i$.
    903 
    904 We process $i$ from right to left and maintain all positions $j$ satisfying $L_j\le i$. The rightmost marked position is exactly $x$.
    905 
    906 **Computing $c_2$**
    907 
    908 Among the distance-$2$ positions we have:
    909 
    910 * $R_i-i-1$ positions between $i$ and $R_i$;
    911 * $R_{R_i}$, if it exists;
    912 * all currently marked positions except $R_i$.
    913 
    914 There is one possible double count: $R_{R_i}$ may itself already be marked.
    915 
    916 So we can compute $c_2$ by processing $i$ from right to left and maintaining all marked positions.
    917 
    918 Complexity: $\mathcal{O}(n)$
    919 
    920 **Code**
    921 
    922 ```
    923 #include <bits/stdc++.h>
    924 using namespace std;
    925 
    926 using ll = long long;
    927 
    928 const int MXN = 1e6+5;
    929 
    930 int n, p[MXN], R[MXN], L[MXN];
    931 ll dp[MXN];
    932 vector<int> vec[MXN];
    933 bool mark[MXN];
    934 
    935 void solve(int l, int r) {
    936     dp[r] = r-l;
    937     int lst=r, cnt=0;
    938     if(L[r]!=n+1) {
    939         vec[L[r]].push_back(r);
    940         mark[r] = 1;
    941         cnt++;        
    942     }
    943     for(int i=r-1; i>=l; i--) {
    944         while(!mark[lst]) lst--;
    945         if(lst==R[i]) {
    946             dp[i] = dp[R[i]] + r-l+1 - 2 - (i-l);
    947         }
    948         else {
    949             int c1 = i-l + 1;
    950             int c2 = R[i]-i-1 + (R[R[i]]!=n+1) + cnt - 1 - (R[R[i]]!=n+1 && L[R[R[i]]]<=i);
    951             dp[i] = dp[lst] + 2*(r-l+1) - 3 - 2*c1 - c2 + 1;
    952         }
    953         for(int j : vec[i])
    954             mark[j] = 0,
    955             cnt--;
    956         if(L[i]!=n+1) {
    957             vec[L[i]].push_back(i);
    958             mark[i] = 1;
    959             cnt++;
    960         }
    961     }
    962 
    963     for(int i=l; i<=r; i++)
    964         dp[i] += l-1;
    965 }
    966 
    967 void Main() {
    968     cin >> n;
    969     for(int i=1; i<=n; i++) {
    970         cin >> p[i];
    971         vec[i].clear();
    972         mark[i] = 0;
    973     }
    974     fill(L+1, L+n+1, n+1);
    975     for(int i=n; i>=1; i--) {
    976         for(R[i]=i+1; R[i]<=n && p[R[i]]<p[i]; R[i]=R[R[i]]);
    977         L[R[i]] = i;
    978     }
    979     int l=1;
    980     for(int r=1; r<=n; r++)
    981         if(R[r]==n+1) {
    982             solve(l, r);
    983             l = r+1;
    984         }
    985     ll ans = 0;
    986     for(int i=1; i<=n; i++)
    987         ans += dp[i];
    988     cout << ans << '\n';
    989 }
    990 
    991 int32_t main() {
    992     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    993     int T;
    994     cin >> T;
    995     while(T--) Main();
    996     return 0;
    997 }
    998 ```
    999 
   1000 ---
   1001 
   1002 [2268E - Kia Kio and Tree of Life](/contest/2268/problem/E "Codeforces Round 1124 (Div. 1)")
   1003 
   1004 **Idea:** [sweetweasel](/profile/sweetweasel "International Master sweetweasel")  
   1005  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T")
   1006 
   1007 **Hints**
   1008 
   1009 **Hint 1**
   1010 
   1011 The number of valid trees that can be constructed from a segment of length $m$ is the $m$-th Catalan number.
   1012 
   1013 **Hint 2**
   1014 
   1015 The vertices inside every subtree form a continuous subarray. Fix a subarray of length $l$. In how many trees does it appear as the subtree below some edge?
   1016 
   1017 **Answer**
   1018 
   1019 Exactly $C_lC_{n-l}$, where $C_i$ is the $i$-th Catalan number.
   1020 
   1021 **Hint 3**
   1022 
   1023 Consider every bit independently. If the XOR of the entire array has this bit set, exactly one of the two components created by cutting any edge has this bit set.
   1024 
   1025 **Hint 4**
   1026 
   1027 Suppose the bit is not set in the XOR of the entire array. We need, for every length $l$, the number of subarrays of length $l$ whose XOR has this bit set.
   1028 
   1029 **Hint 5**
   1030 
   1031 Let $p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$. Encode the corresponding bit of each $p_i$ as either $1$ or $-1$. The number of pairs with different signs can be found from their autocorrelation.
   1032 
   1033 **Hint 6**
   1034 
   1035 We only need a weighted sum of the autocorrelation values. Using Parseval's identity, this weighted sum can be calculated without performing an inverse NTT for every bit.
   1036 
   1037 **Solution**
   1038 
   1039 Let $C_m$ be the $m$-th Catalan number:
   1040 
   1041 $ C_m=\frac{1}{m+1}\binom{2m}{m}. $
   1042 
   1043 The recursive construction in the statement generates exactly the binary trees whose inorder traversal is:
   1044 
   1045 $ 1,2,\ldots,n. $
   1046 
   1047 Therefore, there are $C_n$ valid trees.
   1048 
   1049 Consider an edge between a parent and one of its children. The component containing the child after removing this edge is exactly the child's subtree. Since the inorder traversal is fixed, the vertices of this subtree form a continuous subarray.
   1050 
   1051 Now fix a proper subarray $[L,R]$ of length $l$.
   1052 
   1053 There are $C_l$ possible trees inside this subarray. After deleting this subtree, the remaining $n-l$ vertices can form any valid tree, giving $C_{n-l}$ possibilities.
   1054 
   1055 The location of $[L,R]$ determines one gap in the inorder traversal of the remaining tree. This gap corresponds to a unique empty child position, so the chosen subtree can be attached there in exactly one way.
   1056 
   1057 Therefore, a fixed subarray of length $l$ appears as the child subtree of an edge in exactly:
   1058 
   1059 $ C_lC_{n-l} $
   1060 
   1061 valid trees.
   1062 
   1063 Let:
   1064 
   1065 $ S=a_1\oplus a_2\oplus\cdots\oplus a_n. $
   1066 
   1067 For a subarray $I$, let its XOR be $X_I$. Cutting the edge above this subtree produces two components with XOR values:
   1068 
   1069 $ X_I \qquad\text{and}\qquad S\oplus X_I. $
   1070 
   1071 Thus, the whole answer can be written as:
   1072 
   1073 $ \sum_{\substack{I\text{ is a subarray}\\|I| \lt n}} C_{|I|}C_{n-|I|} \left(X_I+(S\oplus X_I)\right). $
   1074 
   1075 We calculate this sum bit by bit.
   1076 
   1077 Fix a bit $b$.
   1078 
   1079 **Case 1: Bit $b$ of $S$ is set.**
   1080 
   1081 At this bit, $X_I$ and $S\oplus X_I$ are different. Therefore, exactly one of the two components has this bit set for every tree and every edge.
   1082 
   1083 There are $C_n$ trees, and every tree has $n-1$ edges. Hence, before multiplying by $2^b$, the contribution is:
   1084 
   1085 $ (n-1)C_n. $
   1086 
   1087 **Case 2: Bit $b$ of $S$ is not set.**
   1088 
   1089 In this case, the two component XORs have the same value at bit $b$.
   1090 
   1091 * If bit $b$ of $X_I$ is zero, the edge contributes zero.
   1092 * If bit $b$ of $X_I$ is one, both components contribute this bit, so the edge contributes twice.
   1093 
   1094 For every length $l$, let $D_l$ be the number of subarrays of length $l$ whose XOR has bit $b$ set. The contribution of this bit is:
   1095 
   1096 $ 2\sum_{l=1}^{n-1}D_lC_lC_{n-l}. $
   1097 
   1098 It remains to calculate every $D_l$.
   1099 
   1100 Define the prefix XORs:
   1101 
   1102 $ p_0=0,\qquad p_i=a_1\oplus a_2\oplus\cdots\oplus a_i. $
   1103 
   1104 The XOR of a subarray of length $l$ starting after position $i$ is:
   1105 
   1106 $ p_i\oplus p_{i+l}. $
   1107 
   1108 Define:
   1109 
   1110 $ s_i= \begin{cases} 1,&\text{if bit }b\text{ of }p_i\text{ is zero},\\ -1,&\text{if bit }b\text{ of }p_i\text{ is one}. \end{cases} $
   1111 
   1112 The required subarray has bit $b$ set exactly when $s_i$ and $s_{i+l}$ are different.
   1113 
   1114 Consider:
   1115 
   1116 $ R_l=\sum_{i=0}^{n-l}s_is_{i+l}. $
   1117 
   1118 Equal pairs contribute $1$, while different pairs contribute $-1$. Since there are $n+1-l$ pairs in total:
   1119 
   1120 $ R_l=(n+1-l)-2D_l. $
   1121 
   1122 Therefore:
   1123 
   1124 $ D_l=\frac{n+1-l-R_l}{2}. $
   1125 
   1126 The values $R_l$ form the autocorrelation of the sequence $s$. After padding the sequence with enough zeros, let $F_k$ be its NTT. The NTT representation of the autocorrelation is:
   1127 
   1128 $ P_k=F_kF_{-k}. $
   1129 
   1130 With a transform of size $N$, the index $-k$ is represented by $(N-k)\bmod N$.
   1131 
   1132 A direct implementation could perform an inverse NTT and obtain every $R_l$. However, we only need their weighted sum.
   1133 
   1134 Let:
   1135 
   1136 $ w_l=C_lC_{n-l} $
   1137 
   1138 for $1\leq l \lt n$, and let $W_k$ be the NTT of $w$. Using Parseval's identity:
   1139 
   1140 $ \sum_{l=1}^{n-1}w_lR_l = \frac{1}{N} \sum_{k=0}^{N-1}P_kW_{-k}. $
   1141 
   1142 Also:
   1143 
   1144 $ 2\sum_{l=1}^{n-1}D_lw_l = \sum_{l=1}^{n-1}(n+1-l)w_l - \sum_{l=1}^{n-1}R_lw_l. $
   1145 
   1146 The first sum is independent of the bit and can be precomputed. The second sum is calculated using one forward NTT and Parseval's identity.
   1147 
   1148 Therefore, we need one NTT for the weights and at most one NTT for each of the $18$ bits.
   1149 
   1150 The total time complexity is:
   1151 
   1152 $ \mathcal{O}(18n\log n), $
   1153 
   1154 and the memory complexity is $\mathcal{O}(n)$.
   1155 
   1156 **Code**
   1157 
   1158 ```
   1159 #include <bits/stdc++.h>
   1160  
   1161 using namespace std;
   1162  
   1163 using i64 = long long;
   1164  
   1165 const int mod = 998244353;
   1166 const int G = 3;
   1167 const int B = 18;
   1168 const int N = 200000;
   1169  
   1170 int qpow(int a, int b) {
   1171     int r = 1;
   1172     while (b) {
   1173         if (b & 1) r = (i64)r * a % mod;
   1174         a = (i64)a * a % mod;
   1175         b >>= 1;
   1176     }
   1177     return r;
   1178 }
   1179  
   1180 struct NTT {
   1181     int n;
   1182     vector<int> rev, roots;
   1183  
   1184     NTT(int n) : n(n), rev(n), roots(n) {
   1185         for (int i = 1; i < n; i++) {
   1186             rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
   1187         }
   1188  
   1189         for (int len = 1; len < n; len <<= 1) {
   1190             int z = qpow(G, (mod - 1) / (len << 1));
   1191             roots[len] = 1;
   1192             for (int i = 1; i < len; i++) {
   1193                 roots[len + i] = (i64)roots[len + i - 1] * z % mod;
   1194             }
   1195         }
   1196     }
   1197  
   1198     void transform(vector<int>& a) const {
   1199         for (int i = 0; i < n; i++) {
   1200             if (i < rev[i]) swap(a[i], a[rev[i]]);
   1201         }
   1202  
   1203         for (int len = 1; len < n; len <<= 1) {
   1204             for (int i = 0; i < n; i += len << 1) {
   1205                 for (int j = 0; j < len; j++) {
   1206                     int x = a[i + j];
   1207                     int y = (i64)a[i + j + len] * roots[len + j] % mod;
   1208  
   1209                     a[i + j] = x + y;
   1210                     if (a[i + j] >= mod) a[i + j] -= mod;
   1211  
   1212                     a[i + j + len] = x - y;
   1213                     if (a[i + j + len] < 0) a[i + j + len] += mod;
   1214                 }
   1215             }
   1216         }
   1217     }
   1218 };
   1219  
   1220 vector<int> fac(2 * N + 1);
   1221 vector<int> ifac(2 * N + 1);
   1222 vector<int> catalan(N + 1);
   1223  
   1224 void init() {
   1225     fac[0] = 1;
   1226     for (int i = 1; i <= 2 * N; i++) {
   1227         fac[i] = (i64)fac[i - 1] * i % mod;
   1228     }
   1229  
   1230     ifac[2 * N] = qpow(fac[2 * N], mod - 2);
   1231     for (int i = 2 * N; i >= 1; i--) {
   1232         ifac[i - 1] = (i64)ifac[i] * i % mod;
   1233     }
   1234  
   1235     for (int i = 0; i <= N; i++) {
   1236         catalan[i] = (i64)fac[2 * i] * ifac[i] % mod
   1237                    * ifac[i + 1] % mod;
   1238     }
   1239 }
   1240  
   1241 void solve() {
   1242     int n;
   1243     cin >> n;
   1244  
   1245     vector<int> a(n), pref(n + 1);
   1246     for (int& x : a) cin >> x;
   1247  
   1248     if (n == 1) {
   1249         cout << 0 << '\n';
   1250         return;
   1251     }
   1252  
   1253     for (int i = 1; i <= n; i++) {
   1254         pref[i] = pref[i - 1] ^ a[i - 1];
   1255     }
   1256  
   1257     vector<int> weight(n);
   1258     int W = 0;
   1259  
   1260     for (int d = 1; d < n; d++) {
   1261         weight[d] = (i64)catalan[d] * catalan[n - d] % mod;
   1262         W = (W + (i64)(n - d + 1) * weight[d]) % mod;
   1263     }
   1264  
   1265     int len = 1;
   1266     while (len < 2 * (n + 1)) len <<= 1;
   1267  
   1268     NTT ntt(len);
   1269  
   1270     vector<int> kernel(len);
   1271     for (int d = 1; d < n; d++) {
   1272         kernel[d] = weight[d];
   1273         kernel[len - d] = weight[d];
   1274     }
   1275  
   1276     ntt.transform(kernel);
   1277  
   1278     int answer = (i64)((1 << B) - 1) * W % mod;
   1279     int inv_len = qpow(len, mod - 2);
   1280     int inv_two = (mod + 1) / 2;
   1281     int total_xor = pref[n];
   1282  
   1283     vector<int> seq(len);
   1284  
   1285     for (int b = 0; b < B; b++) {
   1286         if ((total_xor >> b) & 1) continue;
   1287  
   1288         fill(seq.begin(), seq.end(), 0);
   1289  
   1290         for (int i = 0; i <= n; i++) {
   1291             seq[i] = ((pref[i] >> b) & 1) ? mod - 1 : 1;
   1292         }
   1293  
   1294         ntt.transform(seq);
   1295  
   1296         int spectral_sum = 0;
   1297  
   1298         for (int k = 0; k < len; k++) {
   1299             int opposite = (len - k) & (len - 1);
   1300  
   1301             int term = (i64)kernel[k] * seq[k] % mod
   1302                      * seq[opposite] % mod;
   1303  
   1304             spectral_sum += term;
   1305             if (spectral_sum >= mod) spectral_sum -= mod;
   1306         }
   1307  
   1308         int Q = (i64)spectral_sum * inv_len % mod * inv_two % mod;
   1309  
   1310         answer -= (i64)(1 << b) * Q % mod;
   1311         if (answer < 0) answer += mod;
   1312     }
   1313  
   1314     cout << answer << '\n';
   1315 }
   1316  
   1317 int main() {
   1318     cin.tie(0)->sync_with_stdio(0);
   1319  
   1320     init();
   1321  
   1322     int T;
   1323     cin >> T;
   1324  
   1325     while (T--) solve();
   1326 }
   1327 ```
   1328 
   1329 ---
   1330 
   1331 [2268F - Deglado](/contest/2268/problem/F "Codeforces Round 1124 (Div. 1)")
   1332 
   1333 **Idea:** [eren__](/profile/eren__ "Grandmaster eren__")  
   1334  **Preparation:** [Hamed_Ghaffari](/profile/Hamed_Ghaffari "International Grandmaster Hamed_Ghaffari") and [_R00T](/profile/_R00T "Master _R00T")
   1335 
   1336 **Hints**
   1337 
   1338 **Hint 1**
   1339 
   1340 Think of each operation as swapping two elements in each of two columns. Therefore, the parity of the total number of inversions over all columns never changes. So if it is odd, the answer is $-1$.
   1341 
   1342 **Hint 2**
   1343 
   1344 Consider the total number of inversions over all columns. One operation can decrease this number by at most $2$. Since there are $2n\binom{2n}{2}$ inversions in the worst case, we need at least $n\binom{2n}{2}$ operations in general. Therefore, our construction can only afford about $9n$ additional operations.
   1345 
   1346 **Hint 3**
   1347 
   1348 Process the values in increasing order. For each value $x$, try to place all occurrences of $x$ into row $x$, so that values $1,2,\ldots,2n-1$ are placed in their correct rows one by one.
   1349 
   1350 **Hint 4**
   1351 
   1352 Pair the columns: $(1,2),(3,4),\ldots$. For a fixed $x$, each pair can contain $0,1,$ or $2$ copies of $x$ in its top row.
   1353 
   1354 **Hint 5**
   1355 
   1356 Distinguish the two possible one-$x$ cases: the $x$ is on top the of left column (we call them $L$-pairs) or on top of the right column (we call them $R$-pairs).
   1357 
   1358 **Hint 6**
   1359 
   1360 Process $L$-pairs from left to right and $R$-pairs from right to left. If an $L$ and $R$ meet, they can be fixed together.
   1361 
   1362 **Solution**
   1363 
   1364 First, consider the parity of the total number of inversions in all columns.
   1365 
   1366 One operation swaps the two top elements with the two bottom elements. In each affected column, this is equivalent to swapping two elements, so the parity of the inversion count of that column changes. Since two columns are affected, the parity of the total inversion count does not change.
   1367 
   1368 In the final grid every column is sorted, so the total number of inversions is $0$, which is even.
   1369 
   1370 Therefore, if the initial total number of inversions is odd, the answer is immediately $-1$.
   1371 
   1372 Now assume it is even.
   1373 
   1374 We process
   1375 
   1376 $ x=1,2,\ldots,2n-1. $
   1377 
   1378 Our goal at step $x$ is to put every occurrence of $x$ into row $x$.
   1379 
   1380 Pair the columns:
   1381 
   1382 $ (1,2),(3,4),\ldots,(2n-1,2n). $
   1383 
   1384 For each pair, look at its two cells in row $x$.
   1385 
   1386 There are four possibilities:
   1387 
   1388 * Type $0$: neither cell contains $x$;
   1389 * Type $L$: only the left cell contains $x$;
   1390 * Type $R$: only the right cell contains $x$;
   1391 * Type $1$: both cells contain $x$.
   1392 
   1393 Our goal is to make every pair Type $1$. Once this happens, all $2n$ copies of $x$ are in row $x$.
   1394 
   1395 For each $x=1,2,\ldots,2n-2$, we proceed through the following steps:
   1396 
   1397 **1.** Consider only the pairs $2,3,\ldots,n-1$. The first and last pairs will be handled separately.
   1398 
   1399 **2.** We get rid of all Type $1$ pairs. For every Type $1$ pair, perform an operation on that pair. The two $x$'s are currently on top, so after the operation, they move down and the pair becomes Type $0$.
   1400 
   1401 **3.** While there is a Type $L$ pair, take the leftmost one, say pair $i$:  
   1402       **3.1.** If pair $i+1$ is Type $0$ or Type $L$, move the right $x$ of pair $i$ to row $x+1$ by performing operations on pair $i$, then perform an operation on pairs $i$ and $i+1$. Pair $i$ becomes Type $1$.  
   1403       **3.2.** If pair $i+1$ is Type $R$, leave this Type $L$ pair for later.
   1404 
   1405 **4.** While there is a Type $R$ pair, take the rightmost one, say pair $i$:  
   1406       **4.1.** If pair $i-1$ is Type $0$ or Type $R$, do the symmetric operation: move the appropriate $x$ to row $x+1$, then perform an operation so that pair $i$ becomes Type 1.  
   1407       **4.2.** If pair $i-1$ is Type $L$, the two pairs form an $L$-$R$ configuration. Move the right $x$ of pair $i-1$ and the left $x$ of pair $i$ to the same row, then perform an operation to move both $x$'s to the top. Both pairs become Type $1$.
   1408 
   1409 **5.** At this point, every middle pair is Type $0$ or Type $1$. For each Type $0$ pair, move its two $x$'s to the same row and perform an operation to move both to the top. Thus every middle pair becomes Type $1$.
   1410 
   1411 **6.** Finally, fix the first and last pairs. They can always be made Type $1$ using at most $2n−x+2$ operations (it means we need at most $2$ additional operations).
   1412 
   1413 For $x=2n-1$, for each $i=1,2,\ldots,2n-1$, if $a_{2n-1,i}\neq 2n-1$, perform an operation on the subgrid whose top-left cell is $(2n-1,i)$. This requires at most $2n-1$ operations.
   1414 
   1415 **Number of operations**
   1416 
   1417 For a fixed $x$, each pair needs at most $2n-x$ operations during the main process. There are $n$ pairs, giving at most $n(2n-x)$.
   1418 
   1419 The first and last pairs require at most $2$ additional operations for each $x$, contributing $2\cdot2(2n-2)$.
   1420 
   1421 Finally, the $x=2n-1$ case costs at most $n-1$ additional operations.
   1422 
   1423 Hence the total is at most
   1424 
   1425 $ \sum_{x=1}^{2n-2} n(2n-x) +4(2n-2)+(n-1). $
   1426 
   1427 The main sum is
   1428 
   1429 $ n\sum_{x=1}^{2n-2}(2n-x) = n\binom{2n}{2}. $
   1430 
   1431 Therefore,
   1432 
   1433 $ \begin{aligned} \text{operations} &\le n\binom{2n}{2} +4(2n-2)+(n-1)\\ &= n\binom{2n}{2}+9n-9\\ &\le n\binom{2n}{2}+9n. \end{aligned} $
   1434 
   1435 So the required bound is satisfied.
   1436 
   1437 The construction also gives the actual sequence of operations if we implement the described moves.
   1438 
   1439 **Code**
   1440 
   1441 ```
   1442 #include <bits/stdc++.h>
   1443 using namespace std;
   1444  
   1445 using pii = pair<int, int>;
   1446  
   1447 const int MXN = 202;
   1448  
   1449 int n, n2, a[MXN][MXN];
   1450 vector<pii> ans;
   1451  
   1452 inline void opr(int i, int j) {
   1453     swap(a[i][j], a[i+1][j]);
   1454     swap(a[i][j+1], a[i+1][j+1]);
   1455     ans.push_back({i, j});
   1456 }
   1457  
   1458 inline int wh(int x, int j) {
   1459     for(int i=x; i<=n2; i++)
   1460         if(a[i][j]==x)
   1461             return i;
   1462     assert(0);        
   1463     return -1;
   1464 }
   1465  
   1466 inline void R(int x, int j) {
   1467     for(int i=wh(x, j+1)-1; i>=x; i--) opr(i, j+1);
   1468 }
   1469  
   1470 inline void RL(int x, int j) {
   1471     int pos1 = wh(x, j+1), pos2 = wh(x, j+2);
   1472     while(pos1>pos2) opr(--pos1, j);
   1473     while(pos1<pos2) opr(--pos2, j+2);
   1474     while(pos1>x) opr(--pos1, j+1);
   1475 }
   1476  
   1477 inline void L(int x, int j) {
   1478     for(int i=wh(x, j)-1; i>=x; i--) opr(i, j-1);
   1479 }
   1480  
   1481 inline void L1(int x, int j) {
   1482     if(a[x+1][j]==x) opr(x+1, j); // extra, we can ignore it for x<=2n-3
   1483     opr(x, j-1); // extra, we can ignore it
   1484     for(int i=wh(x, j)-1; i>=x+1; i--) opr(i, j);
   1485     opr(x, j-1);
   1486 }
   1487  
   1488 inline void solve0(int x, int j) {
   1489     int pos1=wh(x, j), pos2=wh(x, j+1);
   1490     while(pos1>pos2) opr(--pos1, j-1);
   1491     while(pos1<pos2) opr(--pos2, j+1);
   1492     while(pos1>x) opr(--pos1, j);
   1493 }
   1494  
   1495 inline void lft(int x) { // 2 extra
   1496     if(a[x][2]==x) {
   1497         if(a[x][1]==x) return;
   1498         if(a[x+1][1]==x) opr(x+1, 1);
   1499         opr(x, 1);
   1500     }
   1501     else if(a[x][1]==x) {
   1502         if(a[x+1][2]==x) opr(x+1, 1);
   1503         opr(x, 1);
   1504     }
   1505  
   1506     int pos1=wh(x, 1), pos2=wh(x, 2);
   1507     if(pos1>pos2) {
   1508         while(pos1>pos2) opr(--pos1, 1);
   1509         pos2++;
   1510     }
   1511     while(pos1<pos2) opr(--pos2, 2);
   1512     while(pos1>x) opr(--pos1, 1);
   1513 }
   1514  
   1515 inline void rgt(int x) { // 2 extra
   1516     if(a[x][n2-1]==x) {
   1517         if(a[x][n2]==x) return;
   1518         if(a[x+1][n2]==x) opr(x+1, n2-1);
   1519         opr(x, n2-1);
   1520     }
   1521     else if(a[x][n2]==x) {
   1522         if(a[x+1][n2-1]==x) opr(x+1, n2-1);
   1523         opr(x, n2-1);
   1524     }
   1525  
   1526     int pos1=wh(x, n2-1), pos2=wh(x, n2);
   1527     if(pos1<pos2) {
   1528         while(pos1<pos2) opr(--pos2, n2-1);
   1529         pos1++;
   1530     }
   1531     while(pos1>pos2) opr(--pos1, n2-2);
   1532     while(pos1>x) opr(--pos1, n2-1);
   1533 }
   1534  
   1535  
   1536 inline void lst() { // 2n-1 extra
   1537     for(int j=1; j<=n2-1; j++)
   1538         if(a[n2][j]!=n2) opr(n2-1, j);
   1539 }
   1540  
   1541 inline void print() {
   1542     cout << ans.size() << '\n';
   1543     for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
   1544     ans.clear();
   1545 }
   1546  
   1547 void Main() {
   1548     cin >> n;
   1549     n2 = n<<1;
   1550     for(int i=1; i<=n2; i++)
   1551         for(int j=1; j<=n2; j++)
   1552             cin >> a[i][j];
   1553     int inv = 0;
   1554     for(int j=1; j<=n2; j++)
   1555         for(int i1=1; i1<=n2; i1++)
   1556             for(int i2=i1+1; i2<=n2; i2++)
   1557                 inv ^= a[i1][j]>a[i2][j];
   1558     if(inv) {
   1559         cout << "-1\n";
   1560         return;
   1561     }
   1562     if(n==1) {
   1563         if(a[1][1]==2) cout << "1\n1 1\n";
   1564         else cout << "0\n";
   1565         return;
   1566     }
   1567     for(int x=1; x<=n2-2; x++) {
   1568         for(int j=3; j<=n2-3; j+=2)
   1569             if(a[x][j]==x && a[x][j+1]==x) opr(x, j);
   1570         for(int j=3; j<=n2-3; j+=2)
   1571             if(a[x][j]==x && a[x][j+1]!=x) {
   1572                 if(j==n2-3 || a[x][j+3]!=x) R(x, j);
   1573                 else RL(x, j);
   1574             }
   1575         for(int j=n2-3; j>=3; j-=2)
   1576             if(a[x][j]!=x && a[x][j+1]==x) {
   1577                 if(a[x][j-2]==x && a[x][j-1]==x) L1(x, j);
   1578                 else L(x, j);
   1579             }
   1580         for(int j=3; j<=n2-3; j+=2)
   1581             if(a[x][j]!=x)
   1582                 solve0(x, j);
   1583         lft(x);
   1584         rgt(x);
   1585     }
   1586     lst();
   1587     print();
   1588 }
   1589  
   1590 int32_t main() {
   1591     cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
   1592     int tc;
   1593     cin >> tc;
   1594     while(tc--) Main();
   1595     return 0;
   1596 }
   1597 ```
   1598 
   1599 **Challenge**
   1600 
   1601 Can you improve the construction and reduce the number of operations below $n\binom{2n}{2} + 9n$ ?