If Hamed waits $$$d$$$ days before withdrawing, the amount of money in his card increases by exactly $$$2^d$$$.

Therefore the problem becomes: Split $$$n$$$ into exactly $$$k$$$ positive integers $$$a_1,\dots,a_k$$$, and maximize

For fixed $$$a+b$$$, $$$2^a+2^b$$$ is larger when one of them is as large as possible.

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$$$.

Thus the optimal lengths are

So the maximum amount is $$$2^{n-k+1}+2(k-1)$$$

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int tc;
    cin >> tc;
    while(tc--) {
        int n, k;
        cin >> n >> k;
        cout << (1<<(n-k+1)) + 2*(k-1) << '\n';
    }
    return 0;
}

Fact

The only cycles of the function $$$f(x)$$$ are

and

Every positive integer eventually reaches exactly one of these two cycles.

Solution

For each initial value $$$a_i$$$, we simulate the process until it reaches one of the two cycles.

If it reaches $$$1$$$, we assign it the signature $$$8$$$.

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$$$.

Its position after $$$t$$$ operations is

Therefore, two numbers entering the 8-cycle will eventually have identical values at every step if and only if:

We use this value as the signature of each number.

Thus, two initial values are in tune if and only if their signatures are equal.

Let $$$cnt[x]$$$ be the number of elements with signature $$$x$$$. The answer is

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.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"

const int N = 2e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;

// The unique non-trivial cycle of the "sum of squared decimal digits" map.
// 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...
const ll CYC[8] = {4, 16, 37, 58, 89, 145, 42, 20};

int t, n;
ll cnt[9];

// Signature of a lighthouse:
//   8       -> "calm": the value reaches 1 and stays there forever.
//   0..7    -> "restless": the phase of the lighthouse on the 8-cycle.
// Two lighthouses are in tune iff their signatures are equal.
int sig(ll x) {
    ll s = 0;
    while (true) {
        if (x == 1) return 8;
        for (int k = 0; k < 8; k++)
            if (x == CYC[k]) return (int)(((k - s) % 8 + 8) % 8);
        ll y = 0;
        while (x > 0) { ll r = x % 10; y += r * r; x /= 10; }
        x = y;
        s++;
    }
}

void work() {
    cin >> n;

    for (int i = 0; i <= 8; i++) cnt[i] = 0;

    for (int i = 1; i <= n; i++) {
        ll a; cin >> a;
        cnt[sig(a)] ++;
    }

    ll ans = 0;
    for (int i = 0; i <= 8; i++) ans += cnt[i] * (cnt[i] - 1) / 2;

    cout << ans << endl;
}

void reset_work() {
    return;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);

    cin >> t;
    while (t --) {
        work();
        reset_work();
    }

    return 0;
}

We can analyze the problem by splitting it into two cases based on the relationship between $$$2k$$$ and $$$n$$$:

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.

After removing the middle section, we are left with a prefix of length $$$k-1$$$ and a suffix of length $$$k-1$$$.

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.

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.

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.

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.

Using two pointers (l and r) allows us to implement both cases cleanly in $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h> 
#define pb push_back 
#define F first 
#define S second 
#define all(a) a.begin(),a.end() 
#define sz(a) (int)a.size() 
#define pii pair<ll,ll>
#define ll long long
#define ld long double
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
using namespace std ;
const int maxn = 5e5 + 10  ;
int a[maxn] ;
signed main(){
  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int t ;cin >> t ; 
  while(t--){
    int n , k ; cin >> n  >> k; 
    for(int i = 1 ;i <= n ; i++){
       cin >> a[i] ; 
    }
    ll sum = 0 ;
    vector <int> vec;   
    for(int i = 1 ; i <= n ; i++){
      if(i >= k && i <= n-k+1){
        sum += a[i] ;
        continue ; 
      } 
      vec.pb(a[i]) ; 
    }
    int t2 = max(0 , sz(vec)- (k-1)) ;
    int l = 0 , r= sz(vec)-1 ;
    while(t2--){
      sum += max(vec[l] , vec[r]) ;
      l++;
      r--;  
    }
    cout << sum << "\n" ;
  }
}

The possible XOR masks in one operation are:

Their binary representations are:

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.

The All-Meat values smaller than $$$16$$$ are:

or in binary:

They all have even popcount. Therefore, an element with odd popcount can never become All-Meat. This gives us the following upper bound:

Now we prove that this upper bound can always be achieved.

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:

Every element strictly between $$$i$$$ and $$$j$$$ is XORed twice, so it remains unchanged. Only $$$a_i$$$ and $$$a_j$$$ are XORed once.

We can also combine multiple operations on the same pair. The set of all four-bit values with even popcount is:

All of them are already valid masks except $$$5$$$ and $$$10$$$, and:

Thus, we can XOR any two chosen elements by any mask with even popcount.

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.

We now consider two cases.

Case 1: There is an element with odd popcount.

Choose one such element as a buffer.

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.

After this operation:

so $$$a_i$$$ becomes All-Meat. The buffer still has odd popcount because we only XOR it with even-popcount masks.

Therefore, every element with even popcount becomes All-Meat, while the elements with odd popcount cannot contribute to the answer anyway.

Case 2: All elements have even popcount.

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.

After these operations, the array has the form:

where:

Since all original elements have even popcount, $$$x$$$ also has even popcount. If $$$x$$$ is one of:

then every element is already All-Meat.

The only remaining possibilities are $$$x=5$$$ and $$$x=10$$$. In both cases, apply XOR with $$$3$$$ to the first two elements:

Again, every element becomes All-Meat.

Therefore, the upper bound is always achievable, and the answer is exactly:

For each update, we only need to remove the contribution of the old value and add the contribution of the new value.

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)$$$.

#include <bits/stdc++.h>
using namespace std;

inline bool good(int x) {
    return __builtin_popcount(x) % 2 == 0;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int tc;
    cin >> tc;

    while (tc--) {
        int n, q;
        cin >> n >> q;

        vector<int> a(n);
        int answer = 0;

        for (int &x : a) {
            cin >> x;
            answer += good(x);
        }

        cout << answer;

        while (q--) {
            int p, x;
            cin >> p >> x;
            --p;

            answer -= good(a[p]);
            a[p] = x;
            answer += good(a[p]);

            cout << ' ' << answer;
        }

        cout << '\n';
    }

    return 0;
}

Define the prefix XORs of the original array as:

Suppose we choose an interval $$$[l,r]$$$, and let:

Bitwise AND distributes over XOR, so:

Therefore, the answer depends only on the XOR of two prefix endpoints and the maximum of the interval.

Cartesian tree

Build the maximum Cartesian tree of the original array $$$a$$$. Ties may be handled in any consistent way.

This tree has two useful properties:

• The subtree of every vertex $$$v$$$ corresponds to a continuous segment $$$[L_v,R_v]$$$.
• For every interval $$$[l,r]$$$:

Thus, if $$$v=\operatorname{LCA}(l,r)$$$, the value of the interval is:

Constructing the answer bit by bit

Suppose some higher bits of the answer have already been fixed, and we want to test a candidate mask $$$M$$$.

The candidate is feasible if there exists an interval whose value contains every bit of $$$M$$$.

For this check, define:

and its prefix XORs:

Equivalently:

For an interval whose Cartesian-tree LCA is $$$v$$$, all bits of $$$M$$$ occur in its value if and only if:

and:

The second condition can be rewritten as:

Therefore, after fixing one endpoint, we only need a frequency array to determine whether the required other endpoint exists.

Notice that the Cartesian tree is always built from the original values. Only the prefix XORs are masked during a feasibility check.

Processing one Cartesian-tree vertex

Suppose the subtree of $$$v$$$ corresponds to $$$[L,R]$$$.

Every interval whose LCA is exactly $$$v$$$ can be represented by two prefix endpoints:

We need to find a pair satisfying:

There is one important exception. The pair:

represents the interval $$$[v,v]$$$, which is forbidden because the statement requires $$$l \lt r$$$.

Moreover, whenever $$$a_v & M=M$$$, this pair automatically satisfies:

So failing to exclude this exact pair would produce a false positive at every suitable vertex.

Small-to-large traversal

For every processed subtree $$$[L,R]$$$, we maintain the following invariant:

The frequency array contains $$$s_L,s_{L+1},\ldots,s_R$$$.

At a vertex $$$v$$$:

1. Recursively check both child subtrees.
2. Keep the prefix XORs of the larger child in the frequency array.
3. Iterate over the endpoints belonging to the smaller side.
4. For every value $$$s_x$$$, check whether $$$s_x\oplus M$$$ exists on the other side.
5. Merge the smaller side into the frequency array.

The boundary prefix $$$s_{L-1}$$$ is inserted temporarily when needed.

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.

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.

One feasibility check takes:

There are $$$18$$$ bits, so the total time complexity is:

The memory complexity is:

The implementation below uses an explicit stack because a Cartesian tree can have depth $$$n$$$ for a sorted array.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
 
const int N = 2e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, a[N], par[lg][N], pref[N], cnt[N * 2], answ = 0, maxi = 0;
 
int getmx(int l, int r) {
    int res = l;
    for(int i=lg-1; i>=0; i--) {
        if(l + (1<<i) - 1 <= r) {
            res = (a[par[i][l]] > a[res] ? par[i][l] : res);
            l += (1<<i);
        }
    }
    return res;
}
 
void divide(int l, int r) {
    if(l > r) return;
    if(l == r) {
        cnt[pref[l]] ++;
        return;
    }
    if(l == r-1) {
        cnt[pref[l]] ++;
        cnt[pref[r]] ++;
        if((max(a[l], a[r]) & answ) == answ) {
            maxi = max(maxi, pref[l-1] ^ pref[r]);
        }
        return;
    }
 
    int mid = getmx(l, r);
 
    if(r-mid > mid-l) {
        divide(l, mid-1);
        for(int i=l; i<mid; i++) cnt[pref[i]] --;
        divide(mid+1, r);

        for(int i=mid-1; i>=l-1; i--) {
            if(cnt[(answ ^ pref[i])] > 0 && (a[mid]&answ) == answ) maxi = answ;
            if (i == mid-1) cnt[pref[mid]] ++;
        }
        for(int i=mid-1; i>=l; i--) cnt[pref[i]] ++;
    } else {
        divide(mid+1, r);
        for(int i=mid+1; i<=r; i++) cnt[pref[i]] --;
        divide(l, mid-1);
 
        cnt[pref[mid-1]] --;
        cnt[pref[l-1]] ++;
        for(int i=mid; i<=r; i++) {
            if(cnt[(answ ^ pref[i])] > 0  && (a[mid]&answ) == answ) maxi = answ;
            if(i == mid) cnt[pref[mid-1]] ++;
        }
        cnt[pref[l-1]] --;
 
        for(int i=mid; i<=r; i++) cnt[pref[i]] ++; 
    }
}
 
bool check() {
    maxi = 0;
    for(int j=1; j<=n; j++) {
        pref[j] = pref[j-1] ^ (a[j] & answ);
    }
 
    divide(1, n);
 
    for(int i=1; i<=n; i++) {
        cnt[pref[i]] = 0;
    }
 
    if(maxi == answ) return 1;
    return 0;
}
 
void work() {
    cin>>n;
 
    int mxtmp = 0, anstmp = 0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        mxtmp = max(mxtmp, a[i]);
        par[0][i] = i;
    }
 
    for(int i=1; i<=n; i++) anstmp ^= (a[i] & mxtmp);
 
    for(int i=n; i>=1; i--) {
        for(int j=1; j<lg; j++) {
            int x = par[j-1][i], y = par[j-1][min(n, i + (1<<(j-1)))];
            if(a[x] > a[y]) par[j][i] = x;
            else par[j][i] = y;
        }
    }
 
    for(int i=lg-1; i>=0; i--) {
        answ += (1 << i);
 
        if(check() == 0) {
            answ -= (1 << i);
        }
    }
 
    cout<<max(answ, anstmp)<<endl;
}
 
void reset_work() {
    answ = 0;
    for(int i=1; i<=n; i++) a[i] = 0, pref[i] = 0;
    return;
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
 
    // freopen("inp.txt", "r", stdin);
    // freopen("out-m.txt", "w", stdout);
 
 
    cin>>t;
    // t = 1;
    while(t --) {
        work();
        reset_work();
    }
 
    return 0;
}

AghaBalaSar (آقابالاسر) is a term commonly used in the Iranian CP community for the nearest greater/smaller element on either side.

I also used it in a previous contest as well :D 2127F - Hamed and AghaBalaSar

The important observation is that a shortest path has the form

So after at most one initial left move, all right moves are forced.

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.

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.

Let $$$dp_i$$$ be the sum of distances from $$$i$$$ to all positions in the current block.

Let $$$x$$$ be the rightmost position reachable from $$$i$$$ in at most two moves.

There are two cases.

Case 1: ($$$x=R[i]$$$)

Then there is no way to reach anything beyond $$$R_i$$$ in two moves.

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)$$$.

Now compare the contributions of $$$i$$$ and $$$R_i$$$.

• For $$$j \lt i$$$, both distances are $$$1$$$.
• For $$$j=i$$$, we gain $$$-1$$$.
• For $$$j \gt i$$$, the distance from (i) is exactly one larger than the corresponding distance from $$$R_i$$$.

The total difference simplifies to $$$dp_i-dp_{R_i}=r-i-1$$$. Thus

Where $$$r$$$ is the end of the current block.

Case 2: ($$$x \gt R_i$$$)

Now $$$x$$$ is reachable in two moves, and $$$x$$$ is the furthest position with this property.

For every $$$j \gt x$$$, $$$f(i,j)=2+f(x,j)$$$.

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.

Thus, for everything after $$$x$$$, we can simply use $$$dp_x$$$.

It remains to handle the positions between $$$i$$$ and $$$x$$$.

Since $$$x$$$ is reachable in at most two moves, every position $$$j\in(i,x]$$$ has distance either $$$2$$$ or $$$3$$$ from $$$i$$$.

Let $$$c_2$$$ be the number of $$$j \in (i,x]$$$ such that $$$f(i,j)=2$$$.

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

So the only remaining problem is computing $$$x$$$ and $$$c_2$$$ efficiently.

Finding the positions reachable in two moves

A position $$$j \gt i$$$ can be reached in two moves in exactly these ways:

• $$$i \lt j \lt R_i$$$, by $$$i\to R_i\to j$$$;
• $$$j=R_{R_i}$$$;
• There is some $$$k\le i$$$ such that $$$R_k=j$$$, because we can do $$$i\to k\to j$$$.

Let $$$L_j$$$ be the minimum $$$k$$$ such that $$$R_k = j$$$, then third case is simply $$$L_j\le i$$$.

We process $$$i$$$ from right to left and maintain all positions $$$j$$$ satisfying $$$L_j\le i$$$. The rightmost marked position is exactly $$$x$$$.

Computing $$$c_2$$$

Among the distance-$$$2$$$ positions we have:

• $$$R_i-i-1$$$ positions between $$$i$$$ and $$$R_i$$$;
• $$$R_{R_i}$$$, if it exists;
• all currently marked positions except $$$R_i$$$.

There is one possible double count: $$$R_{R_i}$$$ may itself already be marked.

So we can compute $$$c_2$$$ by processing $$$i$$$ from right to left and maintaining all marked positions.

Complexity: $$$\mathcal{O}(n)$$$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MXN = 1e6+5;

int n, p[MXN], R[MXN], L[MXN];
ll dp[MXN];
vector<int> vec[MXN];
bool mark[MXN];

void solve(int l, int r) {
    dp[r] = r-l;
    int lst=r, cnt=0;
    if(L[r]!=n+1) {
        vec[L[r]].push_back(r);
        mark[r] = 1;
        cnt++;        
    }
    for(int i=r-1; i>=l; i--) {
        while(!mark[lst]) lst--;
        if(lst==R[i]) {
            dp[i] = dp[R[i]] + r-l+1 - 2 - (i-l);
        }
        else {
            int c1 = i-l + 1;
            int c2 = R[i]-i-1 + (R[R[i]]!=n+1) + cnt - 1 - (R[R[i]]!=n+1 && L[R[R[i]]]<=i);
            dp[i] = dp[lst] + 2*(r-l+1) - 3 - 2*c1 - c2 + 1;
        }
        for(int j : vec[i])
            mark[j] = 0,
            cnt--;
        if(L[i]!=n+1) {
            vec[L[i]].push_back(i);
            mark[i] = 1;
            cnt++;
        }
    }

    for(int i=l; i<=r; i++)
        dp[i] += l-1;
}

void Main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> p[i];
        vec[i].clear();
        mark[i] = 0;
    }
    fill(L+1, L+n+1, n+1);
    for(int i=n; i>=1; i--) {
        for(R[i]=i+1; R[i]<=n && p[R[i]]<p[i]; R[i]=R[R[i]]);
        L[R[i]] = i;
    }
    int l=1;
    for(int r=1; r<=n; r++)
        if(R[r]==n+1) {
            solve(l, r);
            l = r+1;
        }
    ll ans = 0;
    for(int i=1; i<=n; i++)
        ans += dp[i];
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) Main();
    return 0;
}

Let $$$C_m$$$ be the $$$m$$$-th Catalan number:

The recursive construction in the statement generates exactly the binary trees whose inorder traversal is:

Therefore, there are $$$C_n$$$ valid trees.

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.

Now fix a proper subarray $$$[L,R]$$$ of length $$$l$$$.

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.

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.

Therefore, a fixed subarray of length $$$l$$$ appears as the child subtree of an edge in exactly:

valid trees.

Let:

For a subarray $$$I$$$, let its XOR be $$$X_I$$$. Cutting the edge above this subtree produces two components with XOR values:

Thus, the whole answer can be written as:

We calculate this sum bit by bit.

Fix a bit $$$b$$$.

Case 1: Bit $$$b$$$ of $$$S$$$ is set.

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.

There are $$$C_n$$$ trees, and every tree has $$$n-1$$$ edges. Hence, before multiplying by $$$2^b$$$, the contribution is:

Case 2: Bit $$$b$$$ of $$$S$$$ is not set.

In this case, the two component XORs have the same value at bit $$$b$$$.

• If bit $$$b$$$ of $$$X_I$$$ is zero, the edge contributes zero.
• If bit $$$b$$$ of $$$X_I$$$ is one, both components contribute this bit, so the edge contributes twice.

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:

It remains to calculate every $$$D_l$$$.

Define the prefix XORs:

The XOR of a subarray of length $$$l$$$ starting after position $$$i$$$ is:

Define:

The required subarray has bit $$$b$$$ set exactly when $$$s_i$$$ and $$$s_{i+l}$$$ are different.

Consider:

Equal pairs contribute $$$1$$$, while different pairs contribute $$$-1$$$. Since there are $$$n+1-l$$$ pairs in total:

Therefore:

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:

With a transform of size $$$N$$$, the index $$$-k$$$ is represented by $$$(N-k)\bmod N$$$.

A direct implementation could perform an inverse NTT and obtain every $$$R_l$$$. However, we only need their weighted sum.

Let:

for $$$1\leq l \lt n$$$, and let $$$W_k$$$ be the NTT of $$$w$$$. Using Parseval's identity:

Also:

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.

Therefore, we need one NTT for the weights and at most one NTT for each of the $$$18$$$ bits.

The total time complexity is:

and the memory complexity is $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
using i64 = long long;
 
const int mod = 998244353;
const int G = 3;
const int B = 18;
const int N = 200000;
 
int qpow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1) r = (i64)r * a % mod;
        a = (i64)a * a % mod;
        b >>= 1;
    }
    return r;
}
 
struct NTT {
    int n;
    vector<int> rev, roots;
 
    NTT(int n) : n(n), rev(n), roots(n) {
        for (int i = 1; i < n; i++) {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
        }
 
        for (int len = 1; len < n; len <<= 1) {
            int z = qpow(G, (mod - 1) / (len << 1));
            roots[len] = 1;
            for (int i = 1; i < len; i++) {
                roots[len + i] = (i64)roots[len + i - 1] * z % mod;
            }
        }
    }
 
    void transform(vector<int>& a) const {
        for (int i = 0; i < n; i++) {
            if (i < rev[i]) swap(a[i], a[rev[i]]);
        }
 
        for (int len = 1; len < n; len <<= 1) {
            for (int i = 0; i < n; i += len << 1) {
                for (int j = 0; j < len; j++) {
                    int x = a[i + j];
                    int y = (i64)a[i + j + len] * roots[len + j] % mod;
 
                    a[i + j] = x + y;
                    if (a[i + j] >= mod) a[i + j] -= mod;
 
                    a[i + j + len] = x - y;
                    if (a[i + j + len] < 0) a[i + j + len] += mod;
                }
            }
        }
    }
};
 
vector<int> fac(2 * N + 1);
vector<int> ifac(2 * N + 1);
vector<int> catalan(N + 1);
 
void init() {
    fac[0] = 1;
    for (int i = 1; i <= 2 * N; i++) {
        fac[i] = (i64)fac[i - 1] * i % mod;
    }
 
    ifac[2 * N] = qpow(fac[2 * N], mod - 2);
    for (int i = 2 * N; i >= 1; i--) {
        ifac[i - 1] = (i64)ifac[i] * i % mod;
    }
 
    for (int i = 0; i <= N; i++) {
        catalan[i] = (i64)fac[2 * i] * ifac[i] % mod
                   * ifac[i + 1] % mod;
    }
}
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n), pref(n + 1);
    for (int& x : a) cin >> x;
 
    if (n == 1) {
        cout << 0 << '\n';
        return;
    }
 
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] ^ a[i - 1];
    }
 
    vector<int> weight(n);
    int W = 0;
 
    for (int d = 1; d < n; d++) {
        weight[d] = (i64)catalan[d] * catalan[n - d] % mod;
        W = (W + (i64)(n - d + 1) * weight[d]) % mod;
    }
 
    int len = 1;
    while (len < 2 * (n + 1)) len <<= 1;
 
    NTT ntt(len);
 
    vector<int> kernel(len);
    for (int d = 1; d < n; d++) {
        kernel[d] = weight[d];
        kernel[len - d] = weight[d];
    }
 
    ntt.transform(kernel);
 
    int answer = (i64)((1 << B) - 1) * W % mod;
    int inv_len = qpow(len, mod - 2);
    int inv_two = (mod + 1) / 2;
    int total_xor = pref[n];
 
    vector<int> seq(len);
 
    for (int b = 0; b < B; b++) {
        if ((total_xor >> b) & 1) continue;
 
        fill(seq.begin(), seq.end(), 0);
 
        for (int i = 0; i <= n; i++) {
            seq[i] = ((pref[i] >> b) & 1) ? mod - 1 : 1;
        }
 
        ntt.transform(seq);
 
        int spectral_sum = 0;
 
        for (int k = 0; k < len; k++) {
            int opposite = (len - k) & (len - 1);
 
            int term = (i64)kernel[k] * seq[k] % mod
                     * seq[opposite] % mod;
 
            spectral_sum += term;
            if (spectral_sum >= mod) spectral_sum -= mod;
        }
 
        int Q = (i64)spectral_sum * inv_len % mod * inv_two % mod;
 
        answer -= (i64)(1 << b) * Q % mod;
        if (answer < 0) answer += mod;
    }
 
    cout << answer << '\n';
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    init();
 
    int T;
    cin >> T;
 
    while (T--) solve();
}

First, consider the parity of the total number of inversions in all columns.

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.

In the final grid every column is sorted, so the total number of inversions is $$$0$$$, which is even.

Therefore, if the initial total number of inversions is odd, the answer is immediately $$$-1$$$.

Now assume it is even.

We process

Our goal at step $$$x$$$ is to put every occurrence of $$$x$$$ into row $$$x$$$.

Pair the columns:

For each pair, look at its two cells in row $$$x$$$.

There are four possibilities:

• Type $$$0$$$: neither cell contains $$$x$$$;
• Type $$$L$$$: only the left cell contains $$$x$$$;
• Type $$$R$$$: only the right cell contains $$$x$$$;
• Type $$$1$$$: both cells contain $$$x$$$.

Our goal is to make every pair Type $$$1$$$. Once this happens, all $$$2n$$$ copies of $$$x$$$ are in row $$$x$$$.

For each $$$x=1,2,\ldots,2n-2$$$, we proceed through the following steps:

1. Consider only the pairs $$$2,3,\ldots,n-1$$$. The first and last pairs will be handled separately.

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$$$.

3. While there is a Type $$$L$$$ pair, take the leftmost one, say pair $$$i$$$:
     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$$$.
     3.2. If pair $$$i+1$$$ is Type $$$R$$$, leave this Type $$$L$$$ pair for later.

4. While there is a Type $$$R$$$ pair, take the rightmost one, say pair $$$i$$$:
     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.
     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$$$.

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$$$.

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).

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.

Number of operations

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)$$$.

The first and last pairs require at most $$$2$$$ additional operations for each $$$x$$$, contributing $$$2\cdot2(2n-2)$$$.

Finally, the $$$x=2n-1$$$ case costs at most $$$n-1$$$ additional operations.

Hence the total is at most

The main sum is

Therefore,

So the required bound is satisfied.

The construction also gives the actual sequence of operations if we implement the described moves.

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int, int>;
 
const int MXN = 202;
 
int n, n2, a[MXN][MXN];
vector<pii> ans;
 
inline void opr(int i, int j) {
    swap(a[i][j], a[i+1][j]);
    swap(a[i][j+1], a[i+1][j+1]);
    ans.push_back({i, j});
}
 
inline int wh(int x, int j) {
    for(int i=x; i<=n2; i++)
        if(a[i][j]==x)
            return i;
    assert(0);        
    return -1;
}
 
inline void R(int x, int j) {
    for(int i=wh(x, j+1)-1; i>=x; i--) opr(i, j+1);
}
 
inline void RL(int x, int j) {
    int pos1 = wh(x, j+1), pos2 = wh(x, j+2);
    while(pos1>pos2) opr(--pos1, j);
    while(pos1<pos2) opr(--pos2, j+2);
    while(pos1>x) opr(--pos1, j+1);
}
 
inline void L(int x, int j) {
    for(int i=wh(x, j)-1; i>=x; i--) opr(i, j-1);
}
 
inline void L1(int x, int j) {
    if(a[x+1][j]==x) opr(x+1, j); // extra, we can ignore it for x<=2n-3
    opr(x, j-1); // extra, we can ignore it
    for(int i=wh(x, j)-1; i>=x+1; i--) opr(i, j);
    opr(x, j-1);
}
 
inline void solve0(int x, int j) {
    int pos1=wh(x, j), pos2=wh(x, j+1);
    while(pos1>pos2) opr(--pos1, j-1);
    while(pos1<pos2) opr(--pos2, j+1);
    while(pos1>x) opr(--pos1, j);
}
 
inline void lft(int x) { // 2 extra
    if(a[x][2]==x) {
        if(a[x][1]==x) return;
        if(a[x+1][1]==x) opr(x+1, 1);
        opr(x, 1);
    }
    else if(a[x][1]==x) {
        if(a[x+1][2]==x) opr(x+1, 1);
        opr(x, 1);
    }
 
    int pos1=wh(x, 1), pos2=wh(x, 2);
    if(pos1>pos2) {
        while(pos1>pos2) opr(--pos1, 1);
        pos2++;
    }
    while(pos1<pos2) opr(--pos2, 2);
    while(pos1>x) opr(--pos1, 1);
}
 
inline void rgt(int x) { // 2 extra
    if(a[x][n2-1]==x) {
        if(a[x][n2]==x) return;
        if(a[x+1][n2]==x) opr(x+1, n2-1);
        opr(x, n2-1);
    }
    else if(a[x][n2]==x) {
        if(a[x+1][n2-1]==x) opr(x+1, n2-1);
        opr(x, n2-1);
    }
 
    int pos1=wh(x, n2-1), pos2=wh(x, n2);
    if(pos1<pos2) {
        while(pos1<pos2) opr(--pos2, n2-1);
        pos1++;
    }
    while(pos1>pos2) opr(--pos1, n2-2);
    while(pos1>x) opr(--pos1, n2-1);
}
 
 
inline void lst() { // 2n-1 extra
    for(int j=1; j<=n2-1; j++)
        if(a[n2][j]!=n2) opr(n2-1, j);
}
 
inline void print() {
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
    ans.clear();
}
 
void Main() {
    cin >> n;
    n2 = n<<1;
    for(int i=1; i<=n2; i++)
        for(int j=1; j<=n2; j++)
            cin >> a[i][j];
    int inv = 0;
    for(int j=1; j<=n2; j++)
        for(int i1=1; i1<=n2; i1++)
            for(int i2=i1+1; i2<=n2; i2++)
                inv ^= a[i1][j]>a[i2][j];
    if(inv) {
        cout << "-1\n";
        return;
    }
    if(n==1) {
        if(a[1][1]==2) cout << "1\n1 1\n";
        else cout << "0\n";
        return;
    }
    for(int x=1; x<=n2-2; x++) {
        for(int j=3; j<=n2-3; j+=2)
            if(a[x][j]==x && a[x][j+1]==x) opr(x, j);
        for(int j=3; j<=n2-3; j+=2)
            if(a[x][j]==x && a[x][j+1]!=x) {
                if(j==n2-3 || a[x][j+3]!=x) R(x, j);
                else RL(x, j);
            }
        for(int j=n2-3; j>=3; j-=2)
            if(a[x][j]!=x && a[x][j+1]==x) {
                if(a[x][j-2]==x && a[x][j-1]==x) L1(x, j);
                else L(x, j);
            }
        for(int j=3; j<=n2-3; j+=2)
            if(a[x][j]!=x)
                solve0(x, j);
        lft(x);
        rgt(x);
    }
    lst();
    print();
}
 
int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int tc;
    cin >> tc;
    while(tc--) Main();
    return 0;
}

Can you improve the construction and reduce the number of operations below $$$n\binom{2n}{2} + 9n$$$ ?