The first tester tested on 10 October 2022.

When does the game end?

Depending on whether the player chooses to exchange wallets with their opponent on step $$$1$$$, $$$1$$$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.

The only way that the game ends is when both players have $$$0$$$ coins. Since each operation decreases the total amount of coins by exactly $$$1$$$, the only way for Alice to win the game is if $$$a + b$$$ is odd.

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

int main() {
    int t; cin >> t;
    while (t--) {
        int a, b; cin >> a >> b;
        if ((a + b) % 2 == 0) {
            cout << "Bob\n";
        } else {
            cout << "Alice\n";
        }
    }
}

Try to find a lower bound.

The answer is $$$|a_1 + a_2 + \ldots + a_n|$$$. Intuitively, whenever we have a subarray with a sum equal to $$$0$$$, it will be helpful for us as its penalty will become $$$0$$$. Hence, we can split $$$a$$$ into subarrays with a sum equal to $$$0$$$ and group up the remaining elements into individual subarrays of size $$$1$$$. A formal proof is given below.

Let us define an alternative penalty function $$$p2(l, r) = |a_l + a_{l+1} + \ldots + a_r|$$$. We can see that $$$p2(l, r) \le p(l, r)$$$ for all $$$1\le l\le r\le n$$$. Since the alternative penalty function does not have the $$$(r - l + 1)$$$ term, there is no reason for us to partition $$$a$$$ into two or more subarrays as $$$|x| + |y| \ge |x + y|$$$ for all integers $$$x$$$ and $$$y$$$, so the answer for the alternative penalty function is $$$|a_1 + a_2 + \ldots + a_n|$$$.

Since $$$p2(l, r)\le p(l, r)$$$, this means that the answer to our original problem cannot be smaller than $$$|a_1 + a_2 + \ldots + a_n|$$$. In fact, this lower bound is always achievable. Let us prove this by construction.

Note that if we flip every "$$$\mathtt{+}$$$" to "$$$\mathtt{-}$$$" and every "$$$\mathtt{-}$$$" to "$$$\mathtt{+}$$$", our answer will remain the same since our penalty function involves absolute values. Hence, we can assume that the sum of elements of $$$a$$$ is non-negative.

If the sum of elements of $$$a$$$ is $$$0$$$, we can split $$$a$$$ into a single array equal to itself $$$b_1 = a$$$ and obtain a penalty of $$$0$$$. Otherwise, we find the largest index $$$i$$$ where $$$a_1 + a_2 + \ldots + a_i = 0$$$. Then we let the first subarray be $$$b_1 = [a_1, a_2, \ldots, a_i]$$$ and the second subarray be $$$b_2 = [a_{i + 1}]$$$, so we have $$$p(b_1) = 0$$$ and $$$p(b_2) = 1$$$. Since $$$i$$$ is the largest index, $$$a_{i + 1}$$$ has to be equal to $$$1$$$ as if $$$a_{i + 1}$$$ is $$$-1$$$ instead, there has to be a larger index where the prefix sum becomes $$$0$$$ again for the prefix sum to go from negative to the final positive total sum. This means that for the remaining elements of the array $$$a_{i+2\ldots n}$$$, the sum of its elements decreases by $$$1$$$, so we can continue to use the same procedure to split the remaining elements which decrease the sum by $$$1$$$ and increase the penalty by $$$1$$$ each time until the sum of elements becomes $$$0$$$. Hence, the total penalty will be equal to the sum of elements of $$$a$$$.

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

int t;
int n;
string s;

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> s;
        int sm = 0;
        for (int i = 0; i < n; i++) {
            sm += s[i] == '+' ? 1 : -1;
        }
        cout << abs(sm) << '\n';
    }
}

Consider a greedy approach.

Consider the following approach. We start with empty arrays $$$b$$$ and $$$c$$$, then insert elements of the array $$$a$$$ one by one to the back of $$$b$$$ or $$$c$$$. Our penalty function only depends on adjacent elements, so at any point in time, we only care about the value of the last element of arrays $$$b$$$ and $$$c$$$. Suppose we already inserted $$$a_1, a_2, \ldots, a_{i - 1}$$$ into arrays $$$b$$$ and $$$c$$$ and we now want to insert $$$a_i$$$. Let $$$x$$$ and $$$y$$$ be the last element of arrays $$$b$$$ and $$$c$$$ respectively (if they are empty, use $$$\infty$$$). Note that swapping arrays $$$b$$$ and $$$c$$$ does not matter, so without loss of generality, assume that $$$x\le y$$$. We will use the following greedy approach.

1. If $$$a_i\le x$$$, insert $$$a_i$$$ to the back of the array with a smaller last element.
2. If $$$y < a_i$$$, insert $$$a_i$$$ to the back of the array with a smaller last element.
3. If $$$x < a_i\le y$$$, insert $$$a_i$$$ to the back of the array with a bigger last element.

The proof of why the greedy approach is optimal is given below:

1. $$$a_i\le x$$$. In this case, $$$a_i$$$ is not greater than the last element of both arrays, so inserting $$$a_i$$$ to the back of either array will not add additional penalties. However, it is better to insert $$$a_i$$$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
2. $$$y < a_i$$$. In this case, $$$a_i$$$ is greater than the last element of both arrays, so inserting $$$a_i$$$ to the back of either array will contribute to $$$1$$$ additional penalty. However, it is better to insert $$$a_i$$$ into the array with a smaller last element so that in the future, we can insert a wider range of values into the new array without additional penalty.
3. $$$x < a_i\le y$$$. In this case, if we insert $$$a_i$$$ to the back of the array with the larger last element, there will not be any additional penalty. However, if we insert $$$a_i$$$ to the back of the array with the smaller last element, there will be an additional penalty of $$$1$$$. The former option is always better than the latter. This is because if we consider making the same choices for the remaining elements $$$a_{i+1}$$$ to $$$a_n$$$ in both scenarios, there will be at most one time where the former scenario will add one penalty more than the latter scenario as the former scenario has a smaller last element after inserting $$$a_i$$$. After that happens, the back of the arrays in both scenarios will become the same and hence, the former case will never be less optimal.

Following the greedy approach for all 3 cases will result in a correct solution that runs in $$$O(n)$$$ time.

Consider a dynamic programming approach.

Let $$$dp_{i, v}$$$ represent the minimum penalty when we are considering splitting $$$a_{1\ldots i}$$$ into two subarrays where the last element of one subarray is $$$a_i$$$ while the last element of the second subarray is $$$v$$$.

Speed up the transition by storing the state in a segment tree.

Let us consider a dynamic programming solution. Let $$$dp_{i, v}$$$ represent the minimum penalty when we are considering splitting $$$a_{1\ldots i}$$$ into two subarrays where the last element of one subarray is $$$a_i$$$ while the last element of the second subarray is $$$v$$$. Then, our transition will be $$$dp_{i, v} = dp_{i - 1, v} + [a_{i - 1} < a_i]$$$ for all $$$1\le v\le n, v\neq a_{i - 1}$$$ and $$$dp_{i, a_{i - 1}} = \min(dp_{i - 1, a_{i - 1}} + [a_{i - 1} < a_i], \min_{1\le x\le n}(dp_{i - 1, x} + [x < a_i]))$$$.

To speed this up, we use a segment tree to store the value of $$$dp_{i - 1, p}$$$ at position $$$p$$$. To transition to $$$dp_i$$$, notice that the first transition is just a range increment on the entire range $$$[1, n]$$$ of the segment tree if $$$a_{i - 1} < a_i$$$. For the second transition, we can do two range minimum queries on ranges $$$[1, a_i - 1]$$$ and $$$[a_i, n]$$$. The final time complexity is $$$O(n\log n)$$$.

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

const int INF = 1000000005;
const int MAXN = 200005;

int t;
int n;
int a[MAXN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int t1 = INF, t2 = INF;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (t1 > t2) {
                swap(t1, t2);
            }
            if (a[i] <= t1) {
                t1 = a[i];
            } else if (a[i] <= t2) {
                t2 = a[i];
            } else {
                t1 = a[i];
                ans++;
            }
        }
        cout << ans << '\n';
    }
}

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

const int INF = 1000000005;
const int MAXN = 200005;

int t;
int n;
int a[MAXN];

int mn[MAXN * 4], lz[MAXN * 4];
void init(int u = 1, int lo = 1, int hi = n) {
    mn[u] = lz[u] = 0;
    if (lo != hi) {
        int mid = lo + hi >> 1;
        init(u << 1, lo, mid);
        init(u << 1 ^ 1, mid + 1, hi);
    }
}
void propo(int u) {
    if (lz[u] == 0) {
        return;
    }
    lz[u << 1] += lz[u];
    lz[u << 1 ^ 1] += lz[u];
    mn[u << 1] += lz[u];
    mn[u << 1 ^ 1] += lz[u];
    lz[u] = 0;
}
void incre(int s, int e, int x, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        mn[u] += x;
        lz[u] += x;
        return;
    }
    propo(u);
    int mid = lo + hi >> 1;
    if (s <= mid) {
        incre(s, e, x, u << 1, lo, mid);
    }
    if (e > mid) {
        incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    }
    mn[u] = min(mn[u << 1], mn[u << 1 ^ 1]);
}
int qmn(int s, int e, int u = 1, int lo = 1, int hi = n) {
    if (s > e) {
        return INF;
    }
    if (lo >= s && hi <= e) {
        return mn[u];
    }
    propo(u);
    int mid = lo + hi >> 1;
    int res = INF;
    if (s <= mid) {
        res = min(res, qmn(s, e, u << 1, lo, mid));
    }
    if (e > mid) {
        res = min(res, qmn(s, e, u << 1 ^ 1, mid + 1, hi));
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        init();
        for (int i = 1; i <= n; i++) {
            int ndp = min(qmn(1, a[i] - 1) + 1, qmn(a[i], n));
            if (i > 1) {
                if (a[i - 1] < a[i]) {
                    incre(1, n, 1);
                }
                int dp = qmn(a[i - 1], a[i - 1]);
                if (ndp < dp) {
                    incre(a[i - 1], a[i - 1], ndp - dp);
                }
            }
        }
        cout << qmn(1, n) << '\n';
    }
}

Solve the problem if you have to split the array into $$$k$$$ subsequences, where $$$k$$$ is given in the input ($$$k = 2$$$ for the original problem).

What does the distance of two leaves that share the same parent look like?

What happens if we delete two leaves that share the same parent?

Consider two leaves that share the same parent. They will be adjacent to each other in the dfs order, so their distances will be adjacent in array $$$a$$$. Furthermore, their distances to the root will differ by exactly $$$1$$$ since one of the edges from the parent to its children will have weight $$$0$$$ while the other will have weight $$$1$$$.

If we delete two leaves that share the same parent, the parent itself will become the leaf. Since one of the edges from the parent to the child has weight $$$0$$$, the distance from the parent to the root is equal to the smaller distance between its two children. This means that deleting two leaves that share the same parent is the same as selecting an index $$$i$$$ such that $$$a_i = a_{i - 1} + 1$$$ or $$$a_i = a_{i + 1} + 1$$$, then removing $$$a_i$$$ from array $$$a$$$.

Consider the largest value in $$$a$$$. If it is possible to delete it (meaning there is a value that is exactly one smaller than it to its left or right), we can delete it immediately. This is because keeping the largest value will not help to enable future operations as it can only help to delete elements that are $$$1$$$ greater than it, which is not possible for the largest value.

Now, all we have to do is to maintain all elements that can be deleted and choose the element with the largest value each time. Then, whenever we delete an element, we need to check whether the two adjacent elements become deletable and update accordingly. We can do this using a priority_queue and a linked list in $$$O(n\log n)$$$. Note that many other implementations exist, including several $$$O(n)$$$ solutions.

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

const int MAXN = 200005;

int n;
int a[MAXN];
int prv[MAXN],nxt[MAXN];
bool in[MAXN];

bool good(int i) {
    if (i < 1 || i > n) {
        return 0;
    }
    return a[prv[i]] == a[i] - 1 || a[nxt[i]] == a[i] - 1;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> n;
        priority_queue<pair<int, int>> pq;
        for (int i = 1; i <= n; i++) {
            prv[i] = i - 1;
            nxt[i] = i + 1;
            in[i] = 0;
            cin >> a[i];
        }
        a[n + 1] = a[0] = -2;
        for (int i = 1; i <= n; i++) {
            if (good(i)) {
                in[i] = 1;
                pq.push({a[i], i});
            }
        }
        while (!pq.empty()) {
            auto [_, i] = pq.top(); pq.pop();
            nxt[prv[i]] = nxt[i];
            prv[nxt[i]] = prv[i];
            if (!in[prv[i]] && good(prv[i])) {
                in[prv[i]]=1;
                pq.push({a[prv[i]], prv[i]});
            }
            if (!in[nxt[i]] && good(nxt[i])) {
                in[nxt[i]]=1;
                pq.push({a[nxt[i]], nxt[i]});
            }
        }
        int mn = n, bad = 0;
        for (int i = 1; i <= n; i++) {
            bad += !in[i];
            mn = min(a[i], mn);
        }
        if (bad == 1 && mn == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

Try solving the problem if the sum of elements of array $$$a$$$ is equal to $$$s$$$. If we can do this in $$$O(n)$$$ time, we can iterate through all possible values of $$$p_1 \le s \le p_n$$$ and sum up the number of ways for each possible sum.

Consider starting with array $$$a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$$$ where there are $$$p_n$$$ occurences of $$$1$$$ and $$$p_n - s$$$ occurrences of $$$-1$$$. Then, try inserting $$$(-1, 1)$$$ into the array to fix the number of occurrences of prefix sum starting from the largest value ($$$p_n$$$) to the smallest value ($$$p_1$$$).

Let us try to solve the problem if the sum of elements of array $$$a$$$ is equal to $$$s$$$. Consider starting array $$$a = [1, 1, \ldots, 1, -1, -1, \ldots, -1]$$$ where there are $$$p_n$$$ occurrences of $$$1$$$ and $$$p_n - s$$$ occurrences of $$$-1$$$. Notice that when we insert $$$(-1, 1)$$$ into array $$$a$$$ between positions $$$i$$$ and $$$i + 1$$$ where the sum of $$$a$$$ from $$$1$$$ to $$$i$$$ is $$$s$$$, two new prefix sums $$$s - 1$$$ and $$$s$$$ will be formed while the remaining prefix sums remain the same. Let us try to fix the prefix sums starting from the largest prefix sum to the smallest prefix sum.

In the starting array $$$a$$$, we only have $$$1$$$ occurrence of prefix sum with value $$$p_n$$$. We can insert $$$(-1, 1)$$$ right after it $$$k$$$ times to increase the number of occurrences of prefix sum with value $$$p_n$$$ by $$$k$$$. In the process of doing so, the number of occurrences of prefix sum with value $$$p_n - 1$$$ also increased by $$$k$$$. Now, we want to fix the number of occurrences of prefix sum with value $$$p_n - 1$$$. If we already have $$$x$$$ occurrences but we require $$$y > x$$$ occurrences, we can choose to insert $$$y - 1$$$ pairs of $$$(-1, 1)$$$ right after any of the $$$x$$$ occurrences. We can calculate the number of ways using stars and bars to obtain the formula $$$y - 1\choose y - x$$$.

We continue using a similar idea to fix the number of occurrences of $$$p_n - 2, p_n - 3, \ldots, p_1$$$, each time considering the additional occurrences that were contributed from the previous layer. Each layer can be calculated in $$$O(1)$$$ time after precomputing binomial coefficients, so the entire calculation to count the number of array $$$a$$$ whose sum is $$$s$$$ and has prefix sum consistent to the input takes $$$O(n)$$$ time. Then, we can iterate through all possible $$$p_1 \le s \le p_n$$$ and sum up the answers to obtain a solution that works in $$$O(n^2)$$$ time.

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

typedef long long ll;
const int INF = 1000000005;
const int MAXN = 200005;
const int MOD = 998244353;

ll fact[MAXN * 2], ifact[MAXN * 2];
int t;
int n;
int f[MAXN * 2], d[MAXN * 2];

inline ll ncr(int n, int r) {
    if (r < 0 || n < r) {
        return 0;
    }
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
// count number of a_1 + a_2 + ... + a_n = x
inline ll starbar(int n, int x) {
    if (n == 0 && x == 0) {
        return 1;
    }
    return ncr(x + n - 1, x);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < MAXN * 2; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    ifact[0] = ifact[1] = 1;
    for (int i = 2; i < MAXN * 2; i++) {
        ifact[i] = MOD - MOD / i * ifact[MOD % i] % MOD;
    }
    for (int i = 2; i < MAXN * 2; i++) {
        ifact[i] = ifact[i - 1] * ifact[i] % MOD;
    }
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n * 2 + 5; i++) {
            f[i] = 0;
        }
        n++;
        for (int i = 1; i < n; i++) {
            int s; cin >> s;
            f[s + n]++;
        }
        f[n]++;
        int mn = INF, mx = -INF;
        for (int i = 0; i <= 2 * n; i++) {
            if (f[i]) {
                mn = min(mn, i);
                mx = max(mx, i);
            }
        }
        bool bad = 0;
        for (int i = mn; i <= mx; i++) {
            if (!f[i]) {
                bad = 1;
                break;
            }
        }
        if (bad || mn == mx) {
            cout << 0 << '\n';
            continue;
        }
        ll ans = 0;
        for (int x = mx; x >= mn; x--) {
            d[mx - 1] = f[mx] + (mx > n) - (mx == x);
            for (int i = mx - 2; i >= mn - 1; i--) {
                d[i] = f[i + 1] - d[i + 1] + (i >= x) + (i >= n);
            }
            if (d[mn - 1] != 0) {
                continue;
            }
            ll res = 1;
            for (int i = mx - 1; i >= mn; i--) {
                res = res * starbar(d[i], f[i] - d[i]) % MOD;
            }
            ans += res;
            if (ans >= MOD) {
                ans -= MOD;
            }
        }
        cout << ans << '\n';
    }
}

Solve the problem in $$$O(n)$$$ time.

Unfortunately, it seems like ARC146E is identical to this problem :(

When $$$c_i$$$ and $$$z$$$ equals $$$10^{18}$$$, it means that all the remaining water will always flow into the next water tower. Hence, the answer will be the sum of $$$a_i$$$ minus the amount of water remaining at tower $$$n$$$ after the process.

From hint 1, our new task now is to determine the amount of water remaining at tower $$$n$$$ after the process. Let $$$v_i = a_i - b_i$$$. The remaining amount of water remaining at tower $$$n$$$ is the maximum suffix sum of $$$v$$$, or more formally $$$\max\limits_{1\le k\le n}\ \sum\limits_{i = k}^n v_i$$$. We can use a segment tree where position $$$p$$$ of the segment tree stores $$$\sum\limits_{i = p}^n v_i$$$. The updates can be done using range prefix increment and the queries can be done using range maximum.

Code ReLU segment tree. A similar method can be used to solve the full problem if you combine even more ReLUs. However, it is not very elegant and is much more complicated than the intended solution below.

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

typedef long long ll;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

int n, q;
int a[MAXN], b[MAXN];
ll c[MAXN];
ll v[MAXN], sv[MAXN];

ll mx[MAXN * 4], lz[MAXN * 4];
void init(int u = 1, int lo = 1, int hi = n) {
    lz[u] = 0;
    if (lo == hi) {
        mx[u] = sv[lo];
    } else {
        int mid = lo + hi >> 1;
        init(u << 1, lo, mid);
        init(u << 1 ^ 1, mid + 1, hi);
        mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
    }
}
void propo(int u) {
    if (lz[u] == 0) {
        return;
    }
    lz[u << 1] += lz[u];
    lz[u << 1 ^ 1] += lz[u];
    mx[u << 1] += lz[u];
    mx[u << 1 ^ 1] += lz[u];
    lz[u] = 0;
}
void incre(int s, int e, ll x, int u = 1, int lo = 1, int hi = n) {
    if (lo >= s && hi <= e) {
        mx[u] += x;
        lz[u] += x;
        return;
    }
    propo(u);
    int mid = lo + hi >> 1;
    if (s <= mid) {
        incre(s, e, x, u << 1, lo, mid);
    }
    if (e > mid) {
        incre(s, e, x, u << 1 ^ 1, mid + 1, hi);
    }
    mx[u] = max(mx[u << 1], mx[u << 1 ^ 1]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> c[i];
    }
    ll sma = 0;
    for (int i = n; i >= 1; i--) {
        v[i] = a[i] - b[i];
        sv[i] = v[i] + sv[i + 1];
        sma += a[i];
    }
    init();
    while (q--) {
        int p, x, y; ll z; cin >> p >> x >> y >> z;
        sma -= a[p];
        incre(1, p, -v[p]);
        a[p] = x;
        b[p] = y;
        v[p] = a[p] - b[p];
        sma += a[p];
        incre(1, p, v[p]);
        cout << sma - max(0ll, mx[1]) << '\n';
    }
}

Try modelling this problem into a maximum flow problem.

Try using minimum cut to find the maximum flow.

Speed up finding the minimum cut using a segment tree.

Consider a flow graph with $$$n + 2$$$ vertices. Let the source vertex be $$$s = n + 1$$$ and the sink vertex be $$$t = n + 2$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$, add edge $$$s\rightarrow i$$$ with capacity $$$a_i$$$ and another edge $$$i\rightarrow t$$$ with capacity $$$b_i$$$. Then for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, add edge $$$i\rightarrow i + 1$$$ with capacity $$$c_i$$$. The maximum flow from $$$s$$$ to $$$t$$$ will be the answer to the problem.

Let us try to find the minimum cut of the above graph instead.

Claim: The minimum cut will contain exactly one of $$$s\rightarrow i$$$ or $$$i\rightarrow t$$$ for all $$$1\le i\le n$$$.

Proof: If the minimum cut does not contain both $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$, $$$s$$$ can reach $$$t$$$ through vertex $$$i$$$ and hence it is not a minimum cut. Now, we will prove why the minimum cut cannot contain both $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$. Suppose there exists a minimum cut where there exists a vertex $$$1\le i\le n$$$ where $$$s\rightarrow i$$$ and $$$i\rightarrow t$$$ are both in the minimum cut. We will consider two cases:

• Case 1: $$$s$$$ can reach $$$i$$$ (through some sequence of vertices $$$s\rightarrow j\rightarrow j+1\rightarrow \ldots \rightarrow i$$$ where $$$j < i$$$). If our minimum cut only contains $$$i\rightarrow t$$$ without $$$s\rightarrow i$$$, nothing changes as $$$s$$$ was already able to reach $$$i$$$ when $$$s\rightarrow i$$$ was removed. Hence, $$$s$$$ will still be unable to reach $$$t$$$ and we found a minimum cut that has equal or smaller cost.
• Case 2: $$$s$$$ cannot reach $$$i$$$. If our minimum cut only contains $$$s\rightarrow i$$$ without $$$i\rightarrow t$$$, nothing changes as $$$s$$$ is still unable to reach $$$i$$$, so we cannot make use of the edge $$$i\rightarrow t$$$ to reach $$$t$$$ from $$$s$$$. Hence, $$$s$$$ will still be unable to reach $$$t$$$ and we found a minimum cut that has equal or smaller cost.

Now, all we have to do is select for each $$$1\le i\le n$$$, whether to cut the edge $$$s\rightarrow i$$$ or the edge $$$i\rightarrow t$$$. Let us use a string $$$x$$$ consisting of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$ to represent this. $$$x_i = \texttt{A}$$$ means we decide to cut the edge $$$s\rightarrow i$$$ for a cost of $$$a_i$$$ and $$$x_i = \texttt{B}$$$ means we decide to cut the edge from $$$i\rightarrow t$$$ for a cost of $$$b_i$$$. Notice that whenever we have $$$x_i = \texttt{B}$$$ and $$$x_{i + 1} = \texttt{A}$$$, $$$s$$$ can reach $$$t$$$ through $$$s\rightarrow i\rightarrow i + 1\rightarrow t$$$. To prevent this, we have to cut the edge $$$i\rightarrow i + 1$$$ for a cost of $$$c_i$$$.

To handle updates, we can use a segment tree. Each node of the segment tree stores the minimum possible cost for each of the four combinations of the two endpoints being $$$\texttt{A}$$$ or $$$\texttt{B}$$$. When merging the segment tree nodes, add a cost of $$$c$$$ when the right endpoint of the left node is $$$\texttt{B}$$$ and the left endpoint of the right node is $$$\texttt{A}$$$. The final time complexity is $$$O(n\log n)$$$ as only a segment tree is used.

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

typedef long long ll;
const ll LINF = 1000000000000000005ll;
const int MAXN = 500005;

int n, q;
int a[MAXN], b[MAXN];
ll c[MAXN];

ll st[MAXN * 4][2][2];
void merge(int u, int lo, int hi) {
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    for (int l = 0; l < 2; l++) {
        for (int r = 0; r < 2; r++) {
            st[u][l][r] = min({st[lc][l][0] + st[rc][0][r],
                    st[lc][l][1] + st[rc][1][r],
                    st[lc][l][0] + st[rc][1][r],
                    st[lc][l][1] + st[rc][0][r] + c[mid]});
        }
    }
}
void init(int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[u][0][0] = a[lo];
        st[u][1][1] = b[lo];
        st[u][1][0] = st[u][0][1] = LINF;
        return;
    }
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    init(lc, lo, mid);
    init(rc, mid + 1, hi);
    merge(u, lo, hi);
}
void upd(int p, int u = 1, int lo = 1, int hi = n) {
    if (lo == hi) {
        st[u][0][0] = a[lo];
        st[u][1][1] = b[lo];
        st[u][1][0] = st[u][0][1] = LINF;
        return;
    }
    int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1;
    if (p <= mid) {
        upd(p, lc, lo, mid);
    } else {
        upd(p, rc, mid + 1, hi);
    }
    merge(u, lo, hi);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> c[i];
    }
    init();
    while (q--) {
        int p, x, y; ll z; cin >> p >> x >> y >> z;
        a[p] = x; b[p] = y; c[p] = z;
        upd(p);
        cout << min({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]}) << '\n';
    }
}

Think about how you would construct matrix $$$s$$$ if you were given the tree.

If $$$s_{i, i} = \mathtt{0}$$$, what should the value of $$$s_{j, i}$$$ be for all $$$1\le j\le n$$$?

For some $$$i$$$ where $$$s_{i, i} = \mathtt{1}$$$, let $$$Z$$$ be a set containing all the vertices $$$j$$$ where $$$s_{j, i} = \mathtt{0}$$$. More formally, $$$Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, i} = \mathtt{0}\}$$$. Does $$$Z$$$ have any special properties?

Using hint 3, can we break down the problem into smaller sub-problems?

Try solving the problem if the values in each column are a constant. In other words, $$$s_{i, j} = s_{j, j}$$$ for all $$$1\le i\le n$$$ and $$$1\le j\le n$$$.

Let us consider how we can code the checker for this problem. In other words, if we are given a tree, how can we construct matrix $$$s$$$? We can solve this using dynamic programming. $$$s_{i, j} = \mathtt{1}$$$ if and only if at least one child $$$c$$$ of vertex $$$j$$$ (when the tree is rooted at vertex $$$i$$$) has $$$s_{i, c} = \mathtt{0}$$$. This is because the player can move the coin from vertex $$$j$$$ to vertex $$$c$$$ which will cause the opponent to be in a losing state.

For convenience, we will call a vertex $$$i$$$ special if there exists some $$$1\le j\le n$$$ where $$$s_{j, i} \neq s_{i, i}$$$. Suppose there exist some $$$i$$$ where $$$s_{i, i} = \mathtt{0}$$$. This means that moving the coin to any of the neighbours of $$$i$$$ results in a winning state for the opponent. If the tree was rooted at some other vertex $$$j\neq i$$$, it will still be a losing state as it reduces the options that the player can move the coin to, so $$$s_{j, i}$$$ should be $$$\mathtt{0}$$$ for all $$$1\le j\le n$$$. This means that special vertices must have $$$s_{i, i} = \mathtt{1}$$$

Now, let us take a look at special vertices. Let $$$x$$$ be a special vertex, meaning $$$s_{x, x} = \mathtt{1}$$$ and there exist some $$$j$$$ where $$$s_{j, x} = \mathtt{0}$$$. Let $$$Z$$$ be a set containing all the vertices $$$j$$$ where $$$s_{j, x} = \mathtt{0}$$$. More formally, $$$Z = \{j\ |\ 1\le j\le n\text{ and } s_{j, x} = \mathtt{0}\}$$$. $$$Z$$$ cannot be empty due to the property of special vertices. Notice that whenever we choose to root at some vertex $$$j\neq x$$$, the number of children of $$$x$$$ decreases by exactly $$$1$$$. This is because the neighbour that lies on the path from vertex $$$x$$$ to vertex $$$j$$$ becomes the parent of $$$x$$$ instead of the child of $$$x$$$. If rooting the tree at vertex $$$x$$$ is a winning state but rooting the tree at some other vertex $$$j$$$ results in a losing state instead, it means that the only winning move is to move the coin from vertex $$$x$$$ to the neighbour that is on the path from vertex $$$x$$$ to $$$j$$$.

Let $$$y$$$ denote the only neighbour of vertex $$$x$$$ where we can move the coin from vertex $$$x$$$ to vertex $$$y$$$ and win. In other words, $$$y$$$ is the neighbour of vertex $$$x$$$ where $$$y$$$ lies on the path of the vertices in set $$$Z$$$ and $$$x$$$. This means that $$$Z$$$ is the set of vertices that are in the subtree of $$$y$$$ rooted at vertex $$$x$$$.

Now, let us try to find vertex $$$y$$$. Notice that $$$s_{y, y} = \mathtt{1}$$$. This is because $$$s_{y, x} = \mathtt{0}$$$, so the coin can be moved from vertex $$$y$$$ to vertex $$$x$$$ to result in a losing state for the opponent. Furthermore, $$$s_{j, y} = \mathtt{0}$$$ if and only if $$$j$$$ is not in $$$Z$$$, otherwise $$$s_{j, y} = \mathtt{1}$$$. This is because $$$s_{x, y} = \mathtt{0}$$$ since moving the coin from vertex $$$x$$$ to vertex $$$y$$$ is a winning move for the first player. For all other vertex $$$u\in Z$$$ that is not $$$y$$$, this property will not hold as even if $$$s_{u, u} = \mathtt{1}$$$ and $$$s_{x, u} = \mathtt{0}$$$, $$$s_{y, u}$$$ will be equal to $$$\mathtt{0}$$$ as well as the tree being rooted at $$$x$$$ has the same effect as if it was rooted at $$$y$$$. Since $$$y \in Z$$$, $$$s_{y, u} = \mathtt{0}$$$ does not satisfy $$$s_{j, u} = \mathtt{1}$$$ for all $$$j$$$ in $$$Z$$$.

Since $$$y$$$ is a neighbour of vertex $$$x$$$, we know that there is an edge between vertex $$$y$$$ and $$$x$$$. Furthermore, we know that if the edge between vertex $$$y$$$ and $$$x$$$ is removed, the set of vertices $$$Z$$$ forms a single connected component containing $$$y$$$, while the set of vertices not in $$$Z$$$ forms another connected component containing $$$x$$$. This means that we can recursively solve the problem for the two connected components to check whether the values in the matrix $$$s$$$ are valid within their components.

After recursively solving for each connected component, we are only left with non-special vertices ($$$s_{j, i} = s_{i, i}$$$ for all $$$1\le j\le n$$$) and some special vertices that already have an edge that connects to outside the component. Non-special vertices with $$$s_{i, i} = \mathtt{1}$$$ has to be connected to at least $$$2$$$ non-special vertices with $$$s_{i, i} = \mathtt{0}$$$. The most optimal way to do this is to form a line 0 — 1 — 0 — 1 — 0 as it requires the least amount of $$$s_{i, i} = \mathtt{0}$$$. If there is not enough $$$s_{i, i} = \mathtt{0}$$$ to form the line, a solution does not exist. Otherwise, connect the left-over $$$s_{i, i} = \mathtt{0}$$$ to any of $$$s_{i, i} = \mathtt{1}$$$. On the other hand, special vertices can either be connected to nothing, connected to other special vertices, or connected to non-special vertices with $$$s_{i, i} = \mathtt{1}$$$.

For the final step, we need to check whether $$$s_{i, j}$$$ is consistent when $$$i$$$ and $$$j$$$ are in different components (i.e. ($$$i\in Z$$$ and $$$j\notin Z$$$) or ($$$i\notin Z$$$ and $$$j\in Z$$$)). Notice that $$$s_{i, j} = s_{x, j}$$$ for all $$$i\in Z$$$ and $$$j\notin Z$$$ and $$$j\neq x$$$, and $$$s_{i, j} = s_{y, j}$$$ for all $$$i\notin Z$$$ and $$$j\in Z$$$ and $$$j\neq y$$$. From the steps above, we managed to account for every value in the matrix, hence if matrix $$$s$$$ is consistent through all the steps, the constructed tree would be valid as well.

We can make use of xor hash to find vertex $$$x$$$ together with its corresponding vertex $$$y$$$. With xor hash, the time complexity is $$$O(n^2)$$$. Well-optimised bitset code with time complexity of $$$O(\frac{n^3}{w})$$$ can pass as well.

#include <bits/stdc++.h> 
using namespace std;
 
const int MAXN = 5005;

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
 
int n;
unsigned long long r[MAXN], hsh[MAXN], totr;
string s[MAXN];
vector<pair<int, int>> ans;
 
bool done[MAXN];
bool solve(vector<int> grp) {
    int pr = -1, pl = -1;
    vector<int> lft, rht;
    for (int i : grp) {
        if (s[i][i] == '0' || done[i] || hsh[i] == totr) {
            continue;
        }
        rht.clear();
        for (int j : grp) {
            if (s[j][i] == '0') {
                lft.push_back(j);
            } else {
                rht.push_back(j);
            }
        }
        if (!lft.empty()) {
            pr = i;
            break;
        }
    }
    if (pr == -1) {
        vector<int> dv, zero, one;
        for (int i : grp) {
            if (done[i]) {
                dv.push_back(i);
            } else if (s[i][i] == '0') {
                zero.push_back(i);
            } else {
                one.push_back(i);
            }
        }
        for (int i = 1; i < dv.size(); i++) {
            ans.push_back({dv[i - 1], dv[i]});
        }
        if (one.empty() && zero.empty()) {
            return 1;
        }
        if (one.size() >= zero.size()) {
            return 0;
        }
        if (one.empty()) {
            if (zero.size() >= 2 || !dv.empty()) {
                return 0;
            }
            return 1;
        }
        for (int i = 0; i < one.size(); i++) {
            ans.push_back({zero[i], one[i]});
            ans.push_back({one[i], zero[i + 1]});
        }
        for (int i = one.size() + 1; i < zero.size(); i++) {
            ans.push_back({one[0], zero[i]});
        }
        if (!dv.empty()) {
            ans.push_back({one[0], dv[0]});
        }
        return 1;
    }
    for (int i : lft) {
        if (s[i][i] == '0' || done[i] || ((hsh[i] ^ hsh[pr]) != totr)) {
            continue;
        }
        vector<int> trht;
        for (int j : grp) {
            if (s[j][i] == '0') {
                trht.push_back(j);
            }
        }
        if (trht == rht) {
            pl = i;
            break;
        }
    }
    if (pl == -1) {
        return 0;
    }
    for (int i : lft) {
        for (int j : rht) {
            if (j == pr) {
                continue;
            }
            if (s[i][j] != s[pr][j]) {
                return 0;
            }
        }
    }
    for (int i : rht) {
        for (int j : lft) {
            if (j == pl) {
                continue;
            }
            if (s[i][j] != s[pl][j]) {
                return 0;
            }
        }
    }
    ans.push_back({pl, pr});
    done[pl] = done[pr] = 1;
    return solve(lft) && solve(rht);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < n; i++) {
        r[i] = rnd();
        totr ^= r[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1') {
                hsh[j] ^= r[i];
            }
        }
    }
    bool pos = 1;
    for (int i = 0; i < n; i++) {
        if (s[i][i] == '1') {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if (s[j][i] == '1') {
                pos = 0;
                break;
            }
        }
    }
    if (!pos) {
        cout << "NO\n";
        return 0;
    }
    vector<int> v(n, 0);
    iota(v.begin(), v.end(), 0);
    if (!solve(v)) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (auto [u, v] : ans) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

The original problem allowed $$$5n$$$ type 1 queries and $$$n$$$ type 2 queries and was used as the last problem of a Div. 2 round. When we opened the round for testing, dario2994 solved the problem using $$$2n$$$ type 1 queries, and a few days later, he managed to improve his solution to use only $$$n$$$ type 1 queries. This was what made us decide to change this round into a Div. 1 round instead of a Div. 2 round.

Try rooting the tree at an edge.

Use $$$n - 2$$$ of query $$$2$$$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge.

We start with only the root edge, then add edges of depth $$$0$$$, followed by depth $$$1, 2, \ldots$$$

If we want to add a new edge with depth $$$i$$$, we need to attach it to one of the edges with depth $$$i - 1$$$. We can let the weight of the edge we want to attach be $$$10^9$$$ to force the diameter to pass through it, then let the edges of depth $$$i - 1$$$ have weights be different multiples of $$$n$$$. This way, we can determine which edges of depth $$$i - 1$$$ are used in the diameter (unless the two largest edges are used).

Make use of isomorphism to handle the case in hint 4 where the largest two edges are used.

If isomorphism cannot be used, find a leaf edge of a lower depth than the query edge and force the diameter to pass through the leaf edge and the query edge. Then, only 1 edge of depth $$$i - 1$$$ will be used and the edge weights for edges of depth $$$i - 1$$$ can follow a similar structure as hint 4.

We will root the tree at edge $$$1$$$. Then, use $$$n - 2$$$ of query $$$2$$$ to find the distance of every edge to the root. For convenience, we will call the distance of an edge to the root the depth of the edge. Our objective is to add the edges in increasing order of depth, so when we are inserting an edge of depth $$$i$$$, all edges of depth $$$i - 1$$$ are already inserted and we just have to figure out which edge of depth $$$i - 1$$$ we have to attach the edge of depth $$$i$$$ to.

For convenience, the edge weights used in query $$$1$$$ will be $$$1$$$ by default unless otherwise stated. Let $$$c_i$$$ store the list of edges with depth $$$i$$$. Suppose we want to insert edge $$$u$$$ into the tree and the depth of edge $$$u$$$ is $$$d$$$. We let the weight of the edge $$$u$$$ be $$$10 ^ 9$$$ and the weight of edges in $$$c_{d - 1}$$$ be $$$n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, (|c_{d - 1}| - 1)n$$$. The diameter will pass through edge $$$u$$$, the parent edge of $$$u$$$, as well as one edge of weight $$$(|c_{d - 1}| - 1)n$$$. If we calculate $$$\left\lfloor\frac{\text{diameter} - 10^9}{n}\right\rfloor - (|c_{d - 1}| - 1)$$$, we will be able to tell the index of the parent edge of $$$u$$$.

However, there is one exception. When the parent edge of $$$u$$$ is one of the last 2 edges of $$$c_{d - 1}$$$, we are unable to differentiate between the two of them as they have the same weight. This is not a problem if the last 2 edges are isomorphic to each other, as attaching $$$u$$$ to either parent results in the same tree. For now, we will assume that the last 2 edges of $$$c_{d - 1}$$$ are isomorphic to each other.

However, after attaching edge $$$u$$$ to one last 2 edges in $$$c_{d - 1}$$$, they are no longer isomorphic. Hence, we need to use a different method to insert the remaining edges of depth $$$d$$$. Let the new edge that we want to insert be $$$v$$$. Let the weight of edges $$$u$$$ and $$$v$$$ be $$$10^9$$$ and the weights of edges in $$$c_{d - 1}$$$ be the same as before. Now, we can use $$$\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$$$ to determine whether edge $$$v$$$ share the same parent as $$$u$$$, and if it does not share the same parent, it can still determine the index of the parent edge of $$$v$$$. With the additional information of whether edge $$$v$$$ shares the same parent as edge $$$u$$$, we will be able to differentiate the last 2 edges of $$$c_{d - 1}$$$ from each other.

Now, we just need to handle the issue where the last 2 edges of $$$c_{d - 1}$$$ are not isomorphic. When we only have the root edge at the start, the left and right ends of the edge are isomorphic (note that for the root edge, we consider it as 2 separate edges, one with the left endpoint and one with the right endpoint). We try to maintain the isomorphism as we add edges of increasing depth. Suppose the last two edges of $$$c_{d - 1}$$$ are isomorphic. Let the two edges be $$$a$$$ and $$$b$$$. Then, we insert edges of depth $$$d$$$ using the above method. Let the child edges attached to $$$a$$$ and $$$b$$$ be represented by sets $$$S_a$$$ and $$$S_b$$$ respectively. If either $$$S_a$$$ or $$$S_b$$$ has sizes at least $$$2$$$, the two edges in the same set will be isomorphic, so we can let those 2 edges be the last 2 edges of $$$c_d$$$. Now, the sizes of $$$S_a$$$ and $$$S_b$$$ are both strictly smaller than $$$2$$$. If the sizes of both sets are exactly $$$1$$$, the two edges from each set will be isomorphic as well as $$$a$$$ and $$$b$$$ are isomorphic. Now, the only case left is if at least one of the sets is empty.

Without loss of generality, assume that $$$S_a$$$ is empty. Since it is no longer possible to maintain two isomorphic edges, we now change our objective to find a leaf (it will be clear why in the following paragraphs). If $$$S_b$$$ is empty as well, both $$$a$$$ and $$$b$$$ are leaves so we can choose any one of them. If $$$S_b$$$ is not empty, then $$$a$$$ and $$$b$$$ are no longer isomorphic due to their children. This means that we cannot simply use $$$b$$$ as the leaf $$$S_a$$$ might be children of $$$b$$$ instead of $$$a$$$ as we did not differentiate $$$a$$$ and $$$b$$$ in the previous paragraphs. To determine whether $$$S_a$$$ belongs to $$$a$$$ or $$$b$$$, we can make use of one type 2 query to find the distance between one of the edges in $$$S_a$$$ and $$$a$$$. If the distance is $$$0$$$, it means that $$$S_a$$$ belongs to $$$a$$$. Otherwise, the distance will be $$$1$$$ and $$$S_a$$$ belongs to $$$b$$$.

Now that we found a leaf, we can use the following method to insert an edge $$$u$$$ of depth $$$d$$$. We let the weight of the edge $$$u$$$ and the leaf edge be $$$10 ^ 9$$$ and the weight of edges in $$$c_{d - 1}$$$ be $$$n, 2n, 3n, \ldots, (|c_{d - 1}| - 2)n, (|c_{d - 1}| - 1)n, |c_{d - 1}|n$$$. The diameter will pass through edge $$$u$$$, the leaf edge, and only one edge of depth $$$d - 1$$$ which is the parent edge of $$$u$$$. Hence, after finding a leaf edge, we can uniquely determine the parent edge from $$$\left\lfloor\frac{\text{diameter} - 2\cdot 10^9}{n}\right\rfloor$$$.

We used $$$n - 2$$$ type 1 queries and $$$n - 1$$$ type 2 queries in total. This is because we used a single type 1 query for each non-root edge. We used $$$n - 2$$$ type 2 queries at the start, and we only used $$$1$$$ additional type 2 query when we were no longer able to maintain two isomorphic edges and changed our methodology to use a leaf edge instead.

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

typedef long long ll;
const int INF = 1000000000;
const int MAXN = 1000;

int n;
int lvl[MAXN + 5];
int pe[MAXN + 5];
vector<int> ch[MAXN + 5];

ll query(vector<int> a) {
    cout << "? 1";
    for (int i = 1; i < n; i++) {
        cout << ' ' << a[i];
    }
    cout << endl;
    ll res; cin >> res;
    return res;
}
int query(int a, int b) {
    cout << "? 2 " << a << ' ' << b << endl;
    int res; cin >> res;
    return res;
}

int main() {
    cin >> n;
    for (int i = 2; i < n; i++) {
        lvl[i] = query(1, i);
    }
    int ptr = 3;
    vector<int> base = {1, 2};
    pe[1] = pe[2] = 1;
    bool iso = 1;
    int piv = -1;
    for (int l = 0; l < n; l++) {
        vector<int> a(n, 1);
        int m = base.size();
        for (int i = 0; i < m; i++) {
            a[pe[base[i]]] = min(i + 1, m - iso) * MAXN;
        }
        if (!iso) {
            a[pe[piv]] = INF;
        }
        bool ciso = 0;
        for (int u = 2; u < n; u++) {
            if (lvl[u] != l) {
                continue;
            }
            a[u] = INF;
            ll res = query(a) - INF;
            a[u] = 1;
            if (!iso || ciso) {
                res -= INF;
            }
            int id = res / MAXN;
            if (iso && l) {
                id -= m - 1;
            }
            int v = ptr++;
            pe[v] = u;
            if (ciso) {
                if ((l == 0 && id == 0) || id == -(m - 1)) {
                    ch[base[m - 2]].push_back(v);
                } else if (id == m - 1) {
                    ch[base[m - 1]].push_back(v);
                } else {
                    ch[base[id - 1]].push_back(v);
                }
            } else if (iso && id == m - 1) {
                ch[base[m - 2]].push_back(v);
                ciso = 1;
                a[u] = INF;
            } else {
                ch[base[id - 1]].push_back(v);
            }
        }
        if (m >= 2 && ch[base[m - 2]].size() > ch[base[m - 1]].size()) {
            swap(base[m - 2], base[m - 1]);
        }
        vector<int> nbase;
        for (int i = 0; i < m; i++) {
            for (int j : ch[base[i]]) {
                nbase.push_back(j);
            }
        }
        if (!iso || ch[base[m - 1]].size() >= 2 || ch[base[m - 2]].size() == 1) {
            base = nbase;
            continue;
        }
        if (ch[base[m - 1]].empty()) {
            piv = base[m - 1];
        } else {
            ll res = query(pe[ch[base[m - 1]][0]], pe[base[m - 1]]);
            if (res) {
                swap(base[m - 2], base[m - 1]);
                swap(ch[base[m - 2]], ch[base[m - 1]]);
            }
            piv = base[m - 2];
        }
        iso = 0;
        base = nbase;
    }
    cout << '!' << endl;
    cout << 1 << ' ' << 2 << endl;
    for (int u = 1; u <= n; u++) {
        for (int v : ch[u]) {
            cout << u << ' ' << v << endl;
        }
    }
}

struct S {
    // return value of DP
    int take, notTake;
};
S init(int u) {
    // initialise the base state of dp[u]
    return {1, 0};
}
S merge(S left, S right) {
    // returns the new dp state where old state is left and transition using right
    return {left.take + right.notTake, left.notTake + max(right.take, right.notTake)};
}
S dp(int u, int p) {
    S res = init(u);
    for (int v : adj[u]) {
        if (v == p) continue;
        res = merge(res, dp(v, u));
    }
    return res;
}
int main() {
    dp(1, -1);
}

Let us consider the ending state of the game. It turns out that at the ending state, we will only have logs of $$$1$$$ meter. Otherwise, players can make a move.

Now, at the ending state of the game, we will have $$$\sum\limits_{k=1}^n a_k$$$ logs. And each move we increase the number of logs by exactly $$$1$$$. Since we started with $$$n$$$ logs, there has been exactly $$$(\sum\limits_{k=1}^n a_k) - n$$$ turns.

Alternatively, a log of length $$$a_k$$$ will be cut $$$a_k-1$$$ times, so there will be $$$\sum\limits_{k=1}^n (a_k-1)$$$ turns.

If there were an odd number of turns $$$\texttt{errorgorn}$$$ wins, otherwise $$$\texttt{maomao90}$$$ wins.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[105];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n) cin>>arr[x];
		
		int tot=0;
		rep(x,0,n) tot+=arr[x]-1;
		
		if (tot%2==0) cout<<"maomao90"<<endl;
		else cout<<"errorgorn"<<endl;
	}
}

Claim: The string is obtainable if it ends in $$$\texttt{B}$$$ and every prefix of the string has at least as many $$$\texttt{A}$$$ as $$$\texttt{B}$$$.

An alternative way to think about the second condition is to assign $$$\texttt{A}$$$ to have a value of $$$1$$$ and $$$\texttt{B}$$$ to have a value of $$$-1$$$. Then, we are just saying that each prefix must have a non-negative sum. This is pretty similar to bracket sequences.

Now, both conditions are clearly necessary, let us show that they are sufficient too.

We will explicitly construct the string (in the reverse direction). While there are more than $$$1$$$ occurrences of $$$\texttt{B}$$$ in the string, remove the first occurrence of $$$\texttt{AB}$$$. After doing this process, you will eventually end up with the string $$$\texttt{AAA...AAB}$$$.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		string s;
		cin>>s;
		
		bool ok=(s.back()=='B');
		
		int sum=0;
		for (auto it:s){
			if (it=='A') sum++;
			else sum--;
			if (sum<0) ok=false;
		}
		
		if (ok) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Suppose $$$l$$$ is the smallest index where $$$a_l = a_{l+1}$$$ and r is the largest index where $$$a_r = a_{r+1}$$$. If $$$l=r$$$ or $$$l$$$ and $$$r$$$ does not exist, the condition is already satisfied and we can do 0 operations. Otherwise, the answer is $$$\max(1, r - l - 1)$$$. The proof is as follows:

1. Suppose $$$l+1=r$$$, then, there are 3 elements that are adjacent to each other. Hence, we can just do one operation with $$$i=l$$$ and $$$x=\infty$$$ to make the equality of the array 1.
2. Suppose otherwise, then the array will look something like $$$[..., X, X, ..., Y, Y, ...]$$$, with $$$r - l - 2$$$ elements between the second $$$X$$$ and the first $$$Y$$$. Then, we can do operations on $$$i={l+1, l+2, \ldots, r-2, r-1}$$$ to make the equality of the array 1.

To see why we need at least $$$r - l - 1$$$ operations, observe that each operation will cause $$$r - l$$$ to decrease by at most 1. This is because if we do not do an operation on $$$i \in \{l-1,l+1,r-1,r+1\}$$$, then both $$$a_l = a_{l+1}$$$ and $$$a_r = a_{r+1}$$$ will still hold. We see that $$$r-l$$$ only decreases when do we an operation on $$$i \in {l+1,r-1}$$$ and it is not too hard to show that it only decreases by $$$1$$$ in those cases while $$$r-l > 2$$$

Hence, we keep doing the operation until $$$r - l = 2$$$, which will only require 1 operation to change both pairs and make the equality 1.

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

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int t;
int n;
int a[MAXN];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> t;
    while (t--) {
        cin >> n;
        REP (i, 0, n) {
            cin >> a[i];
        }
        int mn = -1, mx = -1;
        REP (i, 1, n) {
            if (a[i] == a[i - 1]) {
                if (mn == -1) {
                    mn = i;
                }
                mx = i;
            }
        }
        if (mn == mx) {
            cout << 0 << '\n';
        } else {
            cout << max(1, mx - mn - 1) << '\n';
        }
    }
    return 0;
}

We will solve the problem by reversing the steps and transform array $$$b$$$ to array $$$a$$$.

We can do the following operation on $$$b$$$:

• pick index $$$i<j$$$ such that $$$b_j=b_{j+1}$$$ and remove $$$b_{j+1}$$$ and insert it after position $$$i$$$.

Now, for every consecutive block of identical elements in $$$b$$$, we can remove all but one element from it and move it left.

If we process from right to left, we can imagine as taking consecutive elemnets in $$$b$$$ out and placing in a reserve, and using them to match some elements in $$$a$$$ towards the left.

Using this idea, we can use the following greedy two-pointer algorithm:

Let $$$i$$$ and $$$j$$$ represent the size of $$$a$$$ and $$$b$$$ respectively (and hence $$$a_i$$$ and $$$b_j$$$ will refer to the last elements of $$$a$$$ and $$$b$$$ respectively). We also have an initially empty multiset $$$S$$$, which represents the reserve. We will perform the following operations in this order:

1. While $$$b_{j-1}=b_j$$$, add $$$b_j$$$ to the multiset $$$S$$$ and decrement $$$j$$$
2. If $$$a_i = b_j$$$, then decrement both $$$i$$$ and $$$j$$$
3. Otherwise, we delete an occurance of $$$a_i$$$ in $$$S$$$ and decrement $$$i$$$. If we cannot find $$$a_i$$$ in $$$S$$$, it is impossible to transform $$$b$$$ to $$$a$$$.

Let us define an array $$$c$$$ where all elements of $$$c$$$ is $$$1$$$. We can rephrase the problem in the following way:

• Choose $$$i<j$$$ such that $$$a_i = a_j$$$ and $$$c_i>0$$$. Then update $$$c_i \gets c_i-1$$$ and $$$c_j \gets c_j+1$$$.

The final array $$$b$$$ is obtained by the following: Let $$$b$$$ be initially empty, then iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and add $$$c_i$$$ copies of $$$a_i$$$ to $$$b$$$.

As such, we can consider mapping elements of $$$b$$$ into elements of $$$a$$$. More specifically, consider a mapping $$$f$$$ where $$$f$$$ is non-decreasing, $$$b_i=a_{f_i}$$$ and we increment $$$c_{f_i}$$$ by $$$1$$$ for all $$$i$$$. All that remains is to determine if we can make such a mapping such that $$$c$$$ is valid.

Notice that if all elements of $$$a$$$ are identical, the necessary and sufficient condition for a valid array $$$c$$$ is that $$$c_1+c_2+\ldots+c_i \leq i$$$ for all $$$i$$$.

This motivates us to construct an array $$$pa$$$ where $$$pa_i$$$ is the number of indices $$$j \leq i$$$ such that $$$a_i=a_j$$$. Analogously, construct $$$pb$$$.

Then the necessary and sufficient conditions for a mapping $$$f$$$ is that $$$f$$$ is non-decreasing, $$$b_i=a_{f_i}$$$ and $$$pb_i \leq pa_{f_i}$$$. A greedy algorithm to construct $$$f$$$, if it exists, is trivial by minimizing $$$f_i$$$ for each $$$i$$$.

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

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005

int t;
int n;
int a[MAXN], b[MAXN];
int cnt[MAXN];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> t;
    while (t--) {
        cin >> n;
        REP (i, 1, n + 1) {
            cnt[i] = 0;
        }
        REP (i, 0, n) {
            cin >> a[i];
        }
        REP (i, 0, n) {
            cin >> b[i];
        }
        int i = 0, j = 0;
        bool pos = 1;
        while (j < n) {
            if (i < n && j < n && a[i] == b[j]) {
                i++; j++;
                continue;
            }
            if (cnt[b[j]] > 0 && b[j] == b[j - 1]) {
                cnt[b[j++]]--;
            } else if (i < n) {
                cnt[a[i++]]++;
            } else {
                pos = 0;
                break;
            }
        }
        if (pos) {
            assert(i == n);
            REP (i, 1, n + 1) {
                assert(cnt[i] == 0);
            }
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[200005];
int brr[200005];
int crr[200005];
int num[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,1,n+1) cin>>arr[x];
		rep(x,1,n+1) cin>>brr[x];
		
		rep(x,1,n+1) num[x]=0;
		rep(x,1,n+1){
			num[arr[x]]++;
			crr[x]=num[arr[x]];
		}
		
		rep(x,1,n+1) num[x]=0;
		int idx=1;
		rep(x,1,n+1){
			num[brr[x]]++;
			while (idx<=n && (arr[idx]!=brr[x] || crr[idx]<num[brr[x]])) idx++;
		}
		
		if (idx>n) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}

The first idea that we have is that we want to be able to find the minimum possible width of the text editor for a specific height. We can do this in $$$n\log (n \cdot 2000)$$$ queries using binary search for each height. This is clearly not good enough, so let us come up with more observations.

First, we can binary search for the minimum possible width for height $$$1$$$. This value is $$$(\sum_{i=1}^n l_i)+n-1$$$ which we will denote with $$$S$$$.

Let us consider what we might want to query for height $$$h$$$. Suppose that the words are arranged very nicely such that there are no trailing spaces in each line. Then, the total number of characters will be $$$S - h +1$$$. This means that the minimum possible area for height $$$h$$$ will be $$$S-h+1$$$. We also know that if the area is more than $$$S$$$, it will not be useful as the area for $$$h=1$$$ is already $$$S$$$.

Now, we know that the range of possible areas that we are interested in is $$$[S - h +1, S]$$$. There is a total of $$$h$$$ possible areas that it can take, and an area is only possible if $$$h \cdot w = a$$$, or in other words, the area is divisible by $$$h$$$. Among the $$$h$$$ consecutive possible values, exactly one of them will be divisible by $$$h$$$, hence we can just query that one value of $$$w$$$ which can very nicely be found as $$$\lfloor \frac{S}{h} \rfloor$$$.

The total number of queries used is $$$n + \log(n \cdot 2000)$$$ where $$$n$$$ comes from the single query for each height and the $$$\log(n \cdot 2000)$$$ comes from the binary search at the start.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug


int n;

int ask(int i){
	if (i==0) return 0;
	cout<<"? "<<i<<endl;
	int temp;
	cin>>temp;
	
	if (temp==-1){
		exit(0);
	}
	
	return temp;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	
	int lo=-2,hi=5e6,mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (ask(mi)==1) hi=mi;
		else lo=mi;
	}
	
	int ans=1e9;
	rep(x,1,n+1){
		int temp=ask(hi/x);
		if (temp) ans=min(ans,temp*(hi/x));
	}
	
	cout<<"! "<<ans<<endl;
}

Let $$$N$$$ be the length of $$$A$$$ and $$$B$$$.

We want to prove that an optimal swapping from $$$B \to A$$$ is equivalent to sorting via some cycles. Suppose our swap order is $$$\{(l_1,r_1),(l_2,r_2),\ldots,(l_K,r_K)\}$$$. Let's consider a graph $$$G$$$ with edges being the swaps. Suppose the number of connected components in $$$G$$$ is $$$CC$$$, then there is a way to perform the transformation $$$B \to A$$$ using $$$CC$$$ cycles since we can view the labels of each connected component of $$$G$$$ as a permutation of the original vertices. One cycle of length $$$X$$$ uses $$$X-1$$$ swaps, so we use $$$N-CC$$$ swaps in total. Since $$$CC \geq N-K$$$, we can always change the swap order to swapping cycles while not performing a bigger number of moves. Now we have changed the problem to maximizing the number of cycles we use.

Let $$$cnt_x$$$ be the number of occurrences of $$$x$$$ in $$$A$$$. WLOG $$$cnt_1 \geq cnt_2 \geq \ldots$$$.

Let $$$s_A(B)$$$ denote the sadness of $$$B$$$ when the original array is $$$A$$$.

Claim: $$$\max(s_A) \leq N-cnt_1$$$

Proof: By pigeonhole principle, we know there exist a cycle with $$$2$$$ occurrences of the element $$$1$$$.

Consider a cycle that swaps $$$i_1 \to i_2 \to \ldots \to i_K \to i_1$$$ where $$$A_{i_1}=A_{i_z}=1$$$. Then we can increase the number of connected components while maintaining $$$B$$$ by splitting into $$$2$$$ cycles $$$i_1 \to i_2 \to \ldots \to i_{z-1} \to i_1$$$ and $$$i_z \to i_2 \to \ldots \to i_N \to i_z$$$.

Therefore, in an optimal solution, there should not be a cycle that passes through the same value twice. $$$\blacksquare$$$

Therefore, we can assume that all occurrences of $$$1$$$ belong to different cycles. Therefore, $$$\#cyc \geq cnt_1$$$ swaps are used. The number of swaps used is $$$N-\#cyc \leq N-cnt_1$$$.

Therefore, $$$N-cnt_1$$$ is a upper bound of $$$s$$$.

Claim: $$$s_A(B)<N-cnt_1$$$ $$$\Leftrightarrow$$$ there exists a cycle $$$i_1 \to i_2 \to \ldots \to i_K \to i_1$$$ such that all $$$i_x \neq 1$$$.

Proof: $$$(\Rightarrow)$$$ There exists a cycle decomposition of the graph that uses at least $$$cnt_1+1$$$ cycles. Since a single element of $$$1$$$ can only go to a single cycle, there exists a cycle without $$$1$$$.

$$$(\Leftarrow)$$$ Let's remove this cycle to form an arrays $$$A'$$$ and $$$B'$$$. Then $$$s_{A'}(B') \leq N-K-cnt_1$$$. Now, we only needed $$$K-1$$$ swaps to remove the cycle, so it much be that $$$s_A(B) \leq (N-K-cnt_1)+(K-1)=N-cnt_1-1$$$. $$$\blacksquare$$$

Constructing maximal $$$B$$$

To construction a permutation such that $$$s(B)=N-cnt_1$$$, let's construct a graph $$$G_{cnt}$$$ based on the number of occurrences of each element in $$$A$$$. We draw $$$cnt_{i+1}$$$ edges from $$$(i) \to (i+1)$$$ and $$$cnt_{i}-cnt_{i+1}$$$ edges from $$$(i) \to (1)$$$. It is obviously impossible to find a cycle that does not contain $$$1$$$. Since all edges will be of the form $$$(i) \to (i+1)$$$.

Another way to construct this permutation is to assume that $$$A$$$ is sorted. Then we perform $$$cnt_1$$$ cyclic shifts on $$$A$$$ to obtain $$$B$$$.

Checking if $$$B$$$ is maximal

Given the graph representation, finding such a cycle $$$i_1 \to i_2 \to \ldots \to i_K \to i_1$$$ such that all $$$i_x \neq 1$$$ is easy. Let's remove $$$1$$$ from the graph then check if the graph is a DAG.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[200005];
int brr[200005];
int cnt[200005];
vector<int> al[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		rep(x,0,n) cin>>arr[x];
		rep(x,1,n+1) al[x].clear();
		rep(x,1,n+1) cnt[x]=0;
		
		rep(x,0,n) cnt[arr[x]]++;
		
		int mx=0;
		rep(x,1,n+1) mx=max(mx,cnt[x]);
		
		rep(x,0,n) brr[x]=arr[x];
		sort(brr,brr+n);
		
		rep(x,0,n) al[brr[x]].pub(brr[(x+mx)%n]);
		
		rep(x,0,n){
			cout<<al[arr[x]].back()<<" \n"[x==n-1];
			al[arr[x]].pob();
		}
	}
	
}

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
int arr[200005];
int brr[200005];

vector<int> al[200005];
bool onstk[200005];
bool vis[200005];

bool cyc;
void dfs(int i){
	onstk[i]=vis[i]=true;
	
	for (auto it:al[i]){
		if (onstk[it]) cyc=true;
		if (!vis[it]) dfs(it);
	}
	
	onstk[i]=false;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		
		rep(x,1,n+1) al[x].clear();
		rep(x,1,n+1) vis[x]=onstk[x]=false;
		
		rep(x,1,n+1) cin>>arr[x];
		rep(x,1,n+1) cin>>brr[x];
		
		rep(x,1,n+1) al[arr[x]].pub(brr[x]);
		
		int mx=1;
		rep(x,1,n+1) if (sz(al[x])>sz(al[mx])) mx=x;
		
		vis[mx]=true;
		cyc=false;
		rep(x,1,n+1) if (!vis[x]) dfs(x);
		
		if (cyc) cout<<"WA"<<endl;
		else cout<<"AC"<<endl;
	}
}

Determining which Grids are Obtainable

Let $$$R_i$$$ and $$$C_j$$$ denote $$$\bigotimes\limits_{j=1}^c a_{i,j}$$$ and $$$\bigotimes\limits_{i=1}^r a_{i,j}$$$ respectively, or the xor-sum of the $$$i$$$-th row and the xor-sum of the $$$j$$$-th column respectively.

We will split the problem into 3 cases.

Case 1: $$$r$$$ is even and $$$c$$$ is even

Choose some $$$(x,y)$$$ and do an operation on all $$$(i,j)$$$ where $$$i=x$$$ or $$$j=y$$$. The effect of this series of operations is toggling $$$(x,y)$$$.

All possible grids are reachable. Counting them is easy.

Case 2: $$$r$$$ is even and $$$c$$$ is odd

If $$$r$$$ is odd and $$$c$$$ is even, we can treat it as the same case by swapping a few variables.

Notice that every operation toggles all elements in $$$R$$$. It is neccasary that $$$R$$$ all values in R are the same, let us prove that this is sufficient as well.

Now suppose $$$R$$$ is all 0. If $$$R$$$ is all $$$1$$$. We can perform the operation on $$$(1,1)$$$ and now $$$R$$$ is all $$$0$$$.

If we pick $$$1 \leq x \leq r$$$ and $$$1 \leq y < c$$$ and perform operations on all $$$(i,j)$$$ where $$$i \neq x$$$ and $$$j=y$$$ or $$$j=c$$$, then it is equivalent to toggling $$$(x,y)$$$ and $$$(x,c)$$$.

We can perform the following new operation:

• pick $$$1 \leq x \leq r$$$ and $$$1 \leq y < c$$$
• toggle $$$(x,y)$$$,$$$(x,c)$$$

Since $$$R$$$ is all 0, each row has an even number of $$$1$$$. If we apply the new operation on all $$$(x,y)$$$ where $$$a_{x,y} = 1$$$ and $$$y < c$$$, then $$$(x,c)$$$ will be $$$0$$$ in the end. Hence, the whole grid will be $$$0$$$.

Case 3: $$$r$$$ is odd and $$$c$$$ is odd

Notice that every operation toggles all elements in $$$R$$$ and $$$C$$$. It is neccasary that both $$$R$$$ are $$$C$$$ all having the same values, let us prove that this is sufficient as well.

Suppose $$$R$$$ is all $$$0$$$ and $$$C$$$ is all $$$0$$$. If $$$R$$$ and $$$C$$$ are all $$$1$$$, we apply the operation on $$$(1,1)$$$ to make $$$R$$$ and $$$C$$$ both all $$$0$$$

Notice that if we pick $$$1 \leq x_1 < x_2 \leq r$$$ and $$$1 \leq y_1 < y_2 \leq c$$$. Let $$$S=\{(x_1,y_1), (x_1,y_2), (x_2,y_1),(x_2,y_2)\}$$$. When we perform operations on all cells in $$$S$$$, it is equivalent to toggling all cells in $$$S$$$.

We can perform the following new operation:

• pick $$$1 \leq x < r$$$ and $$$1 \leq y < c$$$
• toggle $$$(x,y)$$$,$$$(x,c)$$$,$$$(r,y)$$$,$$$(r,c)$$$

Since $$$R$$$ and $$$C$$$ is all 0, each row and column has an even number of 1. If we apply the new operation on all $$$(x,y)$$$ where $$$a_{x,y} = 1$$$ and $$$x < r$$$ and $$$y < c$$$ , then $$$(x,c)$$$ will be $$$0$$$ for $$$0 < x < r$$$ and $$$(r,y)$$$ will be $$$0$$$ for $$$0 < y < c$$$ in the end. And hence, $$$a_{r,c} = 0$$$ too since $$$R$$$ and $$$C$$$ is all 0. Hence, the whole grid will be $$$0$$$.

Alternate Justification

Thanks to dario2994 for writing this.

Let $$$V = Z_2^{nm}$$$. $$$V$$$ is endowed with the natural scalar product, which induces the concept of orthogonality.

Let $$$M$$$ be the subspace generated by the moves. Let $$$M^{\perp}$$$ be the space orthogonal to $$$M$$$. It is a basic result in linear algebra that $$$(M^{\perp})^{\perp} = M$$$.

One can see that $$$\{(x1, y1), (x1, y2), (x2, y1), (x2, y2)\}$$$ belongs to $$$M$$$ (it is a combination of 4 moves). Thus one deduces that if $$$u \in M^{\perp}$$$ then $$$u_{x,y} = a_x \oplus b_y$$$ for two vectors $$$a\in Z_2^r, b \in Z_2^c$$$. Given $$$a, b$$$; the scalar product between $$$u$$$ and the move centered at $$$(x, y)$$$ is: $$$xor(a) \oplus xor(b) \oplus (c+1)a_x \oplus (r+1)b_y$$$. Assume that $$$u$$$ is in $$$M^{\perp}$$$:

• If $$$r, c$$$ are both even, then $$$a_x$$$ and $$$b_y$$$ must be constant and equal each other. Thus $$$M^{\perp}$$$ is only the $$$0$$$ vector.
• If $$$r$$$ is even and $$$c$$$ is odd, then $$$b_y$$$ is constant. Hence $$$M^{\perp}$$$ is generated by any two rows.
• If $$$r$$$ is odd and $$$c$$$ is even, analogous.
• If $$$r$$$ and $$$c$$$ are both odd, then the only condition is $$$xor(a) \oplus xor(b) = 0$$$. This is necessary and sufficient for the orthogonality. And it implies that $$$M^{\perp}$$$ is generated by any two rows and any two columns.

Since we determined $$$M^{\perp}$$$, we have determined also $$$M$$$.

Counting

Case 1 and 2 are the easy cases while counting case 3 is more involved.

Case 1: $$$r$$$ is even and $$$c$$$ is even

All grids are obtainable. Let $$$\#?$$$ denote the number of $$$\texttt{?}$$$s in the grid. Then the answer is $$$2^{\#?}$$$ since all grid are obtainable.

Case 2: $$$r$$$ is even and $$$c$$$ is odd

If $$$r$$$ is odd and $$$c$$$ is even, we can treat it as the same case by swapping a few variables.

Let us fix whether we want $$$R=[0,0,\ldots,0]$$$ or $$$R=[1,1,\ldots,1]$$$. We will count the number of valid grids for each case.

Let $$$\#?_i$$$ denote the number of $$$\texttt{?}$$$s in the $$$i$$$-th row. If $$$\#?_i>0$$$, then then number of ways to set the $$$i$$$-th row is $$$2^{\#?_i-1}$$$. Otherwise, the number of ways is either $$$0$$$ to $$$1$$$ depending on the initial value of $$$R_i$$$.

Case 3: $$$r$$$ is odd and $$$c$$$ is odd

Let us define a bipartite graph with vertices $$$r+c$$$ vertices, labelled $$$V_{R,i}$$$ for $$$1 \leq i \leq r$$$ and $$$V_{C,j}$$$ for $$$1 \leq j \leq c$$$. If $$$a_{i,j}=\texttt{?}$$$, then we will add an (undirected) edge $$$V_{R,i} \leftrightarrow V_{C,j}$$$. Now we assume that each $$$\texttt{?}$$$ is set to $$$\texttt{0}$$$ at first. We will choose a subset of them to turn into $$$\texttt{1}$$$. When we do this on $$$a_{i,j}$$$, the value of $$$R_i$$$ and $$$C_j$$$ will toggle. In terms of the graph, this corresponds to assigning $$$0$$$ or $$$1$$$ to each edge. When we assign $$$1$$$ to the edge connecting $$$V_{R,i}$$$ and $$$V_{C,j}$$$, then $$$R_i$$$ and $$$C_j$$$ will toggle. We can consider $$$R_i$$$ and $$$C_j$$$ to be the weight of the vertices $$$V_{R,i}$$$ and $$$V_{C,j}$$$ respecitvely.

Consider a connected component of this bipartite graph. Choose an arbitrary spanning tree of this connected component. By assinging the weights of the edges in the spanning tree, we can arbitrarily set the weights of all but one vertex. We cannot arbitarily set the weight of all vertices as the xor-sum of the weight of vertices is an invariant.

Let us show that we can arbitarily choose the weights of all but one vertex on this connected component using the spanning tree. Let us arbitrarily root the tree. Choose some arbitrary leaf of the tree, if the weight of the leaf is correct, assign the edge connected to that vertex weight $$$0$$$. Otherwise, assign it weight $$$1$$$. Then remove the leaf and its corresponding edge. Actually, this shows that there is a one-to-one correspondents between the possible weights of the edges and the possible weights of the vertices.

For the edges not in the spanning tree we have chosen, we can arbitarily set their weights while we are still able to choose the weights of all but one vertex on this connected component by properly assigning weights of the edges in the spanning tree.

Suppose we want this constant value of $$$R$$$ and $$$C$$$ to be $$$v$$$, where $$$v$$$ is either $$$0$$$ or $$$1$$$.

Suppose that the connected component has size $$$n$$$, has $$$m$$$ edges and the xor of all the initial vertex weights is $$$x$$$.

If $$$n$$$ is even:

• If $$$x=0$$$, then there are $$$2^{m-n+1}$$$ ways to assign weights to edges.
• If $$$x=1$$$, then there are $$$0$$$ ways to assign weights to edges.

If $$$n$$$ is odd:

• If $$$x=v$$$, then there are $$$2^{m-n+1}$$$ ways to assign weights to edges.
• If $$$x\neq v$$$, then there are $$$0$$$ ways to assign weights to edges.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=998244353;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

int n,m;
char grid[2005][2005];

int w[4005];
vector<int> al[4005];

bool vis[4005];
int ss,par,edges;

void dfs(int i){
	if (vis[i]) return;
	vis[i]=true;
	
	ss++;
	par^=w[i];
	edges+=sz(al[i]);
	
	for (auto it:al[i]) dfs(it);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m;
	rep(x,0,n) cin>>grid[x];
	
	if (n%2>m%2){
	    swap(n,m);
		rep(x,0,2005) rep(y,0,2005) if (x<y) swap(grid[x][y],grid[y][x]);
	}
	
	// rep(x,0,n){
		// rep(y,0,m) cout<<grid[x][y]<<" "; cout<<endl;
	// }
	
	if (n%2==0 && m%2==0){
		int cnt=0;
		rep(x,0,n) rep(y,0,m) if (grid[x][y]=='?') cnt++;
		cout<<qexp(2,cnt,MOD)<<endl;
	}
	else if (n%2==0 && m%2==1){
		int cnt0=1,cnt1=1;
		
		rep(x,0,n){
			int val=0;
			int cnt=0;
			rep(y,0,m){
				if (grid[x][y]=='?') cnt++;
				else val^=grid[x][y]-'0';
			}
			if (cnt==0){
				if (val==0) cnt1=0;
				else cnt0=0;
			}
			else{
				cnt0=(cnt0*qexp(2,cnt-1,MOD))%MOD;
				cnt1=(cnt1*qexp(2,cnt-1,MOD))%MOD;
			}
		}
		
		cout<<(cnt1+cnt0)%MOD<<endl;
	}
	else{
		rep(x,0,n) rep(y,0,m){
			if (grid[x][y]!='?'){
				w[x]^=grid[x][y]-'0';
				w[y+n]^=grid[x][y]-'0';
			}
			else{
				al[x].pub(y+n);
				al[y+n].pub(x);
			}
		}
		
		int cnt0=1,cnt1=1;
		
		rep(x,0,n+m) if (!vis[x]){
			ss=0,par=0,edges=0;
			dfs(x);
			edges/=2;
			edges-=ss-1; //extra edge
			
			int mul=qexp(2,edges,MOD);
			
			if (ss%2==0){
				if (par) mul=0;
				cnt0=(cnt0*mul)%MOD;
				cnt1=(cnt1*mul)%MOD;
			}
			else{
				if (par==0){
					cnt0=(cnt0*mul)%MOD;
					cnt1=0;
				}
				else{
					cnt0=0;
					cnt1=(cnt1*mul)%MOD;
				}
			}
		}
		
		cout<<(cnt0+cnt1)%MOD<<endl;
	}
}

We can first split string $$$A$$$ into the minimum number of sections of $$$\texttt{010101}\ldots$$$ and $$$\texttt{101010}\ldots$$$. Let the number of sections be $$$K$$$. Since we can simply delete each section individually, the worst answer that we can get is $$$K$$$. Also, there is no reason to only delete part of a segment, so from here on we only assume that we delete maximal segments.

Now, we can decompose $$$A$$$ based on its $$$K$$$ sections and write it as a string $$$D$$$. The rules for the decomposition is as follows:

• $$$10\ldots01 \to x$$$
• $$$01\ldots10 \to x'$$$
• $$$10\ldots10 \to y$$$
• $$$01\ldots01 \to y'$$$

For example, the string $$$A=[0101][1][1010]$$$ becomes $$$D=y'xy$$$. Now, let us look at what our operation does on $$$D$$$.

When we remove a section of even length ($$$y$$$ or $$$y'$$$) that is not on the endpoint of the string, the left and right sections will get combined. This is because the two ends of an even section are opposite, allowing the left and right sections to merge. Otherwise, it results in no merging.

When some sections get combined, the length of string $$$D$$$ gets reduced by $$$2$$$, while the length of $$$D$$$ gets reduced by $$$1$$$ otherwise. Clearly, we want to maximize deleting the number of sections of even length that are not on the endpoints of the string. We will call such a move a power move.

Let us classify strings that have no power moves. They actually come in $$$8$$$ types:

• $$$x x \ldots x$$$
• $$$y' x x \ldots x$$$
• $$$x x \ldots x y$$$
• $$$y' x x \ldots x y$$$
• $$$x' x' \ldots x'$$$
• $$$y x' x' \ldots x'$$$
• $$$x' x' \ldots x' y'$$$
• $$$y x' x' \ldots x' y'$$$

We can prove that for any string not of this form, there will be always be character $$$y$$$ or $$$y'$$$ that is not on the ends of the string. Suppose that the string contains both $$$x$$$ and $$$x'$$$, then $$$xyx'$$$ or $$$x'y'x$$$ must be a substring. Also, the number of $$$y$$$ or $$$y'$$$s on each side cannot be more than $$$1$$$. Note that strings such that $$$y$$$ or $$$yy'$$$ may fall under multiple types.

Furthermore, for string of these types, the number of moves we have to make is equal to the length of the string.

Let us define the balance of $$$x$$$ as the number of $$$x$$$ minus the number of $$$x'$$$. We will define the balance of $$$y$$$ similarly. When we perform a power move, notice that the balance of the string is unchanged. Indeed, each power move either removes a pair of $$$x$$$ and $$$x'$$$ or $$$y$$$ and $$$y'$$$ from the string.

With this, we can easily find which type of ending string we will end up with based on the perviously mentioned invariants, except for the cases of differentiating between the string $$$x x \ldots x$$$ and $$$y' x x \ldots x y$$$ (and the case for $$$x'$$$).

To differentiate between these $$$2$$$ cases, we can note that the first character of our string does not change when we perform power moves. And indeed, $$$x$$$ and $$$y'$$$ have different starting characters.

Note that we have to be careful when the balance of $$$x$$$ and the balance of $$$y$$$ is $$$0$$$ in the initial string as for strings such as $$$yy'$$$, the final string is not $$$\varnothing$$$ but $$$yy'$$$. With this, we can answer queries in $$$O(1)$$$ since we can query the balance of $$$x$$$, the balance of $$$y$$$ and the total length of the decomposed string in $$$O(1)$$$.

Furthermore, there is a implementation trick here. Notice that if $$$a_{l-1}\neq a_l$$$, then then answer for $$$s[l-1,r]$$$ will be equal to the answer for $$$s[l,r]$$$. So in implementation, it is easier to "extend" $$$l$$$ and $$$r$$$ to find the balance of $$$x$$$ and $$$y$$$.

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

int n,q;
string s;
int l[200005];
int r[200005];
int psum[200005];
int balance[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	cin>>s;
	
	s=s[0]+s+s[n-1];
	
	for (int x=1;x<=n;x++){
		if (s[x-1]==s[x]) l[x]=x;
		else l[x]=l[x-1];
	}
	
	for (int x=n;x>=1;x--){
		if (s[x]==s[x+1]){
			r[x]=x;
			psum[x]=1;
			if ((x-l[x])%2==0){
				balance[x]=(s[x]=='1'?1:-1);
			}
		}
		else r[x]=r[x+1];
	}
	
	for (int x=1;x<=n;x++){
		psum[x]+=psum[x-1];
		balance[x]+=balance[x-1];
	}
	
	int a,b;
	while (q--){
		cin>>a>>b;
		a=l[a],b=r[b];
		
		int bl=balance[b]-balance[a-1];
		int sum=psum[b]-psum[a-1];
		
		int ans=(sum+abs(bl))/2;
		
		if ((sum+abs(bl))%2==1) ans++;
		else if (abs(bl)==0) ans++;
		else if (bl>0 ^ s[a]=='1') ans++;
		
		cout<<ans<<"\n";
	}
}

Let us rephrase the problem. Let $$$x$$$ and $$$y$$$ be arrays where $$$x_i=p_i$$$ and $$$y_i=i$$$ initially. For brevity, let $$$c_i = |x_i - y_i|$$$.

We want to check if we can do the following operation $$$n$$$ times on the array:

• Choose an index $$$i$$$ such that and $$$c_i \leq s$$$.
• For all $$$j$$$ where $$$x_i < x_j$$$, update $$$x_j \gets x_j-1$$$.
• For all $$$j$$$ where $$$y_i < y_j$$$, update $$$y_j \gets y_j-1$$$.
• Set $$$x_i \gets \infty$$$ and $$$y_i \gets -\infty$$$

Let us fix $$$s$$$ and solve the problem of checking whether a value of $$$s$$$ allows us to transform the permutation into the empty permutation.

Lemma 1

Let $$$(x,y,c)$$$ be the arrays before some arbitrary operation and $$$(x',y',c')$$$ be the arrays after that operation. If we only perform moves with $$$c_i \leq s$$$, then $$$c_j \leq s$$$ implies that $$$c'_j \leq s$$$ i.e. if something was removable before, it will be removable later if we only use valid moves.

Proof: Note that $$$x'_j = x_j$$$ or $$$x'_j=x_j-1$$$. The case for $$$y$$$ is same.

We can see that $$$c'_j \leq c_j+1$$$. So the only case where $$$c'_j > s$$$ is when $$$c_j=s$$$.

Case $$$1$$$: $$$x_j \leq y_j$$$

Then it must be that $$$x'_j=x_j$$$ and $$$y'_j=y_j-1$$$. By the definition of our operation, we have the following inequality: $$$x_i < x_j \leq y_j < y_i$$$.

This implies that $$$c_i>s$$$, which is a contradiction.

Case $$$2$$$: $$$x_j \geq y_j$$$

By similar analysis we see that $$$c_i>s$$$. $$$\blacksquare$$$

Suppose that we only remove points with $$$c_i \leq s$$$ for some fixed $$$s$$$. This greedy algorithm works here - at each step, choose any point $$$c_i \leq s$$$ with and remove it. - if no such point exists, the $$$s$$$ does not work

Proof:

Given any permutation, let any point with $$$c_a \leq s$$$ be $$$a$$$. Consider any optimal sequence of moves $$$[b_1,b_2,\ldots,b_w,a,\ldots]$$$. We can transform to another optimal solution it by moving $$$a$$$ to the front.

Let the element before $$$a$$$ to be $$$b_w$$$. We will swap $$$a$$$ and $$$b_w$$$. $$$a$$$ is already removable at the start so it will be removable after removing $$$b_1,b_2,\ldots,b_{w-1}$$$ by lemma $$$1$$$. After removing everything before $$$b_1,b_2,\ldots,b_{w-1}$$$, $$$b_w$$$ is removable, so it will be removable after removing $$$a$$$ by lemma $$$1$$$. Hence we can move $$$a$$$ to the front of the sequence of moves by repeatedly swaping elemenets.

By exchange arguement, the greedy solution of removing any point with $$$c_a \leq s$$$ is an optimal solution.

Time Complexity Speedups

By extension, the following greedy algorithm works:

Set $$$s \gets 0$$$.

• At each step, choose index $$$i$$$ with minimal $$$c_i$$$
• Update $$$s \gets \max(s,c_i)$$$
• Remove point $$$i$$$

Let's start with $$$s=0$$$ and remove things while we can. If we are at a state that we are stuck, incremenet $$$s$$$. When we increment $$$s$$$, the moves that we haved done before will still be a valid choice with this new value of $$$s$$$. We simply increment $$$s$$$ until we can remove the entire permutation which is

Now the only difficult part about this is maintaining the array $$$c_i$$$ (the cost) for the points we have not removed.

Let's define a point as good as follows:

If $$$y < x$$$, the point is good if there exist no other point $$$(x',y')$$$ such that $$$y < y' \leq x' < x$$$.

Otherwise, the point is good if there exist no other point $$$(x',y')$$$ such that $$$x < x' \leq y' < y$$$.

We maintain only the good elements, because only good elements are candidates for the minimum $$$c_i$$$. Suppose element is not good and minimal, then the point that causes it to be not good has a strictly smaller cost, an obvious contradiction.

Now we will use data structures to maintain $$$c_i$$$ of good points. We will split the good points into the left good and right good points which are those of $$$x_i \leq y_i$$$ and $$$y_i \leq x_i$$$ respectively. Notice that if $$$x_i = y_i$$$, then it is both left good and right good.

We will focus on the left good points. Suppose $$$i$$$ and $$$j$$$ are both left good with $$$x_i < x_j$$$, then $$$y_i < y_j$$$. Suppose otherwise, then we have $$$x_i < x_j \leq y_j < y_i$$$, making $$$i$$$ not good. As such $$$x$$$ and $$$y$$$ of the left good points are monotone.

To find this monotone chain of left good points, we can maintain a max segment tree which stores max $$$y$$$ for all alive $$$x$$$. Using binary search on segment tree to find the unique point with $$$x' > x$$$ such that $$$y'$$$ is minimized. Where $$$(x,y)$$$ is a point on the chain, and $$$(x',y')$$$ is the next point. We can repeatedly do this to find the entire chain of left good elements

We can store a segment tree where $$$i$$$ is the key and $$$c_i$$$ is the value. If an element is left good, it will always be left good until it is removed.

The following two operations are simply range updates on the segment tree since $$$y_i$$$ is monotone. - For all $$$j$$$ such that $$$x_j>x_i$$$, set $$$x_j \leftarrow x_j-1$$$. - For all $$$j$$$ such that $$$y_j<y_i$$$, set $$$y_j \leftarrow y_j-1$$$.

Now, when we remove some left good point, some other points will become left good, and we will need to add them. We do this by starting from the previous element of the left good chain, and then keep repeating the same algo using descend on the segment tree.

When we add a new left good point, we need to know the cost at the current point in time. If we consider a point which is initially $$$(x,y)$$$, and all other previously removed $$$(x',y')$$$, $$$x$$$ decreases by 1 per $$$x' < x$$$ and $$$y$$$ decreases by 1 per $$$y' < y$$$. Hence, we can maintain a fenwick tree of the removed point's $$$x$$$ and $$$y$$$, and using that we can determine the $$$x$$$ and $$$y$$$ at the time when we add it to the left good chain (and hence to the segment tree).

Time Complexity: $$$O(n \log n)$$$

Quad Trees

Thanks to dario2994 for pointing this out.

Surprisingly quad trees are provably $$$O(n \sqrt n)$$$ here. Take the $$$k$$$-th layer of the quad tree. The $$$n \cdot n$$$ grid will be split into $$$4^k$$$ squares in the $$$k$$$-th layer. Since we are doing half plane covers, our query range will only touch $$$2^k$$$ squares. At the same time, the width of those $$$2^k$$$ squares is $$$\frac{n}{2^k}$$$. Since each column only has a single element, our query range will also by bounded by $$$\frac{n}{2^k}$$$. The time complexity for a single update is given by $$$\sum\limits_{k=1}^{\log n} \min(2^k,\frac{n}{2^k}) = O(\sqrt n)$$$.

// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define ii pair<int,int>
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct FEN{
	int fen[500005];
	
	FEN(){
		memset(fen,0,sizeof(fen));
	}
	
	void upd(int i,int j){
		while (i<500005){
			fen[i]+=j;
			i+=i&-i;
		}
	}
	
	int query(int i){
		int res=0;
		while (i){
			res+=fen[i];
			i-=i&-i;
		}
		return res;
	}
} fval,fidx;

struct dat{
	struct node{
		int s,e,m;
		ii val;
		int lazy=0;
		node *l,*r;
		
		node (int _s,int _e){
			s=_s,e=_e,m=s+e>>1;
			val={1e9,s};
			
			if (s!=e){
				l=new node(s,m);
				r=new node(m+1,e);
			}
		}
		
		void propo(){
			if (lazy){
				val.fi+=lazy;
				if (s!=e){
					l->lazy+=lazy;
					r->lazy+=lazy;
				}
				lazy=0;
			}
		}
		
		void update(int i,int j,int k){
			if (s==i && e==j) lazy+=k;
			else{
				if (j<=m) l->update(i,j,k);
				else if (m<i) r->update(i,j,k);
				else l->update(i,m,k),r->update(m+1,j,k);
				
				l->propo(),r->propo();
				val=min(l->val,r->val);
			}
		}
		
		void set(int i,int k){
			propo();
			if (s==e) val.fi=k;
			else{
				if (i<=m) l->set(i,k);
				else r->set(i,k);
				
				l->propo(),r->propo();
				val=min(l->val,r->val);
			}
		}
	} *root=new node(0,500005);
	
	struct node2{
		int s,e,m;
		int val=-1e9;
		node2 *l,*r;
		
		node2 (int _s,int _e){
			s=_s,e=_e,m=s+e>>1;
			
			if (s!=e){
				l=new node2(s,m);
				r=new node2(m+1,e);
			}
		}
		
		void update(int i,int k){
			if (s==e) val=k;
			else{
				if (i<=m) l->update(i,k);
				else r->update(i,k);
				val=max(l->val,r->val);
			}
		}
		
		ii query(int i,int key){ //find key<=val where i<=s
			if (e<i || val<key) return {-1,-1};
			if (s==e) return {s,val};
			else{
				auto temp=l->query(i,key);
				if (temp!=ii(-1,-1)) return temp;
				else return r->query(i,key);
			}
		}
	} *root2=new node2(0,500005);
	
	set<ii> s={ {500005,500005} };
	
	//root stores the values of each pair
	//root2 stores the left endpoint of each pair to add non-overlapping ranges
	//s stores the pairs are still alive so its easy to do searches
	
	dat *d; //we also store the other guy
	bool orien; //false for i->arr[i]
	
	int pp[500005];
	
	void push(int i,int j){
		pp[j]=i;
		root2->update(j,i);
	}
	
	void add(int i,int j){
		root2->update(j,-1e9);
		s.insert({i,j});
		
		int val;
		if (!orien) val=fval.query(j)-fidx.query(i);
		else val=fidx.query(j)-fval.query(i);
		
		root->set(j,val);
	}
	
	void del(int j){
		ii curr={-1,-1};
		int lim=500005;
		
		if (j!=-1){
			int i=pp[j];
			
			auto it=d->s.ub({j,1e9});
			d->root->update(i,(*it).se-1,-1);
			
			if (!orien) fidx.upd(i,-1),fval.upd(j,-1);
			else fval.upd(i,-1),fidx.upd(j,-1);
			
			it=s.find({i,j});
			if (it!=s.begin()) curr=*prev(it);
			lim=(*next(it)).se;
			s.erase(it);
			root->set(j,1e9);
			root2->update(j,-1e9);
		}
		
		while (true){
			auto temp=root2->query(curr.se,curr.fi);
			swap(temp.fi,temp.se);
			if (temp==ii(-1,-1) || lim<=temp.se) break;
			
			add(temp.fi,temp.se);
			curr=temp;
		}
	}
} *l=new dat(),*r=new dat();

int n;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	//cyclic mapping to each other
	l->d=r;
	r->d=l;
	
	r->orien=true;
	
	cin>>n;
	rep(x,1,n+1){
		int y;
		cin>>y;
		
		if (x<=y) l->push(x,y);
		else r->push(y,x);
	}
	
	rep(x,1,n+1) fidx.upd(x,1),fval.upd(x,1);
	l->del(-1);
	r->del(-1);
	
	int ans=0;
	
	rep(x,0,n){
		if (l->root->val.fi<=r->root->val.fi){
			ans=max(ans,l->root->val.fi);
			l->del(l->root->val.se);
		}
		else{
			ans=max(ans,r->root->val.fi);
			r->del(r->root->val.se);
		}
	}
	
	cout<<ans<<endl;
}

#include <nmmintrin.h>

#pragma GCC target("avx2")

int main() {
    /******   LOADING   ******/

    __m128i zero = _mm_setzero_si128(); // set everything to 0
    __m128i eight = _mm_set1_epi32(8); // set the vector of 4 integers to be equal to 8

    __m128i pi = _mm_setr_epi32(3, 1, 4, 1); // NOTE: set and setr are opposites of each other
    // mm_setr_epi32(3, 1, 4, 1) -> first value == 3, second value == 1, third value == 4, forth value == 1
    // mm_set_epi32(3, 1, 4, 1) -> first value == 1, second value == 4, third value == 1, forth value == 3

    int arr[8] = {0, 1, 2, 3, 4, 5, 6, 7};
    __m128i a0 = _mm_loadu_si128((__m128i*) &arr[0]); // [0, 1, 2, 3]
    __m128i a4 = _mm_loadu_si128((__m128i*) &arr[4]); // [4, 5, 6, 7]

    __m128i a2 = _mm_loadu_si128((__m128i*) &arr[2]); // [2, 3, 4, 5]
    // _mm_insert_epi32(a, i, j) changes j-th number of a to value i
    a2 = _mm_insert_epi32(a2, 99, 1); // [2, 99, 4, 5]

    /******   ARITHMETIC   ******/

    __m128i sm = _mm_add_epi32(a0, a4); // [4, 6, 8, 10] (sum i-th element of a0 with i-th element of a4)
    __m128i mx = _mm_max_epi32(pi, a0); // [3, 1, 4, 3] (maximum of the i-th element of pi and i-th element of a0)
    __m128i sb = _mm_sub_epi32(pi, a0); // [3, 0, 2, -2] (subtract i-th element of a0 from i-th element of pi)

    __m128i smallmul = _mm_mullo_epi32(sm, mx); // [12, 6, 32, 30] (multiply i-th element of sm with mx)
    __m128i mul = _mm_mul_epi32(sm, mx); // [12, 32] (4*3=12, 8*4=32)

    /******   LOGICAL ARITHMETIC   ******/

    __m128i three = _mm_set1_epi32(3);
    // _mm_cmplt_epi32(a, b) returns mask containing a less than b
    __m128i mskl = _mm_cmplt_epi32(pi, three); // contains [0, 2^32-1, 0, 2^32-1] as only 1 < 3
    // _mm_cmpgt_epi32(a, b) returns mask containing a greater than b
    __m128i mskg = _mm_cmpgt_epi32(pi, three); // contains [0, 0, 2^32-1, 0]
    // _mm_cmpeq_epi32(a, b) returns mask containing a equal to b
    __m128i mske = _mm_cmpeq_epi32(pi, three); // contains [2^32-1, 0, 0, 0]

    __m128i mix = _mm_blendv_epi8(eight, pi, mskl); // contains [8, 1, 8, 1]

    /******   REORDERING   ******/

    __m128i a = _mm_setr_epi32(1, 2, 3, 4);
    a = _mm_shuffle_epi32(a, 0b00100111); // [4, 2, 3, 1]

    a = _mm_setr_epi32(1, 2, 3, 4);
    a = _mm_slli_si128(a, 8); // [0, 0, 1, 2]

    a = _mm_setr_epi32(1, 2, 3, 4);
    a = _mm_srli_si128(a, 4); // [2, 3, 4, 0]

    a = _mm_setr_epi32(1, 2, 3, 4);
    __m128i b = _mm_setr_epi32(5, 6, 7, 8);
    a = _mm_alignr_epi8(a, b, 8); // [7, 8, 1, 2]

    /******   EXTRACTING   ******/

    int mxarr[4];
    _mm_storeu_si128((__m128i*) mxarr, mx); // stores values of mx into mxarr
    long long mularr[2];
    _mm_storeu_si128((__m128i*) mularr, mul); // stores values of mul into mularr

    // mul = [12, 32]
    long long mul0 = _mm_extract_epi64(mul, 0); // extract the 0-th element of mul (= 12)
    // sm = [4, 6, 8, 10]
    int sm0 = _mm_extract_epi32(sm, 2); // extract the 2-nd element of sum (= 8)

    /******   OTHERS   ******/

    __m128i llsm = _mm_cvtepi32_epi64(sm); // converts first 2 numbers of sm into 64-bit integers
    // _mm_extract_epi64(llsm, 0) == 4 && _mm_extract_epi64(llsm, 1) == 6
}

REP(x,n){
    if(!inA[x]){
        REP(v,n){
            int a=v,b=(v^x);
            if(find(a)!=find(b)){
                edges.pb({a,b});
                merge(a,b);
            }
            else{
                break;
            }
        }
    }
}

Submission

for(int x=1;x<n;x++){
    if(!inA[x]) continue;
    if(uf.same(0,x)) continue;
    for(int v=0;v<n;v++) add_edge(v,v^x);
}

Submission