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

The first thing to realize is that if the first $$$p$$$ elements of the array are determined, the rest will be unique ($$$a_i = a_{i-p}$$$ to hold the sum). If $$$p$$$ divides $$$n$$$, there will be $$$\frac{n}{p}$$$ blocks, each summing to $$$q$$$, so their total sum which is $$$q\cdot \frac{n}{p}$$$ should be equal to $$$m$$$. If not, the incomplete block that is created at the end can be used to cover any difference in sum, so it's always possible!

t = int(input())

for _ in range(t):
    n, m, p, q = map(int, input().split())
    
    if n % p == 0 and (n // p) * q != m:
        print("NO")
    else:
        print("YES")

This problem was supposed to be for cyclic arrays, and also required construction, but due to D2A difficulty it was adjusted!

Do you have a solution for the cyclic array version? Comment it below

Before starting, we take the absolute value of all elements since their signs do not matter. Then, if the first element of the array is equal to or smaller than the $$$\left\lfloor \frac{n}{2}\right\rfloor + 1$$$ smallest element of the array, the answer is possible. Else, it is impossible. The proof is as follows:

• If the first element is equal to or smaller than the $$$\left\lceil\frac{n}{2}\right\rceil$$$ smallest element of the array, we can negate the big values until the first element becomes the $$$\left\lceil\frac{n}{2}\right\rceil$$$ smallest element of the array, hence becoming the median.

• If the first element is equal to the $$$\left\lfloor \frac{n}{2}\right\rfloor + 1$$$ smallest element of the array, we can negate the entire array, which results in the first element becoming the $$$\left\lceil\frac{n}{2}\right\rceil$$$ smallest element of the array.

• Otherwise, if the first element of the array is larger than the $$$\left\lfloor \frac{n}{2}\right\rfloor + 1$$$ smallest element of the array, negating values smaller than it has no effect, while negating values larger than it just makes the first element further away from the median position. You can verify that negating the first element itself does not help either by using similar cases.

t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    pairs = [(abs(a[i]), i) for i in range(n)]
    pairs.sort()
    
    ans = [0] * n
    
    for i in range(n // 2 + 1):
        _, index = pairs[i]
        ans[index] = 1
    
    if ans[0]:
        print("YES")
    else:
        print("NO")

Would it be easier to calculate the answer for all indices and just output for the first index?

What's up with the name of the problem?

The first fact to notice is that if the subgrid does not contain $$$0$$$, then the MEX is $$$0$$$ and we can ignore such subgrids. If the MEX is going to be $$$k$$$, it means all the values from $$$0$$$ to $$$k-1$$$ are included in the subgrid. For each $$$0\le k\le n^2$$$, we count how many subgrids have a MEX of at least $$$k$$$, aiming to maximize this.
To find the total sum of all MEX values, for each $$$k$$$ we count the number of subgrids that contain all the values from $$$0$$$ to $$$k-1$$$. Summing these counts gives us the final result.

We claim that if our subgrid is nearly square (either a perfect square or a difference of $$$1$$$ in lengths), and is placed in the middle of the grid, then the answer is maximized.

Proof: The multiplication of two numbers with the same sum is maximized when they are as close to each other as possible. Therefore, for each subgrid, if we consider the empty rows above and below it and separately consider the columns on its right and left, if one is fixed, the place is optimized to be in the middle. Now, similarly, we can say that it is optimal if the length and height of the subgrid are close to each other as well, as increasing one will cause the other one to decrease. With these two observations combined, a subgrid having the above properties is optimal when it's a nearly square subgrid in the middle of the grid.

Any ordering with this property works; an easy example is a spiral shape that starts from the center of the grid and turns around itself.

def magical_spiral(n):
    arr = [[-1] * n for _ in range(n)]
    
    if n % 2 == 0:
        x, y = n // 2 - 1, n // 2 - 1
    else:
        x, y = n // 2, n // 2
    
    arr[x][y] = 0
    value = step = 1

    dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]


    while value < n * n:
        for d in range(4):
            steps = step
            
            step += d % 2; dx, dy = dir[d]

            for _ in range(steps):
                x += dx; y += dy

                if 0 <= x < n and 0 <= y < n and arr[x][y] == -1:
                    arr[x][y] = value
                    value += 1
                if value >= n * n:
                    break
            
            if value >= n * n:
                break


    for row in arr:
        print(" ".join(str(num) for num in row))
    print()


t = int(input())

for _ in range(t):
    n = int(input())

    magical_spiral(n)

We had the idea of dividing this problem into two subtasks, in which the second subtask requires you to count the sum of MEX of all subgrids!

Do you have a solution for this? Comment it below

The first observation is that the parity of the position of the elements doesn't change with the operations. Thus, if an element is at an odd or even index in the initial permutation, it will retain the same parity in the final permutation. As long as we have four elements left, we can freely adjust them within their index parity zone, but what about the last three ones? We can see that the parity of the number of inversions is fixed, so by counting the inversions of the initial permutation, the order of the last four elements will be uniquely determined.

#include <bits/stdc++.h>

#define pb push_back
#define int long long 
#define F first
#define S second
#define sz(a) (int)a.size()
#define pii pair<int,int> 
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define all(a) a.begin(),a.end() 

using namespace std ;
const int maxn = 1e6 + 10 ;
int a[maxn] , n , fen[maxn] ; 

void upd(int x){
    while(x <= n){
        fen[x]++;
        x += x&-x;
    }
}

int que(int x){
    int ans =0 ;
    while(x){
        ans += fen[x] ;
        x -= x&-x;
    }
    return ans ; 
}

int f(vector<int> x){
    rep(i , 0, n)fen[i] =0;
    int ans =0 ;
    per(i , sz(x)-1 , 0){
        ans += que(x[i]);
        upd(x[i]) ;
    }
    
    return ans ; 
}

signed main(){
    ios::sync_with_stdio(0) ; cin.tie(0);
    
    int T ;
    cin >> T ;
    
    while(T--){
        vector <int> a1 , a2 ; 
        
        cin >> n ;
        rep(i ,1 ,n){
            int x; cin >> x; 
            
            if (i%2==1) {
                a1.pb(x);
            } else {
                a2.pb(x);
            }
        }    
        
        bool v = (f(a1)%2 != f(a2)%2);
        
        sort(all(a1)); sort(all(a2));
        
        int x1 = 0, x2 =0;    
        
        rep (i ,1 , n) {
            if (i%2==1) {
                a[i] = a1[x1] ; x1++; 
            } else {
                a[i] = a2[x2] ; x2++;
            }
        }
        
        if (v) {
            swap(a[n] , a[n-2]) ;
        }
        
        rep(i ,1 ,n) cout << a[i] << " ";
        cout << "\n";
    }
}

This problem was one of the first problems that we had, and the intended constraits were $$$n\le 3000$$$ as a D1A, but later was moved to D1B with $$$n\le 2\cdot 10^5$$$!

Do you know how to count the parity of inversions without counting the number of inversions?

The first observation is that we only care about the first and last occurrences of each number in the final array, as anything in between doesn't change the maximum distance. Instead of counting the distances directly, the main idea of this problem is to break them down into pieces. For example, the distance of a pair $$$(i, j)$$$ such that $$$1\le i \lt j\le n$$$ and $$$a_i = a_j$$$ and also these indices are the farthest possible, instead of adding up $$$j-i$$$, we count one for each index in between $$$i$$$ and $$$j$$$. In Another word, for each index $$$i$$$, we count how many begins are in or before $$$i$$$, and how many ends are after $$$i$$$, adding up these values for each index gives us the sum of distances.

For each prefix and suffix of our array, we count the maximum number of different begins that we can get greedily. It can be proven that if we try to match each $$$a_i$$$ with the biggest unmatched number left, we'll end up getting the maximum number of different matches possible. Doing so can be calculated in many different ways, one using sets is shown in the implementation below.

After that, for each $$$1\le i \lt n$$$, we have a bound for the number of pairs that these indices can be in between of, as we calculated the maximum distinct matches possible for both sides (one prefix and one suffix). It can be proven that there exists an array $$$b$$$ meeting the problem conditions such that the bound for each index is held, and therefore summing up all values gives us the final answer.

#include <bits/stdc++.h>

#define int long long

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")


#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;


const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;

int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, p, q, ans, flag;
int arr[MAXN], f[MAXN][2];
set<int> st;


void solve() {
    cin >> n;

    for (int i=1; i<=n; i++) cin >> arr[i];

    for (int j=0; j<2; j++) {
        st.clear();
        for (int i=1; i<=n; i++) st.insert(i);

        for (int i=(j? n : 1); (j?i>1 : i<n); (j? i-- : i++)) {
            auto it = st.upper_bound(arr[i]);

            if (it != st.begin()) it--, st.erase(*it);

            f[i][j] = n-st.size();
        }
    }
    
    ans = 0;
    for (int i=1; i<n; i++) ans += min(f[i][0], f[i+1][1]);

    cout << ans << endl;
}

int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> t;

    while (t--) solve();


    return 0;
}

We thought every greedy approach for this problem is wrong, and the intended solution used to be a $$$O(n^3)$$$ DP, but later realized we were wrong!

Can you think of a rational DP idea that despite the time limit can solve this question?

The first observation is that a subarray is cute, iff there is an index $$$i$$$, such that it is the one and only share of the LIS and LDS, and all other elements belong to either LIS or LDS.

Proof: We know that there cannot be two elements belonging to both LIS and LDS, and if there is none, the property won't be held. Therefore, we conclude that there is exactly one element shared between the LIS and LDS.

Diving deeper into the shared element, we can see that the smaller elements before it must all be ascending, and the bigger elements after it must also all be ascending (as this will make our LIS). Similarly, all the bigger elements before it and all the smaller elements after it should be descending. This gives us a good pattern, and we can easily see that any subarray included within a cute subarray is cute itself (call this monotonic property).

For counting the total number of cute subarrays, we calculate the values of $$$R_i$$$ and $$$L_i$$$ for each index. Let $$$L_i$$$ be the biggest index before $$$i$$$, such that the condition above is met. Similarly define $$$R_i$$$ as the $$$smallest$$$ index after $$$i$$$. If we can somehow calculate this values for all indices, then we'll end up with $$$n$$$ segments (for each $$$1\le i\le n$$$), and a subarray is cute iff it's included in at least one segment. This is a very classic problem, so the solution won't be discussed here.

The only detail left is how to calculate the values of $$$L_i$$$ and $$$R_i$$$? We'll discuss the process of calculating the $$$R_i$$$ here, but the $$$L_i$$$ follows a very similar pattern. We claim that $$$R_i = min(R_{i+1}, f(i))$$$. In here $$$f(i)$$$ is defined as follow:

• if $$$a_i \gt a_{i+1}$$$: then $$$f(i)$$$ is minimum index $$$j$$$, such that $$$a_{i+1}\le a_j\le a_i$$$.
• if $$$a_i \lt a_{i+1}$$$: in this case $$$f(i)$$$ is minimum $$$j$$$ such that $$$a_i\le a_j\le a_{i+1}$$$.

Proof: The fact that $$$R_i\le R_{i+1}$$$ can easily be concluded from the fact thay cuteness is a monotonic property. Also going back to the conditions described above, we can see that $$$f(i)$$$ is basically the first index that will ruin our condition, so based on the definition of $$$R_i$$$, we can say that $$$R_i = min(R_{i+1}, f(i))$$$.

The calculation of $$$L_i$$$ and $$$R_i$$$ can both be implemented using a Segment Tree or a Monotonic Stack; both implementations are included below. After we have those values, we count the number of subarrays included in at least one segment, and that would be our final answer.

We ended up having two D1D difficulty problems, but in the end chose this one as it was more cute!

We believe this was one of the cleanest problems we had. However, both the statement and solution made it look too classic, so we had a hard time making sure this idea had not been used elsewhere!

Do you have a different approach than ours? Tell us in the comments.

The length of each two nodes in a tree is always less than the number of nodes, and therefore the maximum weight that we can see in our constructed graph has an upper bound of $$$n-1$$$. Because the weight of any nice path is doubled every time, the maximum length of any nice path won't exceed $$$log_2(n)$$$.

The next observation is that we cannot see any node twice in a nice path (in other words, there are no cycles).

Proof: Let's assume that a cycle exists. We know that the weight of each edge is always greater than the sum of all previous edges, so even without any waste, $$$\sum_{i=0}^{k} 2^i \lt 2^{k+1}$$$. This tells us no matter how far we get, because we're taking more steps in the last edge than the sum of all previous ones, we can never end up in the first node. Therefore, every nice path is a simple path, and no cycles can be made.

Now, let's define $$$dp_{i, j}$$$ as the maximum weight of any edge to start a simple path from vertex $$$j$$$ and take $$$i$$$ steps, and $$$0$$$ if not possible. The idea here is to build the nicest path reversly, from the end to the beginning. We can update this $$$dp$$$ and build the paths backwards, and this will give us an $$$O(n^2\cdot log(n))$$$ solution as $$$i\le log_2(n)$$$.

To optimize this, we use the suffix trick on centroid decomposition and keep the maximum two suffixes every time, to update $$$dp_{i, ?}$$$ in increasing order of $$$i$$$ accordingly. This would result in a $$$O(n\cdot log(n)^3)$$$ implementation, which can be further optimized to $$$O(n\cdot log(n)^2)$$$ using the fact that we can use counting sort for sorting as we have an upper bound of $$$n$$$. Both implementations are included below.

We aimed to kill $$$log(n)^3$$$ implementations but then ended up making some correct $$$log(n)^2$$$ ones TLE, and gave up!

What was your favorite part about this problem? Comment it below.

Note: For the purpose of this editorial, the diameter of a colored tree is defined as a simple path with maximum coolness which has a blue and red node on each side.

Let's say a node is special iff the distance of the farthest blue node from it plus the distance of the farthesrt red node is equal to the length of the diameter of the tree. We also define a special edge as an edge such that the distances of the farthes red nodes on both sides are equal, and the distances of the blue nodes on each side are also equal to each other. Something like this:

We can see that the sum of distances of the farthest blue and green plus one is the length of the diameter. We claim that if there is no special node in a colored tree, then there must be a special edge.

Proof: If there is no special node in a tree, then that means the farthest red and blue node for each vertex are on one side of it. We know that if there is at least one blue and one red colored node, then we have a valid diameter, so considering each node on that diameter, becuase it is not a special node the farthest blue and red of it must be on one side, and this leasds us towards a speical edge, the formal proof is described later when discussing $$$T'$$$.

Let's make some more observations. It's easy to see that the diameter of a tree is not necessarily unique, but an interesting fact is that every two valid diameters must intersect with each other.

Proof: if not, consider the tree is rooted from the blue/red node of one diameter, this would trivially show us a new blue and red node that has a distance longer than our current diameter and therefore a contradiction.

This gives us the idea that the intersection of all valid diameters is a non-empty simple path on the tree.

Proof: Consider two diameters and take their intersection, then add the rest one by one and take the intersection of the intersections. If there are any two pairs with intersections that do not intersect, this means there exists a pair of valid diameters which do not intersect with each other, and this is against our hypothesis.

Before continuing, you must have an idea so far that we are aiming to count the trees with special node based on their node, and others based on their special edge, but there is still a lot to discuss.

Going back to the special nodes, it's easy to see that they must must be on our diameter, and what makes this more interesting is that they must be on all diameters! So, taking the simple path that was the intersection of all valid diameters, we know that all of our special nodes lie on this path.

Getting deeper on special nodes, we can see that for a non-special node such as $$$v$$$, the farthest blue and red are both on the same subtree if we root the tree from $$$v$$$. This makes the sum of distances to farthest red plus the farthest blue result in a number always bigger than the actual length of our diameter (as there is a shared part). Call the child in which both the farthest red and blue lie on a cool child.

Let's create another graph based on our tree (call it $$$T'$$$) that has identical nodes to the tree, and directed edges. For each non-special node, give a directed edge from the identical vertex in $$$T'$$$ to its cool child. It's easy to see that special nodes would not have any incoming edges to them in this new graph, but every non-special node has at least one.

We can use this graph to formally prove almost everything. Let's start with the fact that why any tree without a special node has a special edge?

Proof: No special edge means that there are $$$n$$$ nodes in our tree that each have an outgoing edge, therefore $$$n$$$ directed edges as well. Our initial tree had only $$$n-1$$$ edge, so therefore based on the pigeonhole principle, there must be an edge in the initial tree, that two directed edges pass above it. It's trivial that those edges cannot have the same direction, and therefore this will lead us to a directed cycle of length two. Well, think about it, this is exactly what a special edge is!

So if no special node is there, now we know that there is at least one special edge there somewhere. Well, it appears that we also cannot have more than one special edge in a colored tree.

Proof: If so, we know that both of them must appear on the diameter, and considering their placement, this will contradict the fact that the distance of red and blue from both sides must be equal.

Combining both above observations, now we know that if there is no special node in the colored tree, then there is exactly one special edge there somewhere.

Now let's solve the first sub-problem, which is how to solve the problem if there is no special node. Define $$$f(v, a, b)$$$ for a node $$$v$$$ as the number of colourings which the farthest blue has a distance of $$$a$$$, and the farthest red has a distance of $$$b$$$. How to calculate $$$f$$$? Define $$$g(v, a, b)$$$ as the same thing, but this time for the distance of at most $$$a$$$ for blue and at most $$$b$$$ for red. It's easy to see that if we somehow calculate $$$g(v, a, b)$$$, then the following equation holds: \begin{equation} f(v, a, b) = g(v, a, b) — g(v, a-1, b) — g(v, a, b-1) + g(v, a-1, b-1) \end{equation} And here's how we find $$$g(v, a, b)$$$:

\begin{equation} g(v, a, b) = 3^{p\cdot q}\cdot 1^r \end{equation} Where $$$p$$$ is the number of nodes such as $$$u$$$ that have a distance less than or equal to $$$a$$$, $$$q$$$ is the number of nodes that have a distance bigger than $$$a$$$ but less than or equal to $$$b$$$, and $$$r$$$ is the number of nodes that have a distance more than $$$b$$$. Formally:

This will so far give us an $$$O(n^3)$$$ solution, dw we'll optimize it further later. Now we count the result for each edge of the tree, considering it will be a special edge in some colourings. Call both sides of the edge $$$u$$$ and $$$v$$$ just like the diagram shown above. Assuming we have $$$f$$$ calculated for all nodes, the answer is: \begin{equation} \sum_{a=0}^{n} \sum_{b=0}^{n} f(u, a, b) \cdot f(v, a, b) \cdot (a + b + 1) \end{equation} We're halfway there! Before the optimizing part, the only question left is what if there is a special node?

Let's define a super-special node a node that is special, and not only does it have the farthest blue and red on different sides, but also either a blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red.

Using the same observations that we made earlier and a deeper understanding of $$$T'$$$, you can prove that there is at least one super-special node, also at most one super-special node, and therefore always exactly one super-special node if there exists at least one special node. For such trees, we aim to calculate the answer for them based on their super-special node.

Make the tree rooted from an arbitrary node. Define $$$dp_{v, i, a, b, j}$$$ as if you're in vertext $$$v$$$, you iterated $$$i$$$ children, so far the farthest blue node has a distance of $$$a$$$, the farthest red node has a distance of $$$b$$$, and $$$j=0$$$ if these two don't belong to one subtree (if possible, preferably $$$0$$$), and $$$1$$$ otherwise. Iterate over new subtrees and use the $$$f$$$ function defined before to end up with a computable $$$O(n^4)$$$ implementation!

Now add another dimension $$$k$$$ to the above DP to keep track of if there is any blue node with distance one less than the farthest blue, or a red node with distance one less than the farthest red. Note that this really doesn't change anything.

The above DP, though correct, won't give us a good solution and is only explained for gaining deeper insight. After truly understanding what is going on and what we are looking for, we can break down the same idea and calculate it manually, which will result in a $$$O(n^2)$$$ solution in the end. The primary fact to notice is that if the number of edges between two farthest red vertices is even, then it can be proven that the middle vertex of this path is a special node, and if odd, the middle edge is a special edge. As explaining everything in detail takes forever, try to prove the things we missed yourself and ask if you encountered any issues.

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

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)>>1)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 998244353;
const int MXN = 3006;
const int LOG = 23;

template<typename T>
inline T md(T x) { return x &mdash; (x>=MOD ? MOD : 0); }
template<typename T>
inline void fix(T &x) { x = md(x); }

int n;
vector<int> g[MXN];
vector<int> H[MXN];
int cnt[MXN], pscnt[MXN];
ll red[MXN], redb[MXN];
ll two[MXN], thr[MXN], itwo[MXN];
ll ans;
ll ps[MXN];

void dfs(int v, int h=0, int p=-1) {
    cnt[h]++;
    H[h].back()++;
    for(int u : g[v])
        if(u!=p)
            dfs(u, h+1, v);
}

void Main() {
    cin >> n;
    for(int i=1; i<=n; i++) g[i].clear();
    ans = 0;
    for(int i=0, u,v; i<n-1; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int v=1; v<=n; v++) {
        for(int adj=-1; adj<SZ(g[v]); adj++) {
            for(int i=0; i<n; i++) H[i].clear(), cnt[i]=0;
            if(adj==-1) {
                cnt[0]++;
                for(int u : g[v]) {
                    for(int i=0; i<n; i++) H[i].pb(0);
                    dfs(u, 1, v);
                }
            }
            else {
                if(g[v][adj]<v) continue;
                for(int i=0; i<n; i++) H[i].pb(0);
                dfs(v, 0, g[v][adj]);
                for(int i=0; i<n; i++) H[i].pb(0);
                dfs(g[v][adj], 0, v);
            }
            pscnt[0] = cnt[0];
            for(int i=1; i<n; i++) pscnt[i] = pscnt[i-1] + cnt[i];
            red[0] = 1;
            redb[0] = 1;
            for(int i=1; i<n; i++) {
                red[i] = two[cnt[i]]-1;
                for(int a : H[i])
                    fix(red[i] += MOD-(two[a]-1));
                redb[i] = md(thr[cnt[i]]-two[cnt[i]]+MOD);
                for(int a : H[i])
                    fix(redb[i] += MOD-(thr[a]-two[a]+MOD)*two[cnt[i]-a]%MOD);
            }
            for(int i=0; i<n; i++) {
                ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD*(i+(adj!=-1))%MOD;
                if(i) fix(ps[i] += ps[i-1]);
            }
            for(int j=0; j<n; j++)
                fix(ans += thr[j==0?0:pscnt[j-1]]
                        *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD
                        *itwo[pscnt[j]]%MOD
                        *(ps[n-1]-ps[j]+MOD)%MOD);
            for(int i=0; i<n; i++) {
                ps[i] = red[i]*two[i==0?0:pscnt[i-1]]%MOD;
                if(i) fix(ps[i] += ps[i-1]);
            }
            for(int j=0; j<n; j++)
                fix(ans += thr[j==0?0:pscnt[j-1]]
                        *(thr[cnt[j]]-two[cnt[j]]+MOD)%MOD
                        *itwo[pscnt[j]]%MOD
                        *j%MOD
                        *(ps[n-1]-ps[j]+MOD)%MOD);
            for(int i=0; i<n; i++) {
                ps[i] = redb[i]
                        *thr[i==0?0:pscnt[i-1]]%MOD
                        *itwo[pscnt[i]]%MOD
                        *(i+(adj!=-1))%MOD;
                if(i) fix(ps[i] += ps[i-1]);
            }
            for(int j=1; j<n; j++)
                fix(ans += two[pscnt[j-1]]%MOD
                        *(two[cnt[j]]-1)%MOD
                        *ps[j-1]%MOD);
            for(int i=0; i<n; i++) {
                ps[i] = redb[i]
                        *thr[i==0?0:pscnt[i-1]]%MOD
                        *itwo[pscnt[i]]%MOD;
                if(i) fix(ps[i] += ps[i-1]);
            }
            for(int j=1; j<n; j++)
                fix(ans += two[pscnt[j-1]]%MOD
                        *(two[cnt[j]]-1)%MOD
                        *j%MOD
                        *ps[j-1]%MOD);
            for(int i=0; i<n; i++) {
                fix(ans += (redb[i]-red[i]+MOD)*thr[i==0?0:pscnt[i-1]]%MOD*(i+i+(adj!=-1))%MOD);
            }
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    cin >> T;
    two[0] = 1;
    for(int i=1; i<MXN; i++) two[i] = two[i-1]*2%MOD;
    thr[0] = 1;
    for(int i=1; i<MXN; i++) thr[i] = thr[i-1]*3%MOD;
    itwo[0] = 1;
    for(int i=1; i<MXN; i++) itwo[i] = itwo[i-1]*((MOD+1)/2)%MOD;
    while(T--) Main();
    return 0;
}

The intended solution was the $$$O(n^3)$$$ discussed with some further optimizations, but then a new $$$O(n^2)$$$ solution showed up that changed everything! We thought of dividing the problem into two subtasks, but didn't do so, as the observation required for the $$$O(n^2)$$$ solution was quite beautiful.

Also, we would like to thank Hamed_Ghaffari for his contributions to this problem.