#include<bits/stdc++.h>
using namespace std;
int n,a[109],k;
long long C;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d %lld %d",&n,&C,&k);
		for(int i = 1; i <= n; i ++){
			scanf("%d",&a[i]);
		}
		sort(a + 1,a + n + 1);
		for(int i = 1; i <= n; i ++){
			if(a[i] > C)
				break;
			int o = min(1ll * k,C - a[i]);
			k -= o;
			C += a[i] + o;
		}
		printf("%lld\n",C);
	}
}

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)])

#include<bits/stdc++.h>
using namespace std;
int n,a[5009],bcnt,f1[5009],f2[5009];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i = 1; i <= n; i ++){
			scanf("%d",&a[i]);
		}
		for(int i = n; i >= 1; i --){
		    f1[i] = f2[i] = 0;
			for(int j = i + 1; j <= n; j ++)
			    f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]);
			f1[i] = max(f1[i],f2[i]);
		}
		for(int i = 1; i < n; i ++)
		    printf("%d ",f1[i]);
		printf("%d\n",f1[n]);
	}
}

for _ in range(int(input())):
    n = int(input())
    ans = -1
    for i in range(1, n):
        print("?", 2 * i + 1, 2 * i + 2, flush=True)
        if int(input()):
            ans = 2 * i + 1 
            break
    else:
        print("?", 1, 3, flush=True)
        if int(input()):
            ans = 1
        else:
            print("?", 1, 4, flush=True)
            if int(input()):
                ans = 1
            else:
                ans = 2
    print("!", ans, flush=True)

#include<bits/stdc++.h>
using namespace std;
int t,r,g,b,rb,gb,rg;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d %d",&r,&g,&b);
		while(((r > 0) + (g > 0) + (b > 0)) >> 1){
			if(r <= g && r <= b)
				gb ++,g --,b --;
			else if(g <= r && g <= b)
				rb ++,r --,b --;
			else if(b <= r && b <= g)
				rg ++,r --,g --;
		}
		if(g > 0){
		    putchar('G');
		    while(rg > 0)
		   		putchar('R'),putchar('G'),rg --;
		   	bool flg = false;
		   	while(gb > 0)
		   		putchar('B'),putchar('G'),gb --,flg = true;
		    	if(flg){
		   		while(rb > 0)
		    			putchar('B'),putchar('R'),rb --;
		    	}
		    	else{
		    		while(rb > 0)
	    				putchar('R'),putchar('B'),rb --;
		    	}
		}
		else if(r > 0){
			putchar('R');
			while(rg > 0)
				putchar('G'),putchar('R'),rg --;
			bool flg = false;
			while(rb > 0)
				putchar('B'),putchar('R'),rb --,flg = true;
			if(flg){
				while(gb > 0)
					putchar('B'),putchar('G'),gb --;
			}
			else{
				while(gb > 0)
					putchar('G'),putchar('B'),gb --;
			}
		}
		else{
			if(b > 0)
				putchar('B');
			while(gb > 0)
				putchar('G'),putchar('B'),gb --;
			bool flg = false;
			while(rb > 0)
				putchar('R'),putchar('B'),rb --,flg = true;
			if(flg){
				while(rg > 0)
					putchar('R'),putchar('G'),rg --;
			}
			else{
				while(rg > 0)
					putchar('G'),putchar('R'),rg --;
			}
		}
		puts("");
	}
} 

import sys
input = lambda: sys.stdin.readline().strip()
def work(s):
    n = len(s)
    p = [0] * n
    b = [0] * n
    for i in range(1, n):
        j = p[i - 1]
        while j and s[i] != s[j]:
            j = p[j - 1]
        if s[i] == s[j]:
            j += 1
        p[i] = j
        if j == 0:
            b[i] = 0
        elif p[j - 1] == 0:
            b[i] = j
        else:
            b[i] = b[j - 1]
    ans = 0
    for i in range(n):
        p[i] = 0
        p[i] = p[i - b[i]] + 1
        ans += p[i]
    return ans

for _ in range(int(input())):
    n, q = map(int, input().split())
    s = input()
    for _ in range(q):
        l, r = map(int, input().split())
        print(work(s[l - 1:r]))

#include<bits/stdc++.h>
using namespace std;
const int N = 300009;
int n,k,t,a[N],tt[N];
long long b[N],ans[N],sum,mxa;
struct FLONG{
	long long val;
	int nd;
	FLONG(long long v = 0,int d = 0):
		val(v),nd(d)
	{}
	bool operator<(const FLONG &b)const{
		return val > b.val || (val == b.val && nd < b.nd);
	}
};
set<FLONG>s;
set<FLONG> :: iterator o;
struct pir{
	int to,len;
	pir(int t = 0,int l = 0):
		to(t),len(l)
	{}
	bool operator<(const pir &b)const{
		return len > b.len || (len == b.len && to < b.to);
	}
}mn[N],se[N],lf[N];
vector<int>e[N];
void srh(int v,int fa){
	mn[v] = pir(v,0);
	se[v] = pir(0,~0x3f3f3f3f);
	lf[v] = pir(0,~0x3f3f3f3f);
	for(unsigned i = 0; i < e[v].size(); i ++){
		if(e[v][i] != fa){
			srh(e[v][i],v);
			pir th = mn[e[v][i]];
			th.len ++;
			if(th < se[v])
				swap(th,se[v]);
			if(se[v] < mn[v])
				swap(se[v],mn[v]);
		}
	}
}
void gt1(){
	sum = ans[1] = 0;
	ans[1] += a[1];
	for(int i = 2; i <= n; i ++){
		b[mn[i].to] += a[i];
		tt[i] = mn[i].to;
		//printf("%d %d\n",i,tt[i]);
	}
	s.clear();
	for(int i = 2; i <= n; i ++){
		s.insert(FLONG(b[i],i));
	}
	o = s.begin();
	ans[1] += o -> val;
	sum += o -> val;
	for(int i = 1; i < k - 1; i ++){
		o ++;
		ans[1] += o -> val;
		sum += o -> val;
	}
	s.insert(FLONG(-1ll,0));
	s.insert(FLONG(-2ll,0));
}
void era(int x){
	FLONG u = FLONG(b[x],x);
	if(!(*o < u)){
		o ++;
		sum += o -> val;
		sum -= b[x];
	}
	s.erase(u);
	//printf("%d %lld\n",x,sum);
}
void ins(int x){
	FLONG u = FLONG(b[x],x);
	s.insert(u);
	if(!(*o < u)){
		sum -= o -> val;
		sum += b[x];
		o --;
	}
	//printf("%d %lld\n",x,sum);
}
void stp(int x){
	era(tt[x]);
	b[tt[x]] -= a[x];
	ins(tt[x]);
	tt[x] = 0; 
}
void sett(int x,int ttp){
	tt[x] = ttp;
	era(tt[x]);
	b[tt[x]] += a[x];
	ins(tt[x]);
}
void srho(int v,int fa){
	//printf(" %d %d\n",v,fa);
	if(fa != 0){
		stp(v);
		era(v);
		ins(fa);
		sett(fa,lf[fa].to);
		ans[v] = sum + a[v];
	}
	for(unsigned i = 0; i < e[v].size(); i ++){
		if(e[v][i] != fa){
			pir u = lf[fa];
			u.len ++;
			if(mn[v].to == mn[e[v][i]].to)
				lf[v] = min(u,se[v]);
			else
				lf[v] = min(u,mn[v]);
			srho(e[v][i],v);
		}
	}
	if(fa != 0){
		ins(v);
		sett(v,mn[v].to);
		stp(fa);
		era(fa);
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&k);
		mxa = 0;
		for(int i = 1; i <= n; i ++){
			scanf("%d",&a[i]);
			mxa = max(mxa,1ll * a[i]);
			e[i].clear();
			b[i] = 0;
		}
		for(int i = 1; i < n; i ++){
			int u,v;
			scanf("%d %d",&u,&v);
			e[u].emplace_back(v);
			e[v].emplace_back(u);
		}
		if(k == 1){
			printf("%lld\n",mxa);
			continue;
		}
		lf[0].len = ~0x3f3f3f3f;
		srh(1,0);
		gt1();
		srho(1,0);
		for(int i = 1; i <= n; i ++){
			mxa = max(mxa,ans[i]);
			//printf("%lld\n",ans[i]);
		}
		printf("%lld\n",mxa);
	}
}

For $$$|p_{n-1}-p_n|$$$ to be divisible by $$$n-1$$$, either $$$p_{n-1}=1$$$ and $$$p_n=n$$$, or $$$p_{n-1}=n$$$ and $$$p_n=1$$$. Either way, we can construct $$$p$$$ backwards. For $$$i$$$ from $$$n-2$$$ to $$$1$$$, there will only by one possible choice for $$$p_i$$$, where $$$p_i$$$ is either $$$p_{i+1}-i$$$ or $$$p_{i+1}+i$$$, depending on the parity of $$$i$$$.

for _ in range(int(input())):
    n = int(input())
    p = [1, n]
    used = {1, n}
    for i in range(n - 2, 0, -1):
        prev = p[-1]
        if 1 <= prev - i <= n and prev - i not in used:
            p.append(prev - i)
            used.add(prev - i)
        else:
            p.append(prev + i)
            used.add(prev + i)
    p.reverse()
    print(*p)

We can divide the string into segments that contain only zeros. For one segment that is bounded by two ones, the answer is $$$\lfloor \frac{len}{3} \rfloor$$$.

If a segment of zeros is adjacent to the start or the end of the row, we need to introduce extra zeros. This is because in the proof, the boundary that the remaining zeros can be placed are reduced. If the whole string consist of zeors, we need to introduce two zeros. Otherwise, we need to introduce one zero.

By summing up the contributions of the segments, we can solve the answer.

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    s = '1' + s + '1';
    int ans = 0;
    for (int i = 1, l = 0; i <= n; ++i) {
        if (s[i] == '0') {
            if (s[i-1] == '1') {
                l = i;
            }
            if (s[i+1] == '1') {
                int c = (l == 1) + (i == n);
                ans += (i - l + 1 + c) / 3;
            }
        } else {
            ++ans;
        }
    }
    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) solve();
    return 0;
}

For any array of elements, if you can somehow swap any pair of elements (maybe indirectly), you can always sort the array.

For some $$$i,j$$$ such that $$$|a_i-a_j| \lt k$$$, how to swap them with help from other elements?

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    if a == b:
        print(-1)
        continue
    print(min(max(a[i] - b[0], b[-1] - a[i]) for i in range(n) if a[i] != b[i]))

Greedy.

Let $$$ x, y \in \mathbb{Z}_{\ge 0} $$$.
We consider the optimization problem

where $$$\&$$$ denotes the bitwise AND operation.

Equivalent Formulation

Define

Define also the restricted optima

Proposition

Equivalently:

There exists an optimal solution $$$(p,q)$$$ such that $$$p = x$$$ or $$$q = y$$$.

Proof of Equivalence

• If an optimal solution satisfies $$$p = x$$$, then its cost equals $$$|y - q|$$$ for some $$$q$$$ with $$$x \& q = 0$$$, hence $$$\mathrm{OPT} = \mathrm{OPT}_x$$$.
• Similarly, if an optimal solution satisfies $$$q = y$$$, then $$$\mathrm{OPT} = \mathrm{OPT}_y$$$.
• Conversely, if the equality holds, the minimizer in the attaining branch gives an optimal solution with $$$p=x$$$ or $$$q=y$$$.

Inductive Proof on Bit-Length

Fix an integer $$$n \ge 1$$$.
Assume

Let

Write the binary decompositions

where

The constraint $$$p \& q = 0$$$ implies:

1. $$$p_1$$$ and $$$q_1$$$ cannot both be $$$1$$$,
2. $$$p_0 \& q_0 = 0$$$.

Case 1: No Conflict $$$(x_1,y_1) \neq (1,1)$$$

In this case, the highest bit does not force a trade-off.

Lemma 1

If $$$x_1 = 0$$$, then there exists an optimal solution with $$$p_1 = 0$$$. Similarly, if $$$y_1 = 0$$$, there exists an optimal solution with $$$q_1 = 0$$$.

Proof

Assume $$$x_1 = 0$$$ but $$$p_1 = 1$$$. Replace $$$p$$$ by $$$p' = p - W$$$.

• Feasibility: clearing a bit of $$$p$$$ cannot create a new $$$1 \& 1$$$ conflict.
• Optimality: since $$$x \lt W$$$,

Thus $$$p_1$$$ can be set to $$$0$$$ without increasing cost.
The argument for $$$q$$$ is symmetric.

Hence we may assume

The objective becomes

This reduces the problem to the $$$(n-1)$$$-bit instance $$$(x_0,y_0)$$$. By the inductive hypothesis, there exists an optimal solution with $$$p_0 = x_0$$$ or $$$q_0 = y_0$$$, hence $$$p = x$$$ or $$$q = y$$$.

Case 2: Conflict $$$(x_1,y_1) = (1,1)$$$

Now the highest bit conflicts, so

Lemma 2

We could Exclusion of $$$(0,0)$$$.

Proof

Any feasible solution with

satisfies

Moreover, there exists a feasible solution with $$$(p_1,q_1) = (1,0)$$$ and cost

Since $$$x = W + x_0 \gt p$$$ and $$$y = W + y_0 \gt q$$$,

If $$$p & q = 0$$$, then binary addition has no carry, hence

Therefore

Now define

Since $$$q'$$$ is the bitwise complement of $$$x_0$$$ on the lower $$$n-1$$$ bits,

The cost is

Since $$$W \ge 1$$$,

Thus the $$$(0,0)$$$ case cannot be optimal.

Lemma 3

Fix $$$(p_1,q_1) = (1,0)$$$. Then there exists an optimal solution with $$$p = x$$$.

Proof

Write $$$p = W + p_0$$$, $$$q = q_0$$$. The cost is

For fixed $$$p_0$$$, this is minimized by maximizing $$$q_0$$$ subject to $$$p_0 \& q_0 = 0$$$, i.e.

The resulting cost is

Define $$$g(t) = t + |x_0 - t|$$$. Then

Hence the minimum is attained at $$$t = x_0$$$, yielding $$$p = x$$$.

By symmetry, in the $$$(0,1)$$$ case there exists an optimal solution with $$$q = y$$$.

Conclusion

In all cases, there exists an optimal solution $$$(p,q)$$$ satisfying

Equivalently,

Proofs of the intended solution are similar with this.

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 x, y;
    std::cin >> x >> y;
    i64 min = 1e18, p, q;
    auto upd = [&](i64 _p, i64 _q) -> void {
        if ((_p & _q) == 0 && abs(_p - x) + abs(_q - y) < min) {
            min = abs(_p - x) + abs(_q - y);
            p = _p;
            q = _q;
        }  
    };
    upd(x, y);
    for (int i = 29; i >= 0; i--) {
        if ((x & y) >> i & 1) {
            upd((x >> i << i) + (1LL << i), y);
            upd(x, (y >> i << i) + (1LL << i));
            upd(x >> i << i, (y >> i << i) - 1);
            upd((x >> i << i) - 1, y >> i << i);
        }
    }
    std::cout << p << " " << q << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

What is the optimal strategy for both players?

If you have obtained a formula for $$$f(x,y)$$$, how do you calculate the required sum efficiently, perhaps using some tree techniques?

#include <bits/stdc++.h>
 
using namespace std;
 
using i64 = long long;
 
i64 solve_tree(int n, int r, vector<vector<int>> g) {
    vector<int> dep(n), sz(n, 1), pa(n);
    i64 ans = 0;
    auto dfs = [&](auto &&self, int u, int p) -> map<int, int> {
        pa[u] = p;
        map<int, int> mp;
        mp[dep[u]] = 1;
        for (auto v : g[u]) if (v != p) {
            dep[v] = dep[u] + 1;
            auto nmp = self(self, v, u);
            if (mp.size() < nmp.size()) swap(mp, nmp);
            for (auto &[d, f] : nmp) {
                ans += 1LL * f * mp[d] * (d - dep[u]);
                mp[d] += f;
            }
            sz[u] += sz[v];
        }
        return mp;
    };
    dfs(dfs, r, -1);
    for (int u = 0; u < n; u++) {
        i64 s = 1LL * sz[u] * (sz[u] - 1) / 2;
        for (auto v : g[u]) if (v != pa[u]) s -= 1LL * sz[v] * (sz[v] - 1) / 2;
        ans -= 1LL * dep[u] * s;
    }
    sort(dep.begin(), dep.end());
    for (int u = 0; u < n; u++) ans += 1LL * dep[u] * (n - u - 1);
    return ans;
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n - 1; i++) a[i] = i + 1;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        a[u] = max(a[u], v);
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) g[a[i]].push_back(i);
    cout << solve_tree(n, n - 1, g) << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) solve();
}

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

#include <bits/stdc++.h>

using namespace std;

using B = bitset<100001>;

using i64 = long long;
using i128 = __int128_t;

constexpr i64 MOD = 998244353;

vector<i64> calc(int n, string &s, i64 x, i64 y) {
    B bf0, bf1, br0, br1;
    bf0.set(0);
    br0.set(0);
    for (auto c : s) {
        B nbf0, nbf1, nbr0, nbr1;
        if (c != '1') {
            nbf0 |= bf0 << 1;
            nbf1 |= bf1 << 1;
            nbr0 |= br0 >> 1;
            nbr1 |= br1 >> 1;
        }
        if (c != '0') {
            nbf0 |= br1;
            nbf1 |= br0;
            nbr0 |= bf1;
            nbr1 |= bf0;
        }
        nbf0[0] = nbf0[0] | nbr0[0];
        nbr0[0] = nbr0[0] | nbf0[0];
        nbf1[0] = nbf1[0] | nbr1[0];
        nbr1[0] = nbr1[0] | nbf1[0];
        bf0 = nbf0;
        bf1 = nbf1;
        br0 = nbr0;
        br1 = nbr1;
    }
    vector<i64> res;
    auto tosum = [&](i64 c) -> i64 {
        return (i128(c) * c + i128(x - y) * c + i128(n) * x * y) / (2 * x);
    };
    for (int i = 0; i <= n; i++) {
        if (bf0[i]) res.push_back(tosum(i * x));
        if (bf1[i]) res.push_back(tosum(i * x + y));
    }
    for (int i = 1; i <= n; i++) {
        if (br0[i]) res.push_back(tosum(-i * x));
        if (br1[i]) res.push_back(tosum(-i * x + y));
    }
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

void solve() {
    int n;
    cin >> n;
    i64 x, y;
    cin >> x >> y;
    string s;
    cin >> s;
    auto rs = calc(n, s, x, y);
    i64 ans = 0;
    for (auto v : rs) ans = (ans + (v % MOD + MOD)) % MOD;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();

}

Can you transform some constraints of the problem into something easier to handle?

Try to come up with a dynamic programming solution that runs in polynomial time.

How do you optimize your solution? Pay attention to any unusual constraints.

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    f = [10 ** 9] * 320
    f[0] = 0
    for i in range(n):
        if s[i] == "1":
            for j in range(318, -1, -1):
                f[j + 1] = min(f[j + 1], f[j])
        nf = [10 ** 9] * 320
        for j in range(320):
            nf[j] = min(nf[j], max(f[j], a[i]) + max(1, 2 * j - 1))
            if j:
                nf[j - 1] = min(nf[j - 1], f[j] + 2 * j - 1)
        print(nf[0]) 
        f = nf

Solve the problem in $$$O(n \operatorname{polylog} n)$$$.

Processing two permutations is difficult. How can we reduce them to one?

In a DFS order, the nodes of any subtree form a contiguous segment, with the root of the subtree appearing at the very beginning of that segment. What property does this imply for our problem?

The property that a segment must be a "permutation of a specific set" is not straightforward to check directly. Is there a way to simplify this condition into something more computationally efficient?

Because each valid segment can be mapped to a subtree, the valid segments form a laminar family (i.e., they do not cross). Any two valid segments are either completely disjoint or one is strictly contained inside the other.

The problem asks for the largest depth. To achieve this, we can greedily find the largest valid segment for every fixed start position.

Read the hints above.

Recall that we need to solve for any $$$1 \le l \le n$$$, the largest $$$r$$$ such that:

• $$$c[l] = \min(c[l \dots r])$$$
• $$$\max(c[l \dots r]) - \min(c[l \dots r]) = r - l$$$

There are multiple ways to solve this. We will introduce a divide-and-conquer approach.

To solve this problem using a divide-and-conquer approach, we define a recursive function that processes the interval $$$[l, r]$$$. The core logic handles the sub-problems where the valid range $$$[i, j]$$$ crosses the midpoint $$$mid$$$ (with $$$l \le i \le mid \lt j \le r$$$).

We precompute the prefix minimums and maximums for the right half ($$$mid + 1 \dots r$$$) and the suffix minimums and maximums for the left half ($$$l \dots mid$$$). Let's denote the suffix values for index $$$i$$$ as $$$min[i]$$$ and $$$max[i]$$$, and similarly for the prefix values at index $$$j$$$.

The problem requires $$$c[i] = \min(c[i \dots j])$$$. Since we are iterating $$$i$$$ from $$$mid$$$ down to $$$l$$$, this condition implies that $$$c[i]$$$ must be the minimum of the left part $$$c[i \dots mid]$$$. If $$$min[i] \neq min[i+1]$$$, it indicates that $$$c[i]$$$ is strictly smaller than the minimum of the range to its right, making it a candidate for the global minimum.

For such valid $$$i$$$, we consider two cases based on the location of the maximum value in the range $$$[i, j]$$$:

Case 1: The Maximum is on the Left

If the maximum value of the range is determined by the left side (i.e., $$$\max(c[i \dots j]) = max[i]$$$), the equation $$$\max - \min = j - i$$$ can be rewritten to determine the specific target index $$$j$$$:

We simply calculate this candidate $$$j$$$ and verify three conditions:

• $$$j$$$ is within the valid right range ($$$mid \lt j \le r$$$).
• The minimum on the right does not contradict our global minimum assumption ($$$min[j] \gt min[i]$$$).
• The maximum on the right is not larger than our current maximum ($$$max[j] \lt max[i]$$$).

If these hold, we update the answer for $$$i$$$.

Case 2: The Maximum is on the Right

If the maximum value is on the right side (i.e., $$$\max(c[i \dots j]) = max[j]$$$), the equation becomes:

Rearranging the terms to separate $$$i$$$ and $$$j$$$, we get:

To solve this efficiently, we group the indices $$$j$$$ from the right half based on the value of $$$max[j] - j$$$. For each $$$i$$$, we simply access the corresponding group to find the largest $$$j$$$ that satisfies the remaining validity conditions ($$$min[j] \gt min[i]$$$ and $$$max[j] \gt max[i]$$$). Because $$$max[j]$$$ is monotonic, we can introduce two-pointer strategy to avoid the $$$\log$$$ factor.

By conducting this algorithm, we can solve the largest valid segments for each start position. Then, we can use a stack to simulate the dfs process of the common tree, and solve the maximum depth easily.

The time complexity is $$$O(n\log n)$$$ by careful implementation.

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n+1), b(n+1);
    for (int i = 1; i <= n; ++i) std::cin >> a[i];
    for (int i = 1; i <= n; ++i) std::cin >> b[i];
    std::vector<int> mp(n+1), c(n+1), R(n+1);
    for (int i = 1; i <= n; ++i) mp[b[i]] = i;
    for (int i = 1; i <= n; ++i) c[i] = mp[a[i]];
    for (int i = 1; i <= n; ++i) mp[c[i]] = i;
    std::vector<int> min(n + 1), max(n + 1);
    std::vector<std::vector<std::pair<int, int>>> rmax(2 * n + 1);
    std::vector<int> p(2 * n + 1);

    auto work = [&](auto &&self, int l, int r) -> void {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        self(self, l, mid);
        self(self, mid + 1, r);
        min[mid] = max[mid] = c[mid];
        for (int i = mid - 1; i >= l; --i) {
            min[i] = std::min(min[i + 1], c[i]);
            max[i] = std::max(max[i + 1], c[i]);
        }
        min[mid + 1] = max[mid + 1] = c[mid + 1];
        rmax[c[mid + 1] - mid - 1 + n].emplace_back(c[mid + 1], mid + 1);
        for (int i = mid + 2; i <= r; ++i) {
            min[i] = std::min(min[i - 1], c[i]);
            max[i] = std::max(max[i - 1], c[i]);
            rmax[max[i] - i + n].emplace_back(min[i], i);
        }
        for (int i = mid; i >= l; --i) {
            if (min[i] != min[i + 1]) {
                int j = i + max[i] - min[i];
                if (j > mid && j <= r && min[j] > min[i] && max[j] < max[i]) {
                    R[i] = std::max(R[i], j);
                }
                j = min[i] - i + n;
                while (p[j] < std::ssize(rmax[j]) && rmax[j][p[j]].first > min[i]) {
                    ++p[j];
                }
                if (p[j]) {
                    int k = rmax[j][p[j] - 1].second;
                    if (max[k] > max[i]) R[i] = std::max(R[i], k);
                }
            }
        }
        for (int i = mid + 1; i <= r; ++i) {
            rmax[max[i] - i + n].clear();
            p[max[i] - i + n] = 0;
        }
    };
    work(work, 1, n);

    std::stack<int> st;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && st.top() <= i) st.pop();
        if (R[i]) {
            st.push(R[i]);
            ans = std::max(ans, int(st.size()));
        }
    }
    std::cout << (ans + 1) << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    while (T--) solve();
    return 0;
}

The problem background is a tribute to the visual novel Symphonic Rain. I highly recommend you to play it!

Construct the optimal tree by following the approach used in F1. Two child nodes $$$a$$$ and $$$b$$$ of a node are defined as entangled if and only if $$$a$$$ and $$$b$$$ appear in different orders in the two permutations. The maximal entangled set of a node's children is defined as the largest connected component formed by the entangled relationships among its children.

Theorem $$$1$$$: Each maximal entangled set and the points in its subtree must form an interval in both DFS sequences.

Proof: Suppose one DFS sequence contains nodes $$$a, b, c$$$ such that $$$a$$$ and $$$c$$$ belong to the same maximal entanglement set while $$$b$$$ does not. Then in the other DFS sequence, all nodes after $$$b$$$ must appear after $$$a$$$ and before $$$c$$$. Thus $$$a$$$ and $$$c$$$ cannot be entangled, leading to a contradiction.

Theorem $$$2$$$: Among the maximal entangled sets of a leaf node, if any maximal entangled set contains only one node, then this maximal entangled set must be the last maximal entangled set to appear in both DFS sequences.

Proof: Suppose there exists a maximal entanglement set with a single node that is not the latest maximal entanglement set in either DFS sequence. Then all subsequent maximal entanglement sets must be able to be connected under this node, contradicting the optimal tree property.

Theorem $$$3$$$: A maximal entanglement set must be connected under the same node in any valid tree.

Proof: For a pair of entangled child nodes $$$x, y$$$ of node $$$a$$$ in an optimal tree, let $$$p_x$$$ and $$$p_y$$$ be the ancestors of $$$x$$$ and $$$y$$$, respectively. Since $$$p_x$$$ and $$$p_y$$$ cannot be points in the subtree of $$$a$$$ other than $$$a$$$ itself (otherwise it contradicts the optimal tree structure). Furthermore, since $$$x$$$ appears earlier than $$$y$$$ in some DFS sequence, traversing from $$$x$$$ to $$$y$$$ requires popping all other nodes in $$$a$$$'s subtree (because $$$p_y$$$ is not within the maximal entangled group's range). This implies that traversing from $$$x$$$ to $$$y$$$ can only be achieved by popping $$$p_y$$$ multiple times from $$$x$$$ and then attaching $$$y$$$ to $$$p_y$$$. Thus, $$$p_y$$$ must be an ancestor of $$$p_x$$$. Similarly, $$$p_x$$$ must also be an ancestor of $$$p_y$$$, so $$$p_x = p_y$$$.

Theorem $$$4$$$: If a maximal entanglement set has size greater than 1, then on any valid tree, if the parent node of this maximal entanglement set is $$$p$$$, then the subtree of all nodes within this maximal entanglement set must lie within the subtree of $$$p$$$.

Proof: Suppose a node $$$d$$$ in the subtree of some node $$$x$$$ within the maximal entanglement set does not lie within the subtree of $$$p$$$. Find a node $$$y$$$ entangled with $$$x$$$. Then, in the DFS sequence where $$$x$$$ appears before $$$y$$$, $$$d$$$ must lie between $$$x$$$ and $$$y$$$, contradicting that $$$d$$$ is not in the subtree of $$$p$$$.

Therefore, each maximal entanglement set greater than $$$1$$$ can be collapsed into a single node, treated as a leaf attached to its parent. At this point, the two DFS sequences become identical. The number of solutions is thus equal to the number of trees where the DFS sequences perfectly match and every node that was originally in a maximal entanglement set remains a leaf in the new tree. For solutions within each maximal entanglement set, we can recursively compute the number of trees matching the DFS sequence for each node within that set. Multiplying these values yields the total number of valid trees.

Consider counting the number of trees where the DFS sequence is identical to the given sequence, and every node that was originally in a maximal entanglement set remains a leaf in the new tree. Treat the DFS process as a bracket sequence: entering a new node is treated as a left bracket, and exiting a node is treated as a right bracket. If a node is a leaf, then the next bracket after its left bracket must be a right bracket. Thus, the problem asks for the number of bracket sequences that satisfy having $$$n$$$ left brackets and right brackets, where the next bracket after the $$$a_1, a_2, \dots, a_m$$$th left bracket is always a right bracket. A simple $$$O(n^2)$$$ dynamic programming approach suffices to find the answer.

The overall time complexity is $$$O(n^2)$$$.

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long ans;
int a[5000],b[5000],pa[5000],pb[5000],tvis[5000],cvis[5000],zvis[5000];
vector<int>line[5001];
int dep[5001],cntsg[5001],wp[5001];
vector<int>vec;
long long dp[5001],tdp[5001];
long long solve(){
	long long i,j,n=vec.size(),csum;
	for(i=0;i<=n;i++)dp[i]=0;
	dp[0]=1;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)tdp[j+vec[i]]=(tdp[j+vec[i]]+dp[j])%mod;
		csum=0;
		for(j=n;j>=0;j--)
		{
			csum=(csum+tdp[j])%mod;
			dp[j]=csum;
			tdp[j]=0;
		}
	}
	vec.clear();
	return dp[0];
}
void dfs(int t){
	vector<int>::iterator it;
	int i;
	for(i=0;i<cntsg[t];i++)vec.push_back(0);
	if(wp[t]==-1)ans=ans*solve()%mod;
	else
	{
		vec.push_back(1);
		dfs(wp[t]);
	}
	for(it=line[t].begin();it!=line[t].end();it++)
	{
		if(*it==wp[t])continue;
		vec.push_back(1);
		dfs(*it);
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,n,i,j,t,ccnt,r;
	for(cin>>T;T>0;T--)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			a[i]--;
			pa[a[i]]=i;
		}
		for(i=0;i<n;i++)
		{
			cin>>b[i];
			b[i]--;
			pb[b[i]]=i;
		}
		for(i=0;i<n;i++)tvis[i]=0;
		for(i=n-1;i>-1;i--)
		{
			t=pb[a[i]];
			cntsg[i]=0;
			wp[i]=-1;
			for(j=0;j<n;j++)
			{
				cvis[j]=0;
				zvis[j]=0;
			}
			ccnt=0;
			r=-1;
			for(j=0;i+j<n&&t+j<n;j++)
			{
				if(cvis[a[i+j]]==0)ccnt++;
				cvis[a[i+j]]++;
				if(cvis[a[i+j]]==0)ccnt--;
				if(cvis[b[t+j]]==0)ccnt++;
				cvis[b[t+j]]--;
				if(cvis[b[t+j]]==0)ccnt--;
				if(ccnt==0)
				{
					zvis[i+j]=1;
					r=i+j;
				}
			}
			for(j=i+1;j<=r;j++)
			{
				if(tvis[j])
				{
					line[i].push_back(j);
					tvis[j]=0;
					if(zvis[j-1])
					{
						cntsg[i]++;
						wp[i]=j;
					}
					else wp[i]=-1;
				}
			}
			if(wp[i]!=-1)cntsg[i]--;
			tvis[i]=1;
		}
		cntsg[n]=0;
		wp[n]=-1;
		for(i=0;i<n;i++)
		{
			cvis[i]=0;
			zvis[i]=0;
		}
		ccnt=0;
		r=-1;
		for(i=0;i<n;i++)
		{
			if(cvis[a[i]]==0)ccnt++;
			cvis[a[i]]++;
			if(cvis[a[i]]==0)ccnt--;
			if(cvis[b[i]]==0)ccnt++;
			cvis[b[i]]--;
			if(cvis[b[i]]==0)ccnt--;
			if(ccnt==0)
			{
				zvis[i]=1;
				r=i;
			}
		}
		for(i=0;i<n;i++)
		{
			if(tvis[i])
			{
				line[n].push_back(i);
				tvis[i]=0;
				if(i==0||zvis[i-1])
				{
					cntsg[n]++;
					wp[n]=i;
				}
				else wp[n]=-1;
			}
		}
		if(wp[n]!=-1)cntsg[n]--;
		ans=1;
		dep[n]=0;
		dfs(n);
		for(i=0;i<=n;i++)line[i].clear();
		cout<<ans<<'\n';
	}
	return 0;
}

Solve the problem in $$$O(n \log^2 n)$$$.

Observation 0: If $$$q_1,q_2,\dots,q_n$$$ is valid, then $$$q_1\bmod n+1,q_2\bmod n+1,\dots,q_n\bmod n+1$$$ is another valid $$$q$$$. This is obvious.

Therefore, we do not need the exact original labeling of values. We may assume $$$q_v=n$$$.

Define $$$Child_v={u\mid s[u][v]=1}$$$; Define $$$smn_v = min_{u\in Child_v}u$$$; Define $$$smx_v = max_{u\in Child_v}u$$$.

Observation 1: If the value at index $$$v$$$ is $$$n$$$, then the position of $$$n−1$$$ must be either $$$mn_v$$$ or $$$mx_v$$$.

Proof: If $$$q_{x}=n-1$$$, and $$$smn_v \lt x \lt smx_v$$$. Then the parent node of at least one of $$$mn_v$$$ and $$$mx_v$$$ must be $$$x$$$. This is contrary to the previous assumption.

So we only need to choose between these two candidates. We may assume $$$q_u=n-1$$$.

Define an edge $$$(u, parent_u)$$$ to cross index $$$v$$$ if $$$u$$$ and its parent lie on different sides of $$$v$$$, in other words, $$$(u-v)\cdot(parent_u-v) \lt 0$$$.

Observation 2: In every Cartesian tree during the process, the edge between index $$$u$$$ ($$$q_u=n-1$$$) and its parent $$$(u, parent_u)$$$ never cross the index $$$v$$$ ($$$q_v=n$$$).

Proof: For every node on a Cartesian tree, its parent node must be the closest node greater than it. If this edge $$$(u, parent_u)$$$ crosses node v, then one side's closest point to node u becomes v, leading to a contradiction.

Now let's decide whether $$$n−1$$$ is on the left or right. We are at index $$$v$$$ (treat it as value $$$n$$$).

Case A: all extreme children are on one side. If $$$smx_v \lt v$$$, then every child that ever attaches to $$$v$$$ lies left of $$$v$$$. Therefore $$$n−1$$$ must be on the left, and by Observation 1 it must be $$$smn_v$$$. If $$$smn_v \gt v$$$, similarly $$$n−1$$$ must be on the right, hence it must be $$$smx_v$$$.

Case B: children exist on both sides ($$$smn_v \lt v \lt smx_v$$$)

Observation 3: In the case B ($$$smn_v \lt v \lt smx_v$$$), among these two extreme children, one must have at least one parent edge crosses $$$v$$$, and the other one mustn't.

Proof: One child $$$q_x=n-1$$$ mustn't have a parent edge that crosses the index $$$v$$$ ($$$q_v=n$$$) due to the observation 2. For the other child node $$$q_y$$$, when $$$q_x=n-1$$$ is the root node, the parent node of $$$q_y$$$ must be $$$q_x$$$. They are on both sides of index $$$v$$$ ($$$q_v=n$$$). Therefore, it has at least one parent edge that crosses the index $$$v$$$ ($$$q_v=n$$$).

Similarly, define $$$Fa_v={u\mid s[v][u]=1}$$$; Define $$$fmn_v = min_{u\in Fa_v}u$$$; Define $$$fmx_v = max_{u\in Fa_v}u$$$.

If $$$fmx_{smn_v} \lt v$$$, then $$$smn_v$$$ doesn't have a parent edge that crosses $$$v$$$, then $$$q_{smn_v} = n - 1$$$. And vice versa.

The time complexity is $$$O(n^2)$$$. The bottleneck is preprocessing the input data.

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


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> fa_mx(n + 1), fa_mn(n + 1, n);
        vector<int> son_mx(n + 1), son_mn(n + 1, n);
        vector<vector<int>> fa(n + 1), son(n + 1);
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            s = ' ' + s;
            for (int j = 1; j <= n; j++) {
                if (i == j or s[j] == '0') continue;
                int u = j, v = i;
                fa_mx[v] = max(fa_mx[v], u);
                fa_mn[v] = min(fa_mn[v], u);
                son_mx[u] = max(son_mx[u], v);
                son_mn[u] = min(son_mn[u], v);
            }
        }
        vector<int> a(n + 1);
        for (int p = n, val = n; ; val--) {
            a[p] = val;
            if (val == 1) break;
            int mn = son_mn[p], mx = son_mx[p];
            if (mx < p) {
                p = mn;
            } else if (mn > p) {
                p = mx;
            } else {
                int mx1 = fa_mx[mn];
                if (mx1 <= p) {
                    p = mn;
                } else {
                    int mn2 = fa_mn[mx];
                    assert(mn2 >= p);
                    p = mx;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " \n"[i == n];
        }
    }
}