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

void test_case() {
	int a, b, c, n; cin >> a >> b >> c >> n;
	c = min(c, n / 100); n -= c * 100;
	b = min(b, n / 10); n -= b * 10;
	a = min(a, n); n -= a;
	if (n == 0) cout << "YES\n";
	else cout << "NO\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

We only need to use $$$100$$$ coins as much as possible first, then $$$10$$$ coins as much as possible, and finally $$$1$$$ coins.

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif

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

#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif

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

    int T;  cin >> T;
    while(T--) {
        int n;  cin >> n;
        vector<int> a(n), b(n);

        long long ans = LLONG_MIN, sum = 0, sa = 0, sb = 0;
        for(auto &i: a)     cin >> i;
        for(auto &i: b)     cin >> i, sum += i;


        ans = 2 * a.back() - sum;
        for(int i = n - 1 ; i >= 0 ; i--) {
            sa += a[i], sb += b[i];
            ans = max(ans, min((sa - a.back()) - (sb - b[i]), sa - (sum - b.back())));
        }

        cout << ans << '\n';

    }

    return 0;
}

Consider enumerate $$$i_a$$$ from $$$1$$$ to $$$n$$$.

For a fixed $$$i_a$$$,Bob has only two possible optimal options:choose $$$i_b=1$$$ or $$$i_b=i_a+1$$$ (if $$$i_a \neq n$$$).So Bob chooses $$$min(a_{i_a}+...+a_n-(b_1+...+b_{n-1}),a_{i_a}+...+a_{n-1}-(b_{i_a+1}+...+b_n))$$$.

Note $$$score_i$$$ as the answer for fixed $$$i_a=i$$$,the final answer is $$$max(score_i)$$$.

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

#define int long long

void test_case() {
	int n; cin >> n;
	string s; cin >> s;
	int same = 1, cnt = 0;
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i - 1]) same = 0;
		same++;
		if (same >= 3) cnt += same - 2;
	}
	for (int i = 0; i < n; i += 2) s[i] = '1' + '0' - s[i];
	same = 1;
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i - 1]) same = 0;
		same++;
		cnt += (same - 1) / 2;
	}
	cout << cnt << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

The key observation is that super palindromes are strings of length $$$\geq 3$$$ with all numbers equal, or a string with alternating $$$0-1$$$ (and with odd length).

After that, we only need to enumerate $$$i$$$ from $$$1$$$ to $$$n$$$ and count super palindromes that end in index $$$i$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 2;

int p[MAXN];
bitset<MAXN> used;

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, sum = 1, k = 1;
        cin >> n;
        for (int i = 1;i <= n;i++) {
            used.reset(i);
            p[i] = 0;
        }
        while (sum <= n * (n + 1) / 4) {
            used.set(k);
            p[k] = k;
            k++;
            sum += k;
        }
        k--;
        ll r = n * (n + 1) / 4 - k * (k + 1) / 2, rmax = n;
        while (r) {
            p[k] = min(p[k] + r, rmax);
            used.set(p[k]);
            used.reset(k);
            r -= min(r, rmax - k);
            k--; rmax--;
        }
        int point_p = 1, point_q = 1;
        while (point_p <= n && point_q <= n) {
            while (p[point_p]) point_p++;
            while (used.test(point_q)) point_q++;
            p[point_p] = point_q;
            used.set(point_q);
        }
        for (int i = 1;i <= n;i++) cout << p[i] << ' ';
        cout << endl;
    }
}

Let $$$p$$$ be the lexicographically smallest balanced permutation of length $$$n$$$ and $$$x$$$ be the integer such that $$$1 \leq x < n$$$ and $$$p_1+p_2+⋯+p_x=p_{x+1}+p_{x+2}+⋯+p_n$$$. Let's take a look to the lexicographically smallest (not necessary balanced) permutation of length $$$n$$$, which is $$${1,2,\dots,n}$$$.

Let $$$m$$$ be the largest value such that:

Notice that since $$$m$$$ is as large as possible, $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$. Which means, $$$x < m+1$$$ for any balanced permutation of length $$$n$$$ (since no matter how you rearrange the permutation, $$$p_1+p_2+⋯+p_{m+1} \geq 1+2+\dots+m+(m+1)$$$). It is also worth noting that $$$m < n$$$. This will be useful later.

Since $$$p$$$ is the lexicographically smallest balanced permutation of length $$$n$$$, we want to greedily shove as much small numbers as possible to the prefix of $$$p$$$, then sort the prefix from smallest to largest, thus making $$$x$$$ be as large as possible. Notice that since $$$x < m+1$$$, it is possible that $$$x = m$$$ in the optimal solution and we can prove that it actually is.

Assume $$$p = {1,2,\dots,n}$$$ (in other words, $$$p_i = i$$$ for all $$$1 \leq i \leq n$$$). Focus on the $$$m$$$ first numbers in the permutation. Let $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$ (which means $$$r \geq 0$$$). Since:

$$$r < m+1$$$ which means $$$r \leq m$$$. This means that in order to make sure $$$p_1 + p_2 + \dots + p_m = p_{m+1} + p_{m+2} + \dots + p_n$$$, we can just add $$$1$$$ to all $$$p_j$$$ where $$$m - r + 1 \leq j \leq m$$$ and $$$p_1,p_2,\dots,p_m$$$ will still be a possible prefix of the permutation, since $$$p_m \leq n$$$ and $$$p_1 < p_2 < \dots < p_m$$$ will still be satisfied after the changes (because $$$m < n$$$ and $$$p_1 < p_2 < \dots < p_{m-r} < p_{m-r+1} < \dots < p_m$$$ before the changes). Now that we know $$$x = m$$$, how can we make $$$p$$$ as small lexicographically as possible?

Let's focus on the first $$$m$$$ numbers inside $$$p$$$. Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. We will modify this later. Now, we need to add the value $$$r$$$ to the first $$$m$$$ numbers by spreading the addition. However, to make sure $$$p$$$ is as small as possible, we have to greedily add some value to some last numbers inside $$${p_1,p_2,\dots,p_m}$$$ such that the added value is $$$r$$$ and $$${p_1,p_2,\dots,p_m}$$$ is lexicographically smallest. In other words, we can do this procedure to construct the first $$$m$$$ numbers inside the permutation:

• Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$.
• Let $$$j = m$$$. While $$$r > 0$$$, add $$$\min(r,k-j)$$$ to $$$p_j$$$, decrease $$$r$$$ by $$$\min(r,k-j)$$$, and decrease $$$j$$$ by $$$1$$$ where $$$k$$$ is the maximum integer such that $$$k \leq n$$$ and $$$k$$$ currently does not appear inside $$${p_1,p_2,\dots,p_m}$$$.

For the last $$$n-m$$$ numbers, notice that we can just fill these with all the numbers that are not used in the first $$$m$$$ numbers, since the sum of the numbers will automatically be equal to $$$p_1+p_2+\dots+p_m = \frac{1+2+\dots+n}{2}$$$. Do note that to make sure $$$p$$$ is as small as possible, $$$p_{m+1} < p_{m+2} < \dots < p_n$$$ need to be satisfied.

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

Turns out that there is an unexpected DFS solution to this problem that some of the participants has used, although I don't really know how the sol works :].

Bonus question: Can you guess which $$$n$$$ values results in no possible balanced permutation?

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

#define int long long
#define INF (int)(1e16)

#define N 510000
#define K 51

int a[N], cnt[N], pref[N], dp[K][N], n, k;

void calc(int i, int l, int r, int vl, int vr) {
	if (r < l) return;
	int mid = (l + r) / 2;
	int v, mn = INF;
	for (int j = vr; j >= vl; j--) {
		int sum = pref[mid] - pref[j - 1];
		int need = cnt[mid] - cnt[j - 1];
		if (i % 2 == 0) {
			need = (j + j + need - 1) * need / 2;
			sum = sum - need;
		} else {
			need = (mid + mid - need + 1) * need / 2;
			sum = need - sum;
		}
		if (dp[i - 1][j - 1] + sum < mn) {
			mn = dp[i - 1][j - 1] + sum;
			v = j;
		}
	}
	dp[i][mid] = mn;
	calc(i, l, mid - 1, vl, v);
	calc(i, mid + 1, r, v, vr);
}

void test_case() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 2; i <= n; i++)
		a[i] ^= a[i - 1];
	for (int i = 1; i <= n; i++)
		cnt[i] = cnt[i - 1] + a[i], pref[i] = pref[i - 1] + i * a[i];
	for (int i = 1; i < n; i++)
		dp[0][i] = INF;
	dp[0][0] = 0;
	int ans = INF;
	for (int i = 1; i <= k; i++) {
		calc(i, 1, n - 1, 1, n - 1);
		if (i + (a[n] ^ (i & 1)) <= k)
			ans = min(ans, dp[i][n - 1]);
	}
	cout << ans << '\n';
}

int32_t main() {
	int t; cin >> t;
	while (t--) test_case();
}

Considering the prefix xor array of $$$a$$$, we found that the original operation was equivalent to swapping $$$prexor_ {i-1}, prexor_ {i} (1<i<n) $$$.

In fact,it is a variation of this.

Afterwards, the constraint of 'at most 2' is equivalent to having at most one continuous $$$1... 1$$$in $$$prexor$$$.

Because $$$prexor_n$$$ cannot be changed,if $$$prexor_n=1$$$, we merge all $$$1$$$ into one suffix. Otherwise, we will merge all $$$1$$$s into the vicinity of the middle $$$1$$$.

Read the solution for the Easy Version first.

In this version,we need to divide all $$$1$$$ s into up to $$$\lfloor \frac{k}{2} \rfloor$$$ groups and merge the $$$1$$$ s of each group in the optimal way.

Note $$$pos$$$ as positions of all $$$1$$$s,we can calculate the cost of merging $$$pos_l,...,pos_r$$$ in $$$O(1)$$$.Note it as $$$cost(l,r)$$$.

Now,we have a slmple $$$DP$$$:$$$dp_{i,j}=min_{0 \leq t <i}(dp_{t,j-1}+cost(t+1,i))$$$.It's $$$O(n^2k)$$$.How to optimize it?

We notice $$$cost(l+1,r+1)+cost(l,r) \leq cost(l+1,r)+cost(l,r+1)$$$ holds here.Due to the quadrilateral inequality, decision monotonicity holds. We can optimize it to $$$O(nk log n)$$$ using classic techniques (decision stack or divide and conquer).

The code above divides every group into the left and right parts to make calculations easier.

To learn the classic techniques:

CF 868 F

CF 321 E

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define MOD (int)(1e9+7)
 
#define N 110000ll
#define K 20ll
#define B 850000006ll
 
struct segtree {
	vector<int> sum, lk, lb;
	segtree() {}
	segtree(int n) {
		sum = vector<int>(4 * n + 1, 0);
		lk = vector<int>(4 * n + 1, 1);
		lb = vector<int>(4 * n + 1, 0);
	}
	void push(int v, int l, int r) {
		if (lk[v] == 1 && lb[v] == 0) return;
		sum[v] = (lk[v] * sum[v] % MOD + (r - l + 1) * lb[v] % MOD) % MOD;
		if (l != r) {
			lk[v * 2 + 0] = lk[v] * lk[v * 2 + 0] % MOD;
			lb[v * 2 + 0] = (lk[v] * lb[v * 2 + 0] % MOD + lb[v]) % MOD;
			lk[v * 2 + 1] = lk[v] * lk[v * 2 + 1] % MOD;
			lb[v * 2 + 1] = (lk[v] * lb[v * 2 + 1] % MOD + lb[v]) % MOD;
		}
		lk[v] = 1, lb[v] = 0;
	}
	void upd(int v, int l, int r, int k, int x) {
		push(v, l, r);
		if (k < l || r < k) return;
		if (l == r) {
			sum[v] = x;
			return;
		}
		int mid = (l + r) / 2;
		upd(v * 2 + 0, l, mid, k, x);
		upd(v * 2 + 1, mid + 1, r, k, x);
		sum[v] = (sum[v * 2 + 0] + sum[v * 2 + 1]) % MOD;
	}
	void apply(int v, int l, int r, int ql, int qr, int k, int b) {
		push(v, l, r);
		if (qr < l || r < ql) return;
		if (ql <= l && r <= qr) {
			lk[v] = k;
			lb[v] = b;
			push(v, l, r);
			return;
		}
		int mid = (l + r) / 2;
		apply(v * 2 + 0, l, mid, ql, qr, k, b);
		apply(v * 2 + 1, mid + 1, r, ql, qr, k, b);
		sum[v] = (sum[v * 2 + 0] + sum[v * 2 + 1]) % MOD;
	}
	int get(int v, int l, int r, int ql, int qr) {
		push(v, l, r);
		if (qr < l || r < ql) return 0;
		if (ql <= l && r <= qr) return sum[v];
		int mid = (l + r) / 2;
		return (get(v * 2 + 0, l, mid, ql, qr) +
				get(v * 2 + 1, mid + 1, r, ql, qr)) % MOD;
	}
};
 
int a[N];
segtree p[K], pp;
 
int inv(int x) {
	return x == 1 ? 1 : MOD - MOD / x * inv(MOD % x) % MOD;
}
 
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 0; i < K; i++)
		p[i] = segtree(n);
	pp = segtree(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = 0; j < K; j++)
			if (a[i] & (1 << j)) p[j].upd(1, 0, n - 1, i, 1);
	}
	int pk = (1 - 2 * B % MOD + MOD) % MOD, pb = B;
	int ppk = pk * pk % MOD, ppb = (B - B * B % MOD + MOD) % MOD;
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int i, x; cin >> i >> x; i--;
			for (int j = 0; j < K; j++)
				p[j].upd(1, 0, n - 1, i, (x >> j) & 1);
			pp.upd(1, 0, n - 1, i, 0);
		} else if (t == 2) {
			int l, r; cin >> l >> r; l--; r--;
			for (int j = 0; j < K; j++)
				p[j].apply(1, 0, n - 1, l, r, pk, pb);
			pp.apply(1, 0, n - 1, l, r, ppk, ppb);
		} else if (t == 3) {
			int l, r; cin >> l >> r; l--; r--;
			if (l == r) {cout << 0 << '\n'; continue;}
			int ev = 0;
			int sumpp = pp.get(1, 0, n - 1, l, r);
			for (int j = 0; j < K; j++) {
				int sump = p[j].get(1, 0, n - 1, l, r);
				int cur = (sump * (r - l + 1 - sump + MOD) % MOD - sumpp + MOD) % MOD;
				(ev += cur * (1 << j) % MOD) %= MOD;
			}
			(ev *= inv(r - l + 1) * inv(r - l) % MOD * 2 % MOD) %= MOD;
			cout << ev << '\n';
		}
	}
}

Firstly, because of linearity of expectation, we can calculate answer for each bit independently.

Formula for expected value on segment for one bit is $$$\frac{\sum_{l\leq i\neq j\leq r} p_i(1-p_j)}{(r - l + 1) \cdot (r - l) / 2}$$$, where $$$p_i$$$ is probability of $$$a_i$$$ being set to $$$1$$$.

To calculate this, we just need to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ Let $$$po_i$$$ be $$$p_i$$$ before second operation and $$$b$$$ probability of bit changing ($$$\frac{1}{20}$$$).

Now to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ we just need to apply linear function on segment, we can do it using segment tree. This is already fast enough for C++20 compiler. We can notice that $$$p_i(1-p_i)$$$ is same for all bits, so we can maintain only one segtree for it. With this optimization solution passes using other compilers.

The final complexity is $$$\mathcal{O}(n \log n \log A)$$$

$$$1 \le x < y \le 1000,3 \le n \le 1000$$$

DIV2A

One of the easiest.It contains the simplest 'reverse thinking'.

$$$0 \le x < 2^{30},3 \le n \le 10^5$$$

DIV2D

Contains a general idea for solving bit operation problems:consider bit by bit.

A little patience in observation is also needed.

Both of the above problems use the same model, which may be able to create more interesting problems.

$$$1 \le n \le 10^5$$$

DIV2B

Problems of snake paths on a grid is generally not easy to solve, so I chose to reduce the constraint and set the problem on a $$$2 \cdot n$$$ grid(and it works). I guess it helps beginners familiarize themselves with mex.

In addition,I think we can find more cool problems in $$$2 \cdot n$$$ grid like this one.

$$$2 \le x\le 10^9$$$

DIV2C

In the initial version, $$$x \leq 10^{18}$$$.

After discussion,we have decided to set $$$x \leq 10^9 $$$ to "mislead" people into decomposing $$$x$$$.

The interesting point is,loose constraints actually make the problem more difficult.For example,if I set $$$x \leq 10^{18}$$$ and the number of operations $$$\leq 64$$$,you will soon think of binary stuff.

Afterwards, we really discovered a solution based on factorization, which is also very beautiful!

$$$2 \le n\le 10^{18}$$$

DIV2B

A purely observational problem. I guess some people would like this kind of IQ test style problem.

I believe that some MO and IQ problems can be adapted into CP problems.

$$$1 \le n\le 10^5$$$

DIV2D-E (Codechef Rating 2961)

Including an experience (not accurate) that "most interaction problems involve binary search".

You still need some optimization, otherwise you won't be able to complete the task in $$$40$$$ operations.

$$$1 \le n\le 3000,0 \leq a_i <2^{30}$$$

DIV2D-E (Codechef Rating 3086)

The most interesting point is that when you modify a certain $$$a_x$$$, you can't even get immediate feedback from the judge(most of the time, the maximum value of the array does not change).

Consider bit by bit again :)

$$$1 \le n\le 10^5,1 \leq a_i <10^6$$$

DIV2D (Codechef Rating 2700)

I think it contains some general ideas. Considering the power of each prime factor, then you find $$$gcd(x_1,x_2,...)$$$ is to pick the maximum power of all numbers, and $$$lcm(x_1, x_2,...)$$$ is to pick the minimum power of all numbers.

• $$$1 \leq n,m \leq 3 \cdot 10^5$$$
• $$$1 \leq l \leq r \leq n$$$
• $$$-10^6 \leq k,b,x_i,y_i \leq 10^6$$$

DIV2E (Codechef Rating 3150)

If you are practicing segment trees, I strongly recommend this problem :)

An interesting thing is used here: if you write an equal difference sequence on the coordinate axis, then these points are collinear.

$$$1 \le n\le 4 \cdot 10^5,1 \leq a_i,x_i,k \leq 10^9$$$

DIV2E

This seems like a number theory problem, but it use string algorithms?

There are many educational points.This includes abstracting problems into the simplest mathematical models,techniques for transforming equations, and the use of some classic algorithms.

$$$1 \le n,k\le 10^9$$$

DIV2B-C

One way to create a problem is to start with an interesting definition(in this problem,it is $$$con(x,y)$$$).

No advanced algorithms, only testing your casework.

$$$2 \le n,k\le 10^5$$$

DIV2C

It's a variation of a classic problem.

an easier variation

an harder variation

$$$3 \le n \le m\le 10^6$$$

DIV2D

As we all know,the sum of the two sides of a triangle is greater than the third side.You need to similarly convert condition $$$3$$$.

It contains a general idea:if $$$P$$$ is hard to count,then think about count $$$ALL- \overline P$$$.

$$$C_i^j+C_{i−1}^j+...+C_j^j=C_{i+1}^{j+1}$$$

$$$2 \le n \le 2 \cdot 10^5$$$

DIV2D-E(Codechef Rating 3037)

Finding $$$a$$$ based on given $$$p$$$ is a classic problem(monotonic stack).

Here 'reverse thinking' is used, and fortunately, this problem has become more interesting :)

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

map<int, int> mp;

void test_case() {
	mp.clear();
	int n; cin >> n;
	int cnt1 = 0;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		mp[x]++;
		if (mp[x] == 1) cnt1++;
		if (mp[x] == 2) cnt1--;
	}
	if (cnt1 > 0) cout << "YES\n";
	else cout << "NO\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

If there is a unique number in a, output YES. Otherwise, output NO.

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

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

    int tests;
    cin >> tests;
    
    while (tests--) {
        int64_t n, k;
        cin >> n >> k;
        if (k < 2 * n) {
            cout << (n - k % n) * (n - k % n) << '\n';
        } else if (n == 1 || k % 2 == 0 || k - 2 * (n - 1) != 3) {
            cout << 0 << '\n';
        } else {
            cout << 2 - (n == 2) << '\n';
        }
    }
}

If $$$k \leq 2n$$$,the optimal solution is to form array $$$a$$$ with $$$1$$$ and $$$2$$$. The answer is $$$c_1^ 2$$$.Any other construction will result in a num of $$$1$$$ greater than $$$c_1$$$, obviously not the optimal one.

For $$$k>2n+1$$$,the answer is always $$$0$$$.If $$$k$$$ is even,we can easily form array $$$a$$$ with $$$n$$$ even numbers.If $$$k$$$ is odd,we can set $$$a_1=5$$$ and form $$$a_2,...,a_n$$$ with $$$n-1$$$ even numbers.

For $$$k=2n+1$$$,if $$$n=2$$$,$$$a=[2,3]$$$ is optimal and the answer is $$$1$$$.Otherwise($$$n>2$$$),$$$a=[1,4,2,...,2]$$$ is optimal and the answer is $$$2$$$.

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

#define N 210000

string s;

void test_case() {
	int n; cin >> n >> s;
	sort(begin(s), end(s));
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += s[i] - 'a';
	if (sum % 2 != 0) {cout << -1 << '\n'; return;}
	int ans = n * 100;
	if (s[n - 1] - 'a' <= sum - s[n - 1] + 'a')
		ans = sum;
	for (int i = 0; i < n; i++) {
		int sumcur = sum - s[i] + 'a';
		int valcur = s[i] - 'a' + 26;
		int num = (max(0, valcur - sumcur) + 25) / 26;
		if (num > i) continue;
		ans = min(ans, sum + 26 + num * 26);
	}
	if (ans == n * 100) {cout << -1 << '\n'; return;}
	cout << ans / 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

For $$$n=2$$$,if $$$s_1 \neq s_2$$$ ,output $$$-1$$$.Otherwise,output $$$s_1-'a'$$$.

For $$$n>2$$$,let's consider a classic problem:for a given array $$$a$$$,you can make $$$a_i--,a_j--$$$,determine if you can make all numbers to $$$0$$$.

Let's go back to this problem.Let's see string $$$s$$$ as the array $$$a$$$ above.Note $$$opr_i$$$ as the number of times we operate on $$$s_i$$$.We can get $$$opr_i=(a_i-'a')+26k_i$$$ since we want all $$$a_i='a'$$$.Now our task is minimize $$$\Sigma k_i$$$.

First check if the original array satisfies $$$2max(a_i) \leq \Sigma a_i$$$.If not,then greedily increase the minimum value by $$$26$$$.It can be proven that we can get $$$2max(a_i) \leq \Sigma a_i$$$ after adding the array at most two times .

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=4010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int n,q;
int a[N*N];
int S[N][N];

int main()
{	
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n*n;i++) 
	{
		scanf("%d",&a[i]);
		S[i%(2*n)][(i+2*n)/(2*n)]=S[i%(2*n)][(i+2*n)/(2*n)-1]+a[i];
	}
	for(int i=1;i<=q;i++)
	{
		int t,x,p1,p2,ans=0;
		scanf("%d%d",&t,&x);
		p1=t-x+1;p2=t-2*n+x;
		if(p1>0) ans+=S[p1%(2*n)][(p1+2*n)/(2*n)];
		if(p2>0) ans+=S[p2%(2*n)][(p2+2*n)/(2*n)];
		printf("%d\n",ans);
	}
	
	return 0;
}

The key to solving the problem lies in observing:If we group all elements in $$$a$$$ according to the index mod $$$2n$$$, then at all times, the elements of the same group will always be in the same column.

We divide the elements in $$$a$$$ into $$$2n$$$ groups and build prefix sum arrays for each group. For each query, we calculate which two groups pass through this column, and then calculate the answer with the two prefix sum arrays.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  sum;
int p[N],pos[N],sig[N],BIT[N];

void add(int p,int v)
{
	for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=v;
}

int getsum(int p)
{
	int s=0;
	for(int i=p;i;i-=(i&-i)) s+=BIT[i];
	return s;
}

struct nod
{
	int l,r,sum,tag;
	nod *lc,*rc;
};

struct Segtree
{
	nod *root;
	
	Segtree()
	{
		build(&root,1,n);
	}
	
	void newnod(nod **p,int L,int R)
	{
		*p=new nod;
		(*p)->l=L;(*p)->r=R;(*p)->sum=1;(*p)->tag=0;
	}
	
	void build(nod **p,int L,int R)
	{
		newnod(p,L,R);
		if(L==R) return ;
		int M=(L+R)>>1;
		build(&(*p)->lc,L,M);
		build(&(*p)->rc,M+1,R);
		(*p)->sum=(*p)->lc->sum+(*p)->rc->sum;
	}
	
	void pushdown(nod *p)
	{
		if(p->tag) p->sum*=-1;
		if(p->l!=p->r)
		{
			p->lc->tag^=p->tag;
			p->rc->tag^=p->tag;
		}
		p->tag=0;
	}
	
	void flip(int L,int R)
	{
		_flip(root,L,R);
	}
	
	void _flip(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R)
		{
			p->tag^=1;
			return ;
		}
		int M=(p->l+p->r)>>1;
		if(R<=M)     _flip(p->lc,L,R);
		else if(L>M) _flip(p->rc,L,R);
		else         _flip(p->lc,L,M),_flip(p->rc,M+1,R);
		pushdown(p->lc);pushdown(p->rc);
		p->sum=p->lc->sum+p->rc->sum;
	}
	
	int getsum(int L,int R)
	{
		return _getsum(root,L,R);
	}
	
	int _getsum(nod *p,int L,int R)
	{
		pushdown(p);
		if(p->l==L&&p->r==R) return p->sum;
		int M=(p->l+p->r)>>1;
		if(R<=M)     return _getsum(p->lc,L,R);
		else if(L>M) return _getsum(p->rc,L,R);
		else         return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
	}
};

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]),pos[p[i]]=i;
    	Segtree TR;
    	sum=0;
    	for(int i=1;i<=n;i++) BIT[i]=0;
    	for(int i=1;i<=n;i++)
    	{
	    	sig[i]=(getsum(p[i])&1)?-1:1;
	    	add(p[i],1);
	    }
    	for(int i=1;i<=n;i++)
		{
			sum+=((pos[i]&1)?1:-1)*(ll)(pos[i]-1)*i;
	    	sum+=(ll)(sig[pos[i]]*TR.getsum(pos[i],pos[i])*TR.getsum(pos[i],n))*i;
	    	TR.flip(pos[i],n);
	    }
	    printf("%I64d\n",sum);
	}
	
	return 0;
}

Consider calculating the contribution of each element separately.

For an element,we can observe that only elements with values less than it and indexes greater than it increase its index by $$$1$$$.

We represent these 'influence' as a sequence $$$s$$$ containing only $$$1$$$ and $$$-1$$$.At the beginning,$$$s_i=1$$$ for all $$$1\leq i \leq n$$$.We calculate the contribution of each element in ascending order of values.

Assuming we have already calculated the contribution of $$$x$$$,then we do filp $$$s_{pos_x},...,s_n$$$ (flip denotes making $$$1$$$ to $$$-1$$$ and make $$$-1$$$ to $$$1$$$) and calculate the contribution of $$$x+1$$$ using updated $$$s$$$.

#include <bits/stdc++.h>
// v.erase( unique(all(v)) , v.end() )    ----->   removes duplicates and resizes the vector as so
using namespace std;
#define IO_file freopen("output.txt","w",stdout), freopen("input.txt","r",stdin);
#define ll long long
#define lld long double
const lld pi = 3.14159265358979323846;
#define pb push_back
#define pf push_front
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
constexpr int mod = (int)(1e9 + 7);
#define log(x) (31^__builtin_clz(x)) // Easily calculate log2 on GNU G++ compilers
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}

struct AhoCorasick {
  //The trie
  struct tr_node {
    int adj[26];
    int link;
    int parent;
    int term;
    
    tr_node() {
      link = 0;
      parent = -1;
      term = 0;
      memset(adj, -1, sizeof(adj));
    }
  
  };
  
  vector<tr_node> tr;
  int tick = 0;//--> tick is the number of nodes in the trie
  
  AhoCorasick() {
    init();
  }
  
  void init() {
    tr.clear();
    tr.push_back(tr_node());
    tick = 0;
    tr[0].link = -1;
  }
  
  void insert(const string &s) {
    int p = 0;
    for(int i=0;i<s.size();i++){
      if(tr[p].adj[s[i]-'a'] == -1){
        tr.push_back(tr_node());
        tr[p].adj[s[i]-'a'] = (++tick);
      }
      p = tr[p].adj[s[i]-'a'];
    }
    tr[p].term++;
  }
  
  //build the suffix links and transitions for each node 
  //in Amortized O(sizeof the strings inserted in the trie + No.nodes*sizeofAlphabet).	
  //this implementation has less memory usage, so you choose which to run.
  //you can add an additional array "adj" to build a tree over the suffix links.
  vector<int> character;
  
  //we build the suffix links only and we calculate transitions on the run
  int trans(int p, int c) {
    //p is the node, c is the character
    while(p != -1 && tr[p].adj[c] == -1) p = tr[p].link;
    if(p == -1) return 0;//we return the root
    return tr[p].adj[c];
  }
  
  void build() {
    character.resize(tick+5); 
    queue<int> q; q.push(0);
    character[0] = -1;
    while(!q.empty()){
      int p = q.front(); q.pop();
      if(p){
        if(tr[tr[p].parent].link != -1){
          tr[p].link = trans(tr[tr[p].parent].link, character[p]);
        }
        if(tr[p].link != -1){
          tr[p].term += tr[tr[p].link].term;
        }
      }
      for(int i = 0 ; i < 26 ; i++){
        if(tr[p].adj[i] != -1){
          tr[tr[p].adj[i]].parent = p;
          character[tr[p].adj[i]] = i;
          q.push(tr[p].adj[i]);
          continue;
        }
      }
    }
  }
  
}Aho[20];
 
vector<string> info[20];
 
void add(const string &s) {
  for(int i = 0 ; i < 20 ; i++){
    if(info[i].size() == 0){
      for(int j = 0 ; j < i ; j++){
        for(string x : info[j]){
          info[i].pb(x);
        }
        vector<string> v;
        info[j].swap(v);
        Aho[j].init();
      }
      info[i].pb(s);
      for(string x : info[i]){
        Aho[i].insert(x);
      }
      Aho[i].build();
      break;
    }
  }
}
 
ll query(const string &s) {
  ll cnt = 0;
  for(int i = 0 ; i < 20 ; i++){
    if(info[i].empty()) continue;
    int p = 0;
    for(int j = 0 ; j < s.size() ; j++){
      p = Aho[i].trans(p, s[j] - 'a');
      cnt += Aho[i].tr[p].term;
    }
  }
  return cnt;
}

const int N = 2e5 + 7;
const int M = 4e5 + 7;

int n, par[M], fake_node;
vector<int> adj[M];
string str[N];
string qry_str[N];

void init() {
  for(int i = 0 ; i <= 2 * n ; i++){
    par[i] = i;
  }
  fake_node = n;
}

int find(int x) {
  if(x == par[x]) return x;
  return par[x] = find(par[x]);
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return;
  fake_node++;
  par[x] = fake_node;
  par[y] = fake_node;
  adj[fake_node].pb(x);
  adj[fake_node].pb(y);
}

int in[M], out[M], tick, node_at[M];

void dfs(int node) {
  in[node] = ++tick;
  node_at[tick] = node;
  for(int u : adj[node]){
    dfs(u);
  }
  out[node] = tick;
}

vector<pair<int, bool > > queries2[M]; // the query indx, 0 pos | 1 neg

int main()
{ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n;
init();
for(int i = 1 ; i <= n ; i++){
  cin>>str[i];
}
int q; cin>>q;
vector<pair<int, int> > queries; // the node, the query indx
vector<int> quests;
for(int i = 0 ; i < q ; i++){
  int t; cin>>t;
  if(t == 1){
    int a, b; cin>>a>>b;
    merge(a, b);
    continue;
  }
  int v; cin>>v;
  cin>>qry_str[i];
  v = find(v);
  queries.pb({v, i});
  quests.pb(i);
}
for(int i = 1 ; i < n ; i++){
  merge(i, i + 1);
}
int root = find(1);
dfs(root);
for(pair<int, int> X : queries){
  int v = X.first; int indx = X.second;
  queries2[out[v]].pb({indx, 0});
  if(v != root){
    queries2[in[v] - 1].pb({indx, 1});
  }
}
ll ans[q] = {};
for(int i = 1 ; i <= tick ; i++){
  int u = node_at[i];
  if(u <= n){
    add(str[u]);
  }
  for(pair<int, int> X : queries2[i]){
    int indx = X.first;
    bool o = X.second;
    if(o){
      ans[indx] -= query(qry_str[indx]);
    }
    else {
      ans[indx] += query(qry_str[indx]);
    }
  }
}
for(int i = 0 ; i < quests.size() ; i++){
  cout<<ans[quests[i]]<<'\n';
}



    return 0;
}

We will answer the queries offline.

We will use DSU to process queries of the first type.

For each query of the first type, we will create a new node $$$H$$$ and connect both $$$u$$$ and $$$v$$$ to it.

For each query of the second type, we will add the query to the query-list of the root of the component $$$u$$$ is in.

Now we merge all the components together and we notice that now we have a tree and each query of the second type turns out to be a subtree query in our tree.

We run euler tour on the tree and now each subtree query is a range query in the euler tour array, for example it's a query on $$$[L, R]$$$, the answer to it is the answer on $$$[1, R]$$$ minus the answer on $$$[1, L - 1]$$$.

to answer these prefix queries we will use dynamic Aho-Corasick to add the strings and answer the queries.

The amortized time complexity of this solution is $$$O(N * log(N) * AlphabetSize)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++) printf("%d%c",a[i]*(i&1?1:-1),i==n?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

We just sort the array and set $$$a_i:=-a_i$$$ for all even $$$i$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                string s;
                int k;
                cin >> s >> k;

                int n = (int)s.length();
                int mn = n - k;
                for (int i = n - k - 1; i >= 0; i--) {
                        if (s[i] > s[i + k]) {
                                mn = i;
                        }       
                }

                string ans = s.substr(0, mn) + s.substr(mn + k);

                cout << ans << '\n';
        }
        
        return 0;
}

We will solve this problem by using the sliding window trick. Let's assume $$$s_{i,j}$$$ as the substring inside $$$s$$$ from the $$$i$$$-th character to the $$$j$$$-th character from the left of the string $$$s$$$. First, create a window from the segment $$$[1,k]$$$ denoting the deletion window, which means $$$x=s_{k+1,|s|}$$$ for now. Now, we will slide this window by one index to the right each time and check if the new string formed by concatenating characters not covered by the window after sliding is weaker than current weakest string before sliding.

Notice that when we slide the window from the segment $$$[i,i+k-1]$$$ to $$$[i+1,i+k]$$$, the only difference between the resulting string from both deletion window result is the $$$i$$$-th character. Or more specifically, we override the $$$i$$$-th character in the result from $$$s_{i+k,i+k}$$$ to $$$s_{i,i}$$$. Furthermore, if $$$s_{i+k,i+k}$$$ is lexicographically smaller (or weaker) than $$$s_{i,i}$$$, that means the resulting string from all the deletion window placement after sliding it to the right from the segment $$$[i,i+k-1]$$$ will never be weaker than when the window is at the segment $$$[i,i+k-1]$$$, which means it is enough to keep sliding the deletion window to the right up until the point where $$$s_{i+k,i+k} < s_{i,i}$$$. Then, delete the segment $$$[i,i+k-1]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,k,ans;
int  p[N],d[N],pre[N];
int  dp[N][2];

int main()
{
	//freopen("test.in","r",stdin);
	
	T=1;
	//scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    	ans=0;
    	pre[0]=k; 
	    for(int i=1;i<=n;i++)
	    {
    		if((d[i]&&pre[i-1]>=1900)||((!d[i])&&pre[i-1]<=2100)) pre[i]=(p[i]-pre[i-1])/4+pre[i-1];
			else pre[i]=pre[i-1];
    	}
    	ans=max(pre[n-1],pre[n]);
    	for(int i=0;i<=4000;i++) dp[i][(n+1)&1]=i;
    	for(int i=n;i>=2;i--)
    	{
			for(int j=0;j<=4000;j++) 
			{
				if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[j][i&1]=dp[(p[i]-j)/4+j][(i+1)&1];
				else dp[j][i&1]=dp[j][(i+1)&1];
			}
			ans=max(ans,dp[pre[i-2]][i&1]);
	    }
    	/*for(int i=0;i<=4000;i++) dp[n+1][i]=i;
    	for(int i=n;i;i--)
    	{
	    	for(int j=0;j<=4000;j++)
	    	{
	    		if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[i][j]=dp[i+1][(p[i]-j)/4+j];
	    		else dp[i][j]=dp[i+1][j];
	    	}
	    }
	    ans=dp[1][k];kk=k;
	    for(int i=1;i<=n;i++)
	    {
    		ans=max(ans,(int)dp[i+1][k]);
    		if((d[i]&&k>=1900)||((!d[i])&&k<=2100)) k=(p[i]-k)/4+k;
    	}*/
    	printf("%d\n",k-ans);
	}
	
	//fclose(stdin);
	return 0;
}

The key to solving the problem is to notice that $$$k$$$ is small ($$$k \leq 4000$$$).The intended solution is $$$O(nk)$$$.

We note $$$dp_{i,j}$$$ as the final rating when current score is $$$j$$$, participating in the $$$i, i+1,...,n_{th}$$$ contest.

We can enumerate the skipped contest and update the answer with the $$$dp$$$ array.

To avoid exceeding the memory limit, you need to use a scrolling array.

/**
 *  @the_hyp0cr1t3
 *  30.07.2023 20:42
**/
#include <bits/stdc++.h>

template <int P> struct modint {
    static int mod_;
    int v;

    constexpr modint() : v{} {}
    constexpr modint(long long u) {
        if (u < 0) u = u % get_mod() + get_mod();
        if (u >= get_mod()) u %= get_mod();
        v = u;
    }

    constexpr int val() const { return v; }
    constexpr static int get_mod() {
        if constexpr (P > 0)
            return P;
        else
            return mod_;
    }
    constexpr static void set_mod(int m) {
        mod_ = m;
    }
    explicit constexpr operator int() const { return v; }
    friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
        long long u; in >> u;
        m = modint(u);
        return in;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
        return os << m.v;
    }

    static int inv(int a, int m) {
        int g = m, x = 0, y = 1;
        while (a != 0) {
            int q = g / a;
            g %= a;
            std::swap(g, a);
            x -= q * y;
            std::swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    constexpr static unsigned fast_mod(uint64_t x, unsigned m = get_mod()) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif  // x must be less than 2^32 * m
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
        asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
        return rem;
    }

    constexpr modint inv() const { return modint(inv(v, get_mod())); }
    constexpr modint operator-() const { return modint(v ? get_mod() - v : 0); }
    constexpr modint& operator+=(const modint& o) {
        v += o.v;
        if (v >= get_mod()) v -= get_mod();
        return *this;
    }
    constexpr modint& operator-=(const modint& o) {
        v -= o.v;
        if (v < 0) v += get_mod();
        return *this;
    }
    constexpr modint& operator*=(const modint& o) {
        v = fast_mod(uint64_t(v) * o.v);
        return *this;
    }
    constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
    friend constexpr modint operator+(const modint& a, const modint& b) {
        modint res = a; res += b;
        return res;
    }
    friend constexpr modint operator-(const modint& a, const modint& b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator*(const modint& a, const modint& b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/(const modint& a, const modint& b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr bool operator==(const modint& a, const modint& b) {
        return a.val() == b.val();
    }
};

template <typename T>
constexpr T expo(T A, long long B) {
    T res{1};
    while (B) {
        if (B & 1) res *= A;
        B >>= 1;
        A *= A;
    }
    return res;
}

template <>
int modint<0>::mod_ = 1;

constexpr int mod = 1'000'000'007;
using Z = modint<mod>;
// using Z = double;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    std::cin >> tests;
    while (tests--) {
        int n;
        std::array<Z, 3> p;
        std::cin >> n;
        int pmx = -1;
        for (int k : {2, 1, 0}) {
            std::cin >> p[k];
            pmx = std::max(pmx, p[k].val());
            p[k] /= 100;
        }

        if (pmx == 100) {
            std::cout << (n == 1 ? 0 : -1) << '\n';
            continue;
        }

        --n;

        auto P = p;
        std::array<Z, 2> ans{};
        std::array<std::vector<std::array<Z, 2>>, 3> dp;
        for (int k : {0, 1, 2}) {
            dp[k].reserve(n + 1);
            dp[k].push_back({0, p[k]});
        }

        for (int i = 1; i <= n; i++) {
            ans = {};
            for (int k : {0, 1, 2}) {
                for (int j = 0; j < i; j++) {
                    Z mul = p[(k + 1) % 3] * (i + 1) / (i - j);
                    for (int t : {0, 1}) {
                        dp[k][j][t] *= mul;
                        ans[t] += dp[k][j][t];
                    }
                }
            }
            ans = {(1 + ans[0]) / ans[1], 1};
            for (int k : {0, 1, 2}) {
                P[k] *= p[k];
                dp[k].push_back({});
                for (int t : {0, 1})
                    dp[k][i][t] = ans[t] * P[k];
            }
        }

        std::cout << ans[0] << '\n';
    }

}

For convenience, let $$$A=\frac{a}{100}$$$, $$$B=\frac{b}{100}$$$, $$$C=\frac{c}{100}$$$.

First, let's deal with some corner cases. When $$$n=1$$$, the answer is $$$0$$$. When $$$[A=0] + [B=0] + [C=0] = 2$$$, the answer is $$$-1$$$, because no one can leave if only one move is possible. Make sure to deal with these two cases in this particular order, because the answer when $$$n=1$$$ and $$$[A=0] + [B=0] + [C=0] = 2$$$ are both satisfied is $$$0$$$.

Then, let's solve the problem with DP. Let $$$f_i$$$ be the expected number of rounds it takes to result in $$$1$$$ person, starting from $$$i$$$ people. In the base case, we have $$$f_1 = 0$$$. Then, the transition would be:

where $$$P(i, j)$$$ is the probability of transitioning from $$$i$$$ people to $$$j$$$ people in one round. Rearranging, that is,

$$$P(i, i)$$$ basically translates to the probability of having one type or three types of moves in the room in one round. Thus,

To calculate $$$P(i, j)$$$ where $$$i > j$$$, we can also count cases in which $$$j$$$ winning moves and $$$i - j$$$ losing moves are made. That is,

Then, our answer would just be $$$f_n$$$.

Overall, the complexity is $$$O(n^2\log n)$$$ if techniques like fast-power are used to calculate the powers and combination values. However, the constant can be very big. By precomputing these values, the complexity would be $$$O(n^2)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=63;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,k,ans;
int dif[N];
ll  f[LOGN][LOGN][2];
vector<int> v;

void init()
{
	f[0][0][0]=f[1][0][0]=f[1][0][1]=1;
	for(int i=2;i<LOGN;i++)
	{
	    for(int j=0;j<i;j++)
	    {
	        for(int k=0;k<=1;k++) 
	        {
				f[i][j][k]=f[i-1][j][k];
				if(j) f[i][j][k]+=f[i-1][j-1][k^1];
	        }
	    }
	}
		
}

void DP(int bt)
{
	if(bt<0) 
	{
		ans+=(dif[0]==k);
		return ;
	}
	if(v[bt])
	{
		if(bt==(int)v.size()-1) 
		{
			for(int i=bt;i;i--) ans+=f[i][k][1];
		}
		else 
		{
			int diff=dif[bt+1]+v[bt+1];
			if(k-diff>=0)   ans+=f[bt][k-diff][0];
			if(k-diff-1>=0) ans+=f[bt][k-diff-1][1];
		}
	}
	DP(bt-1);
}

int main()
{
	//freopen("test.in","r",stdin);
	
	init();
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%I64d%I64d",&n,&k);
    	v.clear();
    	while(n) v.push_back(n&1),n>>=1;
    	dif[(int)v.size()-1]=0;
    	for(int i=(int)v.size()-2;i>=0;i--) dif[i]=dif[i+1]+(v[i]^v[i+1]);
    	ans=0;
    	DP((int)v.size()-1);
		printf("%I64d\n",ans%1000000007); 
	}
	
	//fclose(stdin);
	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,tt,ans;
int t[N],s[N],dt[N],ds[N];
int dp[N][N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&tt);
    	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&t[i],&s[i],&dt[i],&ds[i]);
    	ans=0;
    	for(int i=1;i<=tt;i++)
    	{
    		vector<pair<int,int> > v;
	    	for(int j=1;j<=n;j++) 
			{
				if(i+dt[j]>tt) v.push_back(make_pair(s[j],j));
				else           v.push_back(make_pair(ds[j],j));
			}
			sort(v.begin(),v.end());
			for(int j=1;j<=n;j++)
				for(int k=0;k<=i;k++)
					dp[i][j]=-INF;
			dp[0][0]=0;
			for(int j=1;j<=n;j++)
			{
				int num=v[j-1].second;
				if(i-t[num]>=0) ans=max(ans,dp[j-1][i-t[num]]+s[num]-v[j-1].first);
				for(int k=0;k<=i;k++)
				{
					dp[j][k]=dp[j-1][k];
					if(k-t[num]>=0) dp[j][k]=max(dp[j][k],dp[j-1][k-t[num]]+s[num]);
				}
			}
	    }
    	printf("%d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Consider:for a fixed problem set you choose,which problem will the hacker hack?

For problem $$$i$$$,$$$f_i \leq T-Σt$$$,hack it will decrease you score by $$$p_i$$$.

However,for problem $$$i$$$,$$$f_i >T-Σt$$$,hack it will decrease you score by $$$a_i$$$,since you don't have enough time to fix the bug.

Note $$$decrease_i$$$ as the score that actually decreased for the i-th hacked problem.Hacker'll hack the problem with the max $$$decrease$$$ value.

We find $$$decrease$$$ is depend on the value of $$$Σt$$$.

Enumeration $$$Σt$$$ from $$$0$$$ to $$$T$$$,calculate the corresponding $$$decrease$$$,then do classic knapsack DP.It's $$$O(n^2T)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,k,ls,lt;
ll  ans;
int x[N],a[N],S[N],s[N],t[N],nxt[N];
vector<int> p;

//

void build_nxt(int s[],int l)
{
	for(int i=1;i<l;i++)
	{
		int j=i;
		while(s[nxt[j-1]]!=s[i]&&j!=0) j=nxt[j-1];
		nxt[i]=(s[i]==s[nxt[j-1]])?nxt[j-1]+1:0;
	}
	//for(int i=0;i<l;i++) printf("%d ",nxt[i]);
	//printf("\n");
}

void KMP(int s[],int t[],int ls,int lt,vector<int> &v)
{
	build_nxt(t,lt);
	int ps=0,pt=0;
	while(1)
	{
		if(pt>=lt) 
		{
			v.push_back(ps-lt);
			pt=nxt[pt-1];
		}
		if(ps==ls) break;
		while(s[ps]!=t[pt])
		{
			if(!pt) break;
			else pt=nxt[pt-1];
		}
		if(s[ps]==t[pt]) ps++,pt++;
		else ps++,pt=0;
	}
}

//

//

ll md(ll a,ll b)	//a mod b
{
	if(a>0) return a%b;
	return (-(-a)%b+b)%b;	
}
		
void exgcd(ll &x,ll &y,ll a,ll b){
    if(!b){
        x=1;y=0;
        return ;
    }
    exgcd(x,y,b,a%b);
    ll xx=x,yy=y;
    x=yy;y=xx-(a/b)*yy;
}

ll solve_equation(ll a,ll b,ll k)	//solve ax=b(mod k),x>=0 and x is minimal
{
	ll x,y,g;
	md(a,k);md(b,k);
	exgcd(x,y,a,k); 	//ax+ky=gcd(a,k)
	g=a*x+k*y;
	if(b%g) return -1;
	return md(x*(b/g),k/g);
}

int check()
{
	for(int i=1;i<=n;i++) if(x[i]%k) return 0;
	return 1;
}

//


int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++)  scanf("%d",&x[i]);
    	for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    	if(check())
		{
			printf("0\n");
			continue;
		} 
    	for(int i=1;i<=n;i++)  S[i]=(S[i-1]+a[i])%k;
 		ls=2*n-2;lt=n-1;
 		for(int i=1;i<n;i++)   s[i-1]=a[i+1]%k;
 		for(int i=n;i<2*n;i++) s[i-1]=a[i-n+1]%k;
 		for(int i=1;i<n;i++)   t[i-1]=md(a[i]+x[i]-x[i+1],k);
 		p.clear();
    	KMP(s,t,ls,lt,p);
    	ans=INF*INF;
    	for(int i=0;i<p.size();i++)
    	{
	    	ll y=x[1]+S[1+p[i]],sol=solve_equation(S[n],-y,k);
	    	if(sol==-1) continue;
	    	ans=min(ans,sol*n+p[i]+1);
	    }
	    if(ans==INF*INF) printf("-1\n");
	    else printf("%I64d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Let's say $$$t = nm+p (0 \leq p<n)$$$ and $$$S$$$ is sum of all $$$a_i$$$.

We get $$$x_i + a_i + ... + a_{i + p} = x_{i + 1} + a_{i + 1} + ... + a_{i + p + 1}=-Sm (mod k)$$$

Thus $$$x_i + a_i = x_{i + 1} + a_{i + p + 1} (mod k)$$$ for $$$1\leq i \leq n-1$$$.

So we need to find $$$a_i + x_i - x_{i + 1}$$$ shifted in $$$a$$$, this is KMP.

Assume we have known $$$p$$$.Note $$$v=x_i + a_i + ... + a_{i + p}$$$,we also need $$$v+Sm=0(mod k)$$$.Use exgcd to get $$$m$$$.

Complexity:$$$O(n log n)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> a(n);
                vector<int> b(n);

                for (int i = 0; i < n; i++) cin >> a[i];
                for (int i = 0; i < n; i++) cin >> b[i];

                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int x, int y) {
                        if (b[x] == b[y]) return a[x] > a[y];
                        return b[x] == 1;
                });

                int ans = a[0] * b[0];
                int suma = 0, sumb = 0;

                for (int i = 0; i < n; i++) {
                        suma += a[ord[i]];
                        sumb += b[ord[i]];

                        ans = max(ans, suma * sumb);
                        ans = max(ans, a[i] * b[i]);
                }

                cout << ans << '\n';
        }

        return 0;
}

Consider greedy algorithm.

When all $$$b_i(1 \leq i \leq n)=-1$$$,obviously,the answer is $$$-min(a_i)$$$.

Otherwise,we choose all tuples which's $$$b_i=1$$$ firstly.Then choose tuples in descending order of $$$a_i$$$ value which's $$$b_i=-1$$$.The answer is the maximum in this process.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> ca(2 * n);
                vector<int> cb(2 * n);

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        ca[x] += 1;
                }

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        cb[x] += 1;
                }

                bool ok = 1;

                for (int i = 0; i < 2 * n; i++) {
                        if (ca[i] + cb[i] > n) {
                                ok = 0;
                        }
                }

                cout << (ok ? "YES" : "NO") << '\n';
        }
        
        return 0;
}

Note $$$k$$$ is the number with the highest sum of occurrences in $$$s$$$ and $$$t$$$.The answer is "YES" iff $$$occurrences(k) \leq n$$$.

If $$$occurrences(k) > n$$$,it means the total of numbers that are not $$$k$$$ is less than $$$n$$$.Obviously the answer is "NO".

Otherwise,we can use Mathematical induction to prove that there is a solution:

• 1.For two empty sets $$$s$$$,$$$t$$$,$$$occurrences(k) \leq n$$$ holds;

• 2.Assume for two empty sets $$$s$$$,$$$t$$$ if size $$$n$$$,$$$occurrences(k) \leq n$$$ holds.We do remove a $$$k$$$ from one set and remove a number which is not $$$k$$$ from another set.After that,the size becomes $$$n-1$$$,and $$$occurrences(k) \leq n-1$$$ holds.

#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
using namespace std;
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define PI acos(-1)
#define pii pair<int,int>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define len(s) (int)s.size()
#define F first
#define S second
const int mod=1e9+7;
int dp[20001][101][101];
int a[101];
const int add=10000;
const int L=-10000;
const int R=10000;
int f(int sum,int l,int r)
{
	//count number of non-empty subsequence of subarray [l,r] 
	//with adding=sum
	if( !(sum>=L and sum<=R))
		return 0;
	
	if(l==r)
	{

		if(sum==a[l])
			return 1;
		return 0;
	}
	if(dp[sum+add][l][r]!=-1)
		return dp[sum+add][l][r];
	int ans1=f(sum,l,r-1);
	int ans2=f(sum,l+1,r);
	int rem=0;
	if(l+1<=r-1)
		rem=f(sum,l+1,r-1);
	int ans3=0;
	if(l+1<=r-1)
		ans3=f(sum-a[l]-a[r],l+1,r-1)+(sum==(a[l]+a[r]));
	else
		ans3=(sum==(a[l]+a[r]));
	
	return dp[sum+add][l][r]=(((ans1+ans2)%mod-rem+mod)%mod+ans3)%mod;
}
void solve()
{
	int n,x;
	cin>>n>>x;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n<3)
	{
		cout<<0;
		return ;
	}
	else
	{
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
			a[i]-=x;
		int ans=0;
	
		for(int i=1;i<=n;i++)
		{
			for(int j=i+2;j<=n;j++)
			{
				ans+=f(0,i+1,j-1);
				ans%=mod;
			}
		}
		cout<<ans;
	}
}
signed main()
{
fastio
int TestCases=1;
//cin>>TestCases;
while(TestCases--)
{
solve();
cout<<endl;
}
}

Firstly,we substract all $$$a_i$$$ by $$$x$$$.Then the problem is equivent to count the number of subsequences which's sum is $$$0$$$.

Consider sort the array and do DP.Note $$$dp_{l,r,s}$$$ as the number of subsequences with $$$a_l$$$ as the head, $$$a_r$$$ as the tail, and $$$s$$$ as the sum.

For $$$dp_{l,r,0}(2\leq l \leq r \leq n-1)$$$,it's contribution is $$$dp_{l,r,0}*(l-1)*(n-r)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> fac(2222222);

        fac[0] = 1;
        for (int i = 1; i <= 2000000; i++) {
                fac[i] = (fac[i - 1] * i) % MOD;
        }

        auto binpow = [&](int x, int y) {
                int res = 1;

                while (y > 0) {
                        if (y & 1) (res *= x) %= MOD;

                        (x *= x) %= MOD;
                        y >>= 1;
                }

                return res;
        };

        vector<int> inv(2222222);

        inv[2000000] = binpow(fac[2000000], MOD - 2);
        for (int i = 1999999; i >= 0; i--) {
                inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }

        auto comb = [&](int n, int r) {
                if (n < r) {
                        cout << "hi\n";
                        exit(0);
                }
                return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
        };

        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;
                // general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
                int ans = comb(m - 1, n - 1);

                if (n - 1 <= m - (m + 1) / 2) {
                        ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
                }

                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        
        return 0;
}

As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i)< \lceil m/2 \rceil$$$.

What's the number of arrays satisfying the following condition?

• 1.All $$$a_i$$$ are positive integers;

• 2.$$$\Sigma a_i=m$$$.

The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.

$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.

We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.

The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.

The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m, s;
                cin >> n >> m >> s;

                set<pair<int, int>> st;
                st.insert({s, 0});

                for (int i = 0; i < m; i++) {
                        int l, r;
                        cin >> l >> r;

                        vector<pair<int, int>> del;
                        int mnl = INFF, mnr = INFF;
                        for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
                                if (it->fi > r) break;

                                if (l - 1 >= 1) {
                                        mnl = min(mnl, it->se + it->fi - l + 1);
                                }

                                if (r + 1 <= n) {
                                        mnr = min(mnr, it->se + r + 1 - it->fi);
                                }

                                del.push_back(*it);
                        }
                        
                        for (auto p : del) st.erase(p);

                        auto it = st.lower_bound({l - 1, 0});
                        if (it != st.end() && it->fi == l - 1) {
                                mnl = min(mnl, it->se);
                                st.erase(it);
                        }

                        auto it2 = st.lower_bound({r + 1, 0});
                        if (it2 != st.end() && it2->fi == r + 1) {
                                mnr = min(mnr, it2->se);
                                st.erase(it2);
                        }

                        if (l - 1 >= 1) {
                                st.insert({l - 1, mnl});
                        }

                        if (r + 1 <= n) {
                                st.insert({r + 1, mnr});
                        }
                }

                int ans = INFF;

                for (auto [pos, cost] : st) {
                        ans = min(ans, cost);
                }

                cout << ans << '\n';
        }
        
        return 0;
}

The original idea of this problem is using segment tree, hence the $$$n \leq 2\cdot 10^5$$$ constraint. However, this problem can be solved easier by using std::set.

For this problem, we can do DP to solve the problem.

Define $$$dp_i$$$ after the $$$j$$$-th attack as minimum energy needed to avoid the first $$$j$$$ attacks and we ended up at tile $$$i$$$. If we try updating all $$$n$$$ indices for each attack (by doing $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ for all $$$1 \leq j \leq n$$$), that will cost $$$O(n)$$$ transition, which means the complexity will be $$$O(n^2m)$$$ per test case. Since it's too slow, we need some observation.

Observation. For the $$$k$$$-th attack, we only need to update two DP indices each attack and it's optimal to do $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ where $$$i=l_k-1$$$ or $$$i=r_k+1$$$ (if those two indices actually exist inside the range $$$[1,n]$$$) and $$$l_k \leq j \leq r_k$$$

Proof. Assume that everytime the boss attacks, it is sometimes optimal for us to move if we didn't stand inside the incoming lazer previously. So, assume at some point, we went to the right $$$y$$$ tiles as the "optimal" route. Then, there are three cases for the next attack:

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(x > y)$$$. In this case, the current optimal is not the same as the previous optimal, since we could've just not move in previous turn and then move to the left by $$$x-y$$$ tiles.

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(0 < x \leq y)$$$. In this case, the current optimal is also not the same as the previous optimal, since we could've just not move in previous turn and then move to the right by $$$y-x$$$ tiles.

• The current optimal route involves going to the right by $$$x$$$ tiles $$$(x \geq 0)$$$. In this case, there is an alternative solution, where we could've just not move in previous turn and then move to the right by $$$x+y$$$ tiles. It'll result with the same energy spent.

So, it is optimal to do nothing if we don't stand inside the lazer.

If we do stand inside the lazer (assume it's the $$$j$$$-th lazer), it is optimal to go to either $$$l_j-1$$$ or $$$r_j+1$$$, since with the same idea as above, one of these tiles are either the most optimal solution, or one of the most optimal solution (think of it like a waterfall :]).

Now, with this in mind, we can implement this in $$$O(n\sum_{i=1}^n (r_i-li))$$$ per test case. Since it's still too slow, we can optimize it again. Notice that for each attack, we're only interested from the updates that actually give paths, not the one getting blocked by the lazer. So, we will try to implement this using C++ std::set. First, create the set $$$route$$$ which stores all previously updated $$$dp$$$ indices that give paths (since we update the tiles that will get hit by the lazer for each attack to $$$INF$$$ again after updating $$$dp{li-1}$$$ and $$$dp{r_i+1}$$$). Set $$$dp_i=INF$$$ for all $$$1 \leq i \leq n,i \neq s$$$, $$$dp_s=0$$$, and . Then, do the following for the j-th attack:

• Find all the element $$$k$$$ in $$$route$$$ such that $$$l_j \leq k \leq rj$$$.

• For each of the element satisfying the constraint above, update $$$dp{lj-1}$$$ to $$$\min(dp{l_j-1},dp_k+k-lj+1)$$$ and $$$dp{rj+1}$$$ to $$$\min(dp{r_j+1},dp_k+r_j+1-k)$$$

• Set all $$$dp_k$$$ to $$$INF$$$, remove all elements satisfying the constraint above, and then add $$$l_j-1$$$ and $$$r_j+1$$$ to $$$route$$$

The time complexity of this would be $$$O(m\log m)$$$ with $$$O(n)$$$ initializer and $$$O(n)$$$ finding optimal of each $$$dp$$$ index for each test case.

To optimize this even further, notice that after all the $$$m$$$ attacks, every index outside the $$$route$$$ would have the value of $$$INF$$$, so we only need to check the minimum from all $$$dp$$$ with indices inside $$$route$$$ (which is $$$O(m)$$$) and only to reset those indices as well for the next test case (which is also $$$O(m)$$$).

Once again, beware of the fact that $$$l_i-1$$$ or $$$r_i+1$$$ might be out of the arena range.

Time complexity: $$$O(m\log m)$$$

Bonus: Solve the problem if $$$n \leq 10^9$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<bool> ok(22222, 0);

        auto conv = [&](int x) {
                int res = 0;

                while (x > 0) {
                        int y = x % 10;

                        res += y * y;
                        x /= 10;
                }

                return res;
        };

        for (int i = 1; i <= 16200; i++) {
                int x = i;

                set<int> vis;
                
                while (!vis.count(x)) {
                        vis.insert(x);

                        int y = conv(x);
                        if (x == y) {
                                ok[i] = 1;
                        }
                        x = y;
                }
        }
        
        vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
        dp[0][0] = 1;

        for (int i = 1; i <= 200; i++) {
                for (int j = 0; j < 20000; j++) {
                        for (int k = 0; k <= 9; k++) {
                                dp[i][j + k * k] += dp[i - 1][j];
                                dp[i][j + k * k] %= MOD;
                        }
                }
        }

        int t;
        cin >> t;

        while (t --> 0) {
                string l, r;
                cin >> l >> r;

                auto calc = [&](string s, bool on) {
                        int res = 0;
                        int n = (int)s.length();
                        int cur = 0;

                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < s[i] - '0'; j++) {
                                        for (int k = cur + j * j; k <= 16200; k++) {
                                                res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
                                                res %= MOD;
                                        }
                                }
                                cur += (s[i] - '0') * (s[i] - '0');
                        }

                        if (ok[cur] && on) res += 1;

                        return res;
                };
                
                int ans = calc(r, 1) - calc(l, 0);
                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        return 0;
}

Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.

We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.

Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).

It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long
const int bk=500;
namespace sumadd {
   int tag[bk],pb[bk],pre[bk][bk];
   void addib(int l,int r,int id,int v) {
      for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
      tag[id]=0;
   }
   void add(int l,int r,int v) {
      if(l/bk==r/bk) {
         addib(l%bk,r%bk,l/bk,v);
         for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
         return;
      }
      if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
      if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
      while(l<=r) {tag[l/bk]+=v;l+=bk;}
      for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
   }
   int sum(int l,int r) {
      if(l/bk==r/bk) {
         return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
      }
      int sum=0;
      if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
      if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
      sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
      return sum;
   }
   void cln() {
      for(int i=0;i<bk;++i) {
         tag[i]=pb[i]=0;
         for(int j=0;j<bk;++j)
            pre[i][j]=0;
      }
   }
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
   int n,m,q;
   cin >> n >> m >> q;
   for(int i=1,l,r;i<=m;++i) {
      cin >> l >> r;
      ivl[i/bk][i%bk]={l,r};
      lp.push_back(lp.end()[-1]+r-l+1);
   }
   cerr << endl;
   lp.push_back(2147483647);
   for(int i=1,o,l,r,v;i<=q;++i) {
      cin >> o >> l >> r;
      if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
      else {
         auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
         qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
         if(qry[i][1]==qry[i][2]+2) {
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            l-=*prev(il);r-=*prev(il);
            ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
            flag[i]=true;
            continue;
         }
         if(qry[i][1]==qry[i][2]+1) {
            ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
            ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
            flag[i]=true;
            continue;
         }
         if(il!=lp.begin()) {
            int p=qry[i][1]-1;l=*il-l+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.second+1-l,t.second);
         }
         if(next(ir)!=lp.end()) {
            r-=*ir;
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.first,t.first+r-1);
         }
         if(flag[i]) ans[i]=-ans[i];
      }
   }
   sumadd::cln();
   for(int k=0;k<bk;++k) {
      int sum=0;
      for(int i=0;i<bk;++i) {
         auto t=ivl[k][i];
         if(t==pair<int,int>{0,0}) continue;
         cnt[t.first]++;
         cnt[t.second+1]--;
      }
      for(int j=1;j<=2;++j)
         for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
      for(int i=1;i<=q;++i)
         if(qry[i][0]==1) {
            sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
         }
         else
            if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
      for(int i=1;i<=n;++i) cnt[i]=0;
   }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==1)
         sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
      else {
         if(flag[i]) continue;
         int l=qry[i][1],r=qry[i][2];
         if(l>r) continue;
         if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
            for(int j=l;j<=r;++j) {
               auto t=ivl[j/bk][j%bk];
               ans[i]+=sumadd::sum(t.first,t.second);
            }
            continue;
         }
         while(l%bk!=0)    {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
         while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
      }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==2)
         cout << ans[i] << ' ';
   cout << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Consider SQRT decomp for $$$[l_i,r_i]$$$, putting each $$$sqrt(n)$$$ of $$$[l_i,r_i]$$$ into a block, and maintaining the sum of the group, and the number of occurrences in the block in each original array $$$a_i$$$.

Enumerate all blocks, and if a query completely contains an sqrt, then +=sum is added to the result of the query.

If we add, then sum+= the number of times the number * added value. (This can be done with two times perfix sums)

For queries that are not complete blocks, consider direct brute force maintenance of the A-array and query, it has $$$n^{1.5}$$$ query operations and n modification operations, so we can use a partitioned data structure to do $$$O(1)$$$ queries, $$$O(n^{0.5})$$$ modifications.

So, the total complexity is $$$O(n^{1.5})$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long

const int MOD=998244353;
void Delta() {
   int a,b,c,d;
   cin >> a >> b >> c >> d;
   cout << (a+b>c+d?"YES":"NO") << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The probability of Alice's winning is strictly higher than Bob's iff $$$l_1+r_1>l_2+r_2$$$.

Submitting this code directly will get ILE, please delete cerr and submit.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace Fact {
   vector<char> isPrime;
   vector<int> Prime,OneFac;
   void GetPrime(int n){for(int i=0;i<n;++i)isPrime[i]=1;isPrime[1]=1;for(int i=2;i<=n;i++){if(isPrime[i])Prime.push_back(i);for(int j:Prime){if(i*j>n) break;isPrime[i*j]=0;OneFac[i*j]=j;if(i%j==0)break;}}}
   void Fac_dfs(int x,int y,vector<int>& ans,vector<pair<int,int>>& FacList){if(x==(long long)(FacList.size())){ans.push_back(y);return;}int k=1;for(int i=0;i<=FacList[x].second;++i){Fac_dfs(x+1,y*k,ans,FacList);k*=FacList[x].first;}}
   vector<pair<int,int>>GetPrimeFac(int a){vector<pair<int,int>>answer;if(isPrime[a])return(vector<pair<int,int>>{pair<int,int>{a,1}});answer.push_back({OneFac[a],1});a/=OneFac[a];while(!isPrime[a]){if(OneFac[a]==answer.back().first)answer.back().second++;else answer.push_back({OneFac[a],1});a/=OneFac[a];}if(a==answer.back().first)answer.back().second++;else answer.push_back({a,1});return(answer);}
   vector<int>GetFacList(int a){vector<int> ans;vector<pair<int,int>>FacList=GetPrimeFac(a);Fac_dfs(0,1,ans,FacList);return(ans);}
   void init(int n){isPrime.resize(n+2);OneFac.resize(n+2);GetPrime(n);}
   void init(){init(10000005);}
};
#define int long long

const int MOD=998244353;
void Delta() {
   int a,b;
   cin >> a >> b;
   if(Fact::isPrime[a]||(a/Fact::OneFac[a]<b)) cout << "NO" << endl;
   // in code "OneFac" is The smallest non-1 factor.
   else {
      cout << "YES" << endl;
      for(int i=1;i<b;++i) cerr << Fact::OneFac[a] << ' ';
      cerr << a-(b-1)*Fact::OneFac[a] << endl;
   }
}
signed main() {
   Fact::init(100001);
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Let's say we finally get the gcd $$$x$$$, so all $$$a_i$$$ are multiples of $$$x$$$.

We want all $$$a_i$$$to be positive, so every $$$a_i$$$ is at least $$$x$$$, and all sums are at least $$$kx$$$ and sum is divisible by $$$x$$$ (You have some $$$a_i$$$ that is divisible by $$$x$$$, add it up, and it's still divisible by $$$x$$$).

Since we already know sum (is $$$n$$$), $$$x$$$ can only be a factor of $$$n$$$, Since $$$x>1$$$, just to take the smallest non-1 factor of $$$n$$$ and check. If $$$kx$$$ is less than $$$n$$$, then just put all the rest on $$$a_k$$$, which still guarantees that gcd=x.

(The constructional output is given in cerr of code for help understand)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
int n,m,sum;
map<int,int> a,b,c;
vector<pair<int,int>> Q;
void dfs(int idx,int A,int B,int C) {
   if(idx==(int)Q.size()) {
      sum+=a[A]*b[B]*c[C];
      return;
   }
   for(int i=0,t1=1;i<=Q[idx].second;++i,t1*=Q[idx].first)
      for(int j=i,t2=1;j<=Q[idx].second;++j,t2*=Q[idx].first)
         for(int k=j,t3=1;k<=Q[idx].second;++k,t3*=Q[idx].first)
            if(k==Q[idx].second)
               dfs(idx+1,A*t1,B*t2,C*t3);
}
void Delta() {
   cin >> n >> m;
   for(auto i:{&a,&b,&c})
      for(int j=1,x;j<=n;++j) {
         cin >> x;
         ++(*i)[x];
      }
   for(int i=2;i*i<=m;++i)
      while(m%i==0) {
         if(Q.empty()||Q.end()[-1].first!=i) Q.push_back({i,1});
         else Q.end()[-1].second++;
         m/=i;
      }
   if(m!=1)
      if(Q.empty()||Q.end()[-1].first!=m) Q.push_back({m,1});
      else Q.end()[-1].second++;
   else;
   dfs(0,1,1,1);
   cout << sum << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

If a number is less than $$$10^9$$$, it has a maximum possible factor of $$$1344$$$, enumerate two factors of $$$m$$$, then divide the third factor, and then use map to do count to pass.

In this table you can find all the values of $$$\text{d}(n)$$$ and $$$ω(n)$$$ for your future use :)

upd:

$$$\text{d}(n)$$$ = the number of different factors, and $$$ω(n)$$$ = the number of different prime factors

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[500001];
void Delta() {
   int n,x; cin >> n >> x;
   if(x<n-1||x>(n/2)*(n-n/2)) {
      cout << -1 << endl;
      return;
   }
   for(int i=2;i<=n/2+1;++i) cout << i-1 << ' ' << i << endl;
   x-=n-1;
   for(int i=n/2+2;i<=n;++i) {
      cout << min(x,n/2-1)+1 << ' ' << i << endl;
      x-=min(x,n/2-1);
   }
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The key to solving the problem is — consider constructing a tree with the highest score first.

It's obvious all leaf have the same LCA (othwise,link leaves with smaller depths next to leaves with larger depths, and the score will not decrease) .Note $$$x$$$ as the number of leaf nodes,then the score is $$$x(n-x)$$$,when $$$x=\lfloor\frac{n}{2}\rfloor$$$,it reaches the maximum.

From the tree with the highest score, we can easily construct a tree with any score (by moving each leaf node up).

For convenience,note $$$A={a_1,a_2,...,a_n}$$$ and $$$B={a_{n+1},a_{n+2},...,a_{2n}}$$$($$$A,B$$$ are circular).

Calculate $$$preA$$$ and $$$sufB$$$:

• $$$\text{preA}_i:\max(a_j+...+a{i-1}+a_{i})$$$;

• $$$\text{sufB}_i:\max(b_i+b_{i+1}+...+b_{j})$$$;

This can be solved using monotonic stacks in $$$\Theta(n)$$$.

Then reverse $$$A,B$$$ and do it again.

The answer is the maximum of the following values:

• $$$\max(\text{preA}_i);$$$

• $$$\max(\text{sufB}_i);$$$

• $$$\max(\text{preA}_i+\text{sufB}_{i+1}).$$$

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=3000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  ans;
int a[N],b[N],Q[N];
ll  Sa[N],Sb[N],prea[N],sufb[N];

void solve()
{
	for(int i=1;i<=n;i++)   a[i+n]=a[i],b[i+n]=b[i];
	for(int i=1;i<=n*2;i++) Sa[i]=Sa[i-1]+a[i],Sb[i]=Sb[i-1]+b[i];
	int head=1,tail=0;
	for(int i=1;i<=n*2;i++)
	{
		if(i>n)
		{
			while(i-Q[head]>n) head++;
			prea[i-n]=Sa[i]-Sa[Q[head]];
		}	
		while(head<=tail&&Sa[Q[tail]]>Sa[i]) tail--;
		Q[++tail]=i;
	}
	head=1;tail=0;
	for(int i=n*2;i;i--)
	{	
		while(head<=tail&&Sb[Q[tail]]<Sb[i]) tail--;
		Q[++tail]=i;
		if(i<=n)
		{
			while(Q[head]-i+1>n) head++;
			sufb[i]=Sb[Q[head]]-Sb[i-1];
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,prea[i]);
	for(int i=1;i<=n;i++) ans=max(ans,sufb[i]);
	for(int i=1;i<n;i++)  ans=max(ans,prea[i]+sufb[i+1]);
	ans=max(ans,prea[n]+sufb[1]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		ans=-INF;
		solve();
		for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]),swap(b[i],b[j]);
		solve();
		cout<<ans<<'\n';
	}
	
	return 0;
}

We can see how to merge the largest subsegment of two intervals and by GSS1 in $$$\Theta(1)$$$ time, so using a seg tree and just enumerates all possible k and computs it in $$$O(\log n)$$$ time. This is $$$O(n\log n)$$$.

As you can see, each query is a prefix or suffix of a single array, so we can use the prefix sum and the suffix sum, this is $$$\Theta(n)$$$.

I mentioned a minimum-memory solution in the announcement comment, so now explain how to do $$$\text{12,000 KB}$$$.

For this $$$\Theta(n)$$$ level's memory we can only save int32 a[].

For the prefix sum, just save the value of the previous one, and then add it up, you can do $$$\Theta(1)$$$ memory.

For suffix sum, do the normal suffix sum first, and save the suffix sum values on all $$$k·\sqrt{n}$$$ locations. Then compute each sqrt block separately, $$$\Theta(\sqrt{n})$$$ saves its suffix, computes its perfix recursively, and releases the memory after the calculation is complete.

This allows us to achieve memory complexity $$$\Theta(\text{sqrt})$$$ and time complexity $$$\Theta(n)$$$ in addition to "int32 a[]".

It's $$$\text{12,000 KB}$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
int a[3000010];
#define int long long
#define B 1000
class node{public:int sum,lm,rm,ans;}temp;
inline void merge1(node&a,node&l,node&r){a={l.sum+r.sum,max(l.lm,l.sum+r.lm),max(r.rm,r.sum+l.rm),max({l.ans,r.ans,l.rm+r.lm})};}
inline void merge2(node&a,node&l,node&r){a={l.sum+r.sum,min(l.lm,l.sum+r.lm),min(r.rm,r.sum+l.rm),min({l.ans,r.ans,l.rm+r.lm})};}
inline node i2node(int x){return {x,x,x,x};}
node sufb[1500010/B+10],sufnb[1500010/B+10],tsuff[B+10],tsufnf[B+10];
void Delta() {
   int n,s=-2147483648,sum=0,flag=true,mx=-2147483648;cin >> n;
   for(int i=1;i<=n*2;++i) {
      cin >> a[i];sum+=(int)a[i];
      flag&=a[i]<0;mx=max(mx,(int)a[i]);
   } 
   node pre=i2node(0),pren=i2node(0),suf=i2node(0),sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge1(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge1(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge1(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge1(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge1(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge1(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge1(temp,pren,tsuff[i%B+1]);
      merge1(temp,temp,pre);
      merge1(temp,temp,tsufnf[i%B+1]);
      s=max(s,temp.ans);
   }
   pre=pren=suf=sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge2(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge2(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge2(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge2(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge2(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge2(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge2(temp,pren,tsuff[i%B+1]);
      merge2(temp,temp,pre);
      merge2(temp,temp,tsufnf[i%B+1]);
      s=max(s,sum-temp.ans);
   }
   cout << (flag?mx:s) << '\n';
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[200001],b[200001],vis[200001];
vector<int> Q[200001];
void dfs(int x) {
   if(vis[x]) return;
   vis[x]=true;
   for(int i:Q[x]) dfs(i);
}
void Delta() {
   int cnt=0,blk=0,n; // count,block number
   cin >> n;
   for(int i=1;i<=n;++i) {
      cin >> a[i];
      b[i]=a[i];
      Q[i].clear();
      vis[i]=0;
   }
   sort(b+1,b+1+n);
   for(int i=1;i<=n;++i) 
      if(a[i]!=b[i]) {
         Q[a[i]].push_back(b[i]);
         Q[b[i]].push_back(a[i]);
      } else cnt++;
   for(int i=1;i<=n;++i)
      if(!vis[a[i]]&&a[i]!=b[i]) {
         blk++;
         dfs(a[i]);
      }
   if(n==2) {
      if(cnt==2) cout << 0 << endl;
      else cout << -1 << endl;
      return;
   }
   if(cnt!=0) cout << blk+(n-cnt) << endl;
   else if(blk==1) cout << n+2 << endl;
   else cout << n+blk << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Compare the original array (say $$$a$$$) to the sorted one (say $$$b$$$). Since we can move only one token at once, in one move we can place at max one token to its correct place. So let's try to minimise the number of moves that don't do this.

To make optimal moves, model a directed multi-edged graph. Start with only vertices ($$$1$$$ to $$$n$$$), no edges, and add a directed edge from $$$a[i]$$$ to $$$b[i]$$$ when $$$a[i]!=b[i]$$$, for each $$$i$$$ (meaning that $$$b[i]$$$ should be placed in place of $$$a[i]$$$).

We can follow an optimal scheme like this: For now let us assume there is at least one position where correct token is placed (let it be $$$p$$$). Choose an incorrectly placed token, place it on top of $$$p$$$. This creates a gap. Place the correct token for this place. This moves the gap somewhere else. Again choose a corect token for the gap and so on. In the end, place the token stacked on top of $$$p$$$ into the gap, close the gap, and all the tokens we touched are placed correctly.

In the graph, placing a token from $$$b[i]$$$ to gap at $$$a[i]$$$ would mean moving from $$$a[i]$$$ to $$$b[i]$$$ in the graph along an edge and removing the edge. Thus the problem reduces to removing all edges of the graph in minimum number of moves.

The graph is split into disjoint connected componnts. We can thus independently resolve each component optimally for minimum number of moves.

Next, we prove that a connected component is always an euler circuit.

Claim $$$1$$$: The component would have a cycle. If it doesn't, then following some path $$$a \rightarrow b \rightarrow ...$$$, we will reach a dead end, which means that the last element has no place to go, which is not true since it belongs to the array and must have a correct position to be placed at. By induction, we can keep removing cycles (by moving along them and removing edges), and so the component is basically a set of directed cycles intersecting at vertices.

Claim $$$2$$$: It will hence form an euler circuit. Let us go along a cycle. It starts at $$$v$$$, ends at $$$v$$$. Now if there is a cyce intersecting at some vertex $$$v'$$$ in the cycle, on reaching $$$v'$$$ resolve that cycle, return at $$$v'$$$, continue on the older cycle. By this inductive argument, we can cover all edges exactly once and return to $$$v$$$, making an euler circuit.

To find the precise number of moves to resolve a component involving $$$s$$$ tokens, we need to create a gap in $$$1$$$ move, place $$$s-1$$$ tokens correctly, and place the last token we moved initially. Total $$$s+1$$$ moves. To create a gap, we need to place a token from our position to some position not in the component.

Now, proper casework:

Let the number of tokens not placed correctly be $$$co$$$. Let the number of disjoint connected components be $$$x$$$.

If $$$co<n$$$: There is always a correctly placed position to stack our token on and create a gap. So, each component of size s will be resolved in $$$s+1$$$. So total $$$co+x$$$ moves.

If $$$x>1$$$: Since there are $$$>1$$$ components, we can use a position from the other component to create gap for one component. Again $$$co+x$$$.

$$$co==n$$$ and $$$x==1$$$: It may be a single cycle, or $$$>1$$$ joint cycles. If there are $$$>1$$$ joint cycles, resolve one of the cycles, then it reduces to the cases above. Totals to $$$n+2$$$ moves. For exactly one cycle, graph is $$$1 \rightarrow 2 \rightarrow ...n \rightarrow 1$$$. So stack $$$1$$$ on $$$2$$$, resolve rest $$$n-2$$$, total $$$n-1$$$. Then resolve $$$1$$$ and $$$2$$$ which takes $$$3$$$ moves. So total again is $$$n+2$$$. Since $$$n+1$$$ is not possible in this case, and we construct a solution in $$$n+2$$$, it is optimal.

Final solution:

1. $$$(co < n)$$$ or $$$(x>1)$$$ : $$$co+x$$$

2. $$$(co==n)$$$ and $$$(x==1)$$$ : $$$n+2$$$

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

#define int long long

void test_case() {
	int n; cin >> n;
	int a = floor(sqrt(n));
	int b = (n + a - 1) / a;
	cout << a * 2 + b * 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

If $$$n$$$ is a perfect square number, we find that the square dyeing scheme is always optimal.The answer is $$$4\sqrt{n}$$$.

Otherwise,if $$$n-\lfloor \sqrt{n} \rfloor ^2 \leq \lfloor \sqrt{n} \rfloor$$$,the answer is $$$4\lfloor \sqrt{n} \rfloor+2$$$.Otherwise the answer is $$$4\lfloor \sqrt{n} \rfloor+4$$$.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		std::vector<vector<int>> v(2);
		std::vector<int> cnt(2*n + 10);
		for(int i = 0; i < 2; i++) {
			v[i].resize(n);
			for(int &u:v[i]) {
				cin >> u;
				cnt[u]++;
			}	
		}
		int mex = 0;
		while(cnt[mex]) mex++;
		int ans = mex * (n&1);
		for(int i = 0; i < n; i++) {
			int val = v[1 ^ (i%2)][i];
			if(!(n&1)) {
				int cur_mex;
				if(val > mex || cnt[val] > 1) cur_mex = mex;
				else cur_mex = val;
				ans = max(ans, cur_mex); 
			}
		}
		cout << ans << "\n";
	}
}

If $$$n$$$ is odd,we can traverse all cells, which is a simple situation.

If $$$n$$$ is even,we can skip one of $$$(1,2) (1,4) (1,6)...(1,n),(2,1),(2,3),(2,5)...(2,n-1)$$$.If there is a duplicate number, skip it. Otherwise, skip the maximum number.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,k;
int  a[N],pre1[N],tot1[N];
char s[N];

void init()
{
	pre1[n+1]=tot1[n+1]=0;
	for(int i=n;i;i--)
	{
		if(a[i])
		{
			pre1[i]=pre1[i+1]+1;
			tot1[i]=tot1[i+1]+1;
		}
		else
		{
			pre1[i]=0;
			tot1[i]=tot1[i+1];
		}
	}
}

int check(int idx,int c1)
{
	return (pre1[idx]<c1)||(pre1[idx]==c1&&tot1[idx]==c1);
}

void solve1()
{
	int c0=(n+k)/2,c1=c0-k;
	for(int i=1;i<=n;i++)
	{
		if(a[i])
		{
			c1--;
			printf("1");	
		}
		else
		{
			if(c0&&check(i+1,c1))
			{
				c0--;
				printf("0");	
			}
			else
			{
				c1--;
				printf("1");
				for(int i=1;i<=c0;i++) printf("0");
				for(int i=1;i<=c1;i++) printf("1");
				break;
			}
		}
	}
	printf("\n");
}

void solve2()
{
	int c0=0,c1=0;
	if(k>0)
	{
		c0=k;
		c0++,c1++;	
		while(c0+c1<=n) c0++,c1++;	
	}
	else
	{
		c1=-k;
		while(c0+c1<=n) c0++,c1++;	
	}
	printf("1");
	c1--;
	for(int i=1;i<=c0;i++) printf("0");
	for(int i=1;i<=c1;i++) printf("1");
	printf("\n");
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%s",&n,&k,s);
    	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    	init();
    	if(n==1&&a[1]==0&&k==1)
    	{
	    	printf("0\n");
	    	continue;
	    }
    	if((n+k)&1) solve2();
    	else
		{
	    	int c0=(n+k)/2,c1=c0-k;
			if(c0<0||c1<0) solve2();
			else
			{
				if(check(1,c1)) solve1();
				else solve2();
			}
	    }
	}
	
	return 0;
}

First,be careful when $$$y=0$$$ and $$$k=1$$$ :)

Consider the answer with a length greater than $$$n$$$, which is always $$$10...01...1$$$.The construction is not hard.

What about the answer with length $$$n$$$?

Consider setting numbers from the highest bit to the lowest bit and current bit is $$$i$$$.If $$$y_i=1$$$,we must set $$$x_i=1$$$.Otherwise($$$y_i=0$$$),we either do set $$$x_i=0$$$ and go to the lower bit,or do set $$$x_i=1$$$, $$$x_{i+1}x_{i+2}...x_n=0...01...1$$$ and break.

For $$$y_i=0$$$,when can we do set $$$x_i=0$$$ and go to the lower bit?The condition is $$$re1>pre1_{i+1}$$$ or $$$re1==pre1_{i+1}$$$ and $$$pre1_{i+1}==tot1_{i+1}$$$.$$$re1$$$ is the current remaining number of $$$1's$$$,$$$pre1_{i+1}$$$ is the length of the continuous $$$1$$$ prefix of $$$y_{i+1}y_{i+2}...y_n$$$,and $$$tot1_{i+1}$$$ is the total of $$$1$$$ of $$$y_{i+1}y_{i+2}...y_n$$$.

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\n"; } }

Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.

It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.

Based on the above conclusion, we can make the optimal construction.

Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
ll  T,n,m,c;
ll  a[N][N];
ll  dp[N][N];

void init()
{
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		scanf("%I64d",&a[i][j]);
}

void DP()
{
	for(int i=1;i<=n;i++)
	{
		ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
		for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
		for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
		for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
		for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
		for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
	}
	ll ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dp[i][j]);
	printf("%I64d\n",ans);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	init();
    	DP();
	}
	
	return 0;
}

Consider DP.

Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.

Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.

Now consider which cell we go from to $$$(i,j)$$$.There are four situations.

$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;

$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.

$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.

$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n%6==1)
		{
			for(int i=1;i<n/6;i++) printf("0");
			printf("8\n");
			continue;
		}
		for(int i=1;i<=n/6;i++) printf("0");
		if(n%6==2) printf("1\n");
		else if(n%6==3) printf("7\n");
		else if(n%6==4) printf("4\n");
		else if(n%6==5) printf("2\n");
		else printf("\n");
	}
	
	return 0;
}

If $$$n=6k$$$,print $$$0...0$$$;

If $$$n=6k+1$$$,print $$$0...08$$$;

If $$$n=6k+2$$$,print $$$0...01$$$;

If $$$n=6k+3$$$,print $$$0...07$$$;

If $$$n=6k+4$$$,print $$$0...04$$$;

If $$$n=6k+5$$$,print $$$0...05$$$;

If $$$n=6k+6$$$,print $$$0...09$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,k;
int a[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++) a[i]=0;
		for(int i=1;i<=k;i++)
		{
			if(n<2) break;
			a[i]=1;
			n-=2; 
		} 
		for(int i=k;i;i--)
		{
			if(a[i])
			{
				if(n>=4) a[i]=9,n-=4;
				else if(n>=1) a[i]=7,n--;
				else break;
			}
		}
		for(int i=k;i;i--) if(a[i]) printf("%d",a[i]);
		printf("\n");
	}
	
	return 0;
}

First,maximize number of digits — fill each digit with $$$'1'$$$.

Then starting from the highest bit,consider maximizing the current digit — consider changing the current bit to $$$'9'$$$. If no enough matchsticks, consider $$$'7'$$$.

Luckily,you find $$$[1,2n,2,2n-1,...,n,n+1]$$$ works :)

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,x;

int check(vector<int> v)
{
	sort(v.begin(),v.end());
	for(int i=1;i<=n*2;i++) if(v[i]!=i) return 0;
	return 1;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&x);
		ll S=(ll)n*(2*n+1),a=2*n+1,b,flg=0;
		for(int i=x;i<=x;i++)
		{
			for(int j=1;j<=2*n;j++)
			{
				if((S-i-j)%(n-1)) continue;
				b=(S-i-j)/(n-1); 
				vector<int> v;
				v.push_back(0);
				v.push_back(i);
				for(int i=2;i<n*2;i++)
				{
					if(i&1) v.push_back(b-v.back());
					else    v.push_back(a-v.back());
				} 
				v.push_back(j);
				if(check(v))
				{
					for(int k=1;k<=n*2;k++) printf("%d%c",v[k],k==n*2?'\n':' ');
					flg=1;
					break;
				}
			} 
		} 
		if(!flg) printf("-1\n");
	}
	
	return 0;
}

Note $$$s_1=p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n},s_2=p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$.

We can easily get $$$s_1=2n+1$$$.

Consider fix $$$s_2$$$,we can get:$$$p_{2n}=n*s_1-p_1-(n-1)s_2$$$.Since $$$1\leq p_{2n} \leq 2n$$$, we found that there are no more than $$$3$$$ suitable $$$s_2$$$.

For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,m;
int t[N];
int a[N][N],b[N][N],c[N][N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&b[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				c[i][j]=(a[i][j]^b[i][j]);		
		t[0]=t[1]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				t[(i+j)&1]^=c[i][j];
		if(n==3&&m==3&&(c[1][2]||c[2][1]||c[2][3]||c[3][2])) printf("NO\n");
		else if(n==3&&m==4&&(c[2][1]||c[2][4])) printf("NO\n");
		else if(n==4&&m==3&&(c[1][2]||c[4][2])) printf("NO\n");
		else printf("%s\n",(t[0]||t[1])?"NO":"YES");		
	}
	
	return 0;
}

Consider a $$$3*3$$$ matrix,we can do something like:

$$$000$$$

$$$000$$$

$$$000$$$

$$$->$$$

$$$100$$$

$$$010$$$

$$$101$$$

$$$->$$$

$$$101$$$

$$$000$$$

$$$000$$$

Consider we can only flip $$$a_{x,y},a_{x,y+2}$$$ and $$$a_{x,y},a_{x+2,y}$$$,what about the answer?

Note $$$x_0=a_{1,1}⊕a_{1,3}⊕...,x_1=a_{1,2}⊕a_{1,4}⊕...$$$,the answer is $$$YES$$$ if and only if the $$$x_0=x_1=0$$$.

Let's go back to the original problem.The only difference is there are some unaccessable elements.Just do special judgment.

If $$$n=3,m=3$$$,unaccessable elements are $$$a_{1,2},a_{2,1},a_{2,3},a_{3,2}$$$;

If $$$n=3,m=4$$$,unaccessable elements are $$$a_{2,1},a_{2,4}$$$;

If $$$n=4,m=3$$$,unaccessable elements are $$$a_{1,2},a_{4,2}$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,flg;
int a[N],fre[N];
vector<int> G[N],ch[N];

void DFS(int x,int pr)
{
    for(int i=0;i<G[x].size();i++)
    {
	    int y=G[x][i];
            if(y==pr) continue;
	    ch[x].push_back(y);
            DFS(y,x);
    }
    if(x==1) return ;
    if(ch[x].size()==0) fre[x]=0;
    else if(ch[x].size()==1)
    {
    	fre[x]=0;
    	if(a[ch[x][0]]&&fre[ch[x][0]]) a[x]^=1;
    	else if(a[ch[x][0]]&&(!fre[ch[x][0]])) flg=0;
    }
    else if(ch[x].size()==2)
    {
    	if(fre[ch[x][0]]||fre[ch[x][1]])
    	{
    		a[x]^=(a[ch[x][0]]^a[ch[x][1]]);
	    	if(fre[ch[x][0]]&&fre[ch[x][1]]) fre[x]=1;
	    	else
	    	{
	    		fre[x]=0;
	    		if(a[ch[x][0]]&&a[ch[x][1]]) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][0]]&&(!fre[ch[x][0]])) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][1]]&&(!fre[ch[x][1]])) a[x]^=1,a[pr]^=1;
	    	}
	    }
	    else
	    {
	    	fre[x]=0;
    		if(a[ch[x][0]]^a[ch[x][1]]) flg=0;
	    	else a[x]^=a[ch[x][0]],a[pr]^=a[ch[x][0]];
    	}
    }
    else
    {
    	int tagf=0,taga=0;
    	for(int i=0;i<ch[x].size();i++) tagf|=fre[ch[x][i]],taga^=a[ch[x][i]];
    	if((!tagf)&&taga) flg=0;
    	else fre[x]=1,a[x]^=taga;
    }
}

void check1()
{
	int taga=0;
	for(int i=0;i<ch[1].size();i++) if((!fre[ch[1][i]])&&a[ch[1][i]]) flg=0;
	for(int i=0;i<ch[1].size();i++) taga^=a[ch[1][i]];
	if(taga^a[1]) flg=0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	    for(int i=1;i<=n;i++) G[i].clear(),ch[i].clear(); 
	    for(int i=1;i<n;i++)
	    {
    		int u,v;
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);
    		G[v].push_back(u);
    	   }
    	   flg=1;
    	   DFS(1,0);
           check1();
	   printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

Define free nodes $$$x$$$ — $$$free[x]=1$$$ means we can freely flip $$$x,fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0;

Define $$$col[x]$$$ — the value when node $$$x$$$ does not affect $$$fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0.Later on, we can see that this value is unique.

We update the values of $$$free[x],col[x]$$$ from bottom to top.

Case $$$1$$$:$$$x$$$ has $$$0$$$ son nodes.It's easy to get $$$free[x]=0,col[x]=a[x]$$$.

Case $$$2$$$:$$$x$$$ has $$$1$$$ son nodes.

We get $$$free[x]=0$$$.

If $$$col[son[x][0]]=0$$$,we don't need to flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]$$$;

If $$$col[son[x][0]]=1$$$ and $$$free[son[x][0]]=0$$$,no solution.Otherwise we must flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]⊕1$$$;

Case $$$3$$$:$$$x$$$ has $$$>2$$$ son nodes.

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$x$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[x][i]$$$,no solution.

If we can change all the descendant nodes(exclude itself) of $$$x$$$ to 0,$$$x$$$ is always a free node.

Let's calculate $$$col[x]$$$.If $$$tagc=1$$$,we must flip $$$x$$$ and a free node,so $$$col[x]=a[x]⊕1$$$.If $$$tagc=0$$$,$$$col[x]=a[x]⊕0$$$.

Case $$$4$$$:$$$x$$$ has $$$2$$$ son nodes.

If $$$son[x][1],son[x][2]$$$ are both not free nod:

• if $$$col[son[x][1]]⊕col[son[x][2]]=1$$$,no solution;

• if $$$col[son[x][1]]=col[son[x][2]]=0$$$,$$$free[x]=0,col[x]=a[x]$$$;

• if $$$col[son[x][1]]=col[son[x][2]]=1$$$,$$$free[x]=0,col[x]=a[x]⊕1$$$,and flip $$$a[fa[x]]$$$;

If $$$son[x][1],son[x][2]$$$ are both free node,$$$free[x]=1,col[x]=a[x]⊕col[son[x][1]]⊕col[son[x][2]]$$$.

Otherwise,do similar casework :)

Finally(I promise),let's check the answer,for all son nodes of node $$$1$$$:

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$1$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[1][i]$$$,no solution.

Otherwise,we should check $$$a[1]⊕tagc$$$.The answer is $$$YES$$$ if and only if $$$a[1]⊕tagc=0$$$.

Obviously,the length of a continuous segment with a negative contribution is $$$1$$$.

We can write a $$$O(n^2)$$$ DP:

$$$dp[i]=max(dp[j]-a[j+1]+a[j+2]|...|a[i])$$$

Then we notice there're at most $$$O(log maxa)$$$ different values in $$$a[j]|...|a[i]$$$ $$$(j<i)$$$.It's a classic conclution.

For a fix $$$a[j]|...|a[i]$$$ $$$=t$$$,we get $$$dp[i]=max(dp[j]-a[j+1])+t$$$.Since the value range of $$$j$$$ is continuous,we can use a segment tree to maintain it.It's $$$O(n log^2 n)$$$.

In fact,use prefix maximum value is enough.Note $$$premax[i]=max(dp[1]-a[2],...,dp[i]-a[i+1])$$$,$$$dp[i]=premax[j]+t$$$.It's $$$O(n log n)$$$.

This has prepared us for solving F2(solution2).

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=110;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
int a[N],pre[N];
ll  dp[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i<N;i++) dp[i]=pre[i]=0;
		for(int i=1;i<=n;i++)
		{
			int cur=0;
			scanf("%d",&a[i%N]);
			pre[i%N]=(pre[(i-1+N)%N]|a[i%N]);
			dp[i%N]=pre[i%N];
			for(int j=i;j>=max(3,i-60);j--) 
			{
				cur|=a[j%N];
				dp[i%N]=max(dp[i%N],dp[(j-2+N)%N]-a[(j-1+N)%N]+cur);
			}
		}
		printf("%I64d\n",dp[n%N]);
	}

	return 0;
}

You need to observation that the length of consecutive segments will not exceed $$$60$$$.

Then we can use a scrolling array for DP.

Note $$$maxp$$$ as the maximum index of the maximum value in $$$a$$$.

For $$$1 \leq k \leq maxp-1$$$,they do not meet the condition.

For $$$maxp+1 \leq k \leq n$$$,they all meet the condition.

You need to be careful of $$$k==maxp$$$,it meet the condition if and only if there is only one maximum value in $$$a$$$.

Note $$$a_1$$$ as the first $$$\lceil{n/2}\rceil$$$ numbers of $$$a$$$,and $$$a_2$$$ as the last $$$n-\lceil{n/2}\rceil$$$ numbers of $$$a$$$.

Through observation,we found that the following processes will be repeated cyclically:

• erase the leftmost number of $$$a_1$$$

• erase the leftmost number of $$$a_2$$$

• erase the rightmost number of $$$a_1$$$

• erase the rightmost number of $$$a_2$$$

In conclusion:

• If $$$|a_1|>|a_2|$$$(i.e. $$$n$$$ is odd),the answer is the number in the middle of $$$a_1$$$

• If $$$|a_1|=|a_2|$$$(i.e. $$$n$$$ is even),the answer is the number in the middle of $$$a_2$$$

We notice we can convert condition $$$3$$$ to $$$c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$$$.

This provides us with convenience: we can independently calculate the left and right value ranges.

If two ranges intersect, the answer is $$$YES$$$,otherwise the answer is $$$NO$$$.

Let's calculate the left value ranges.Make all $$$a_i=0$$$ to $$$1$$$ and $$$a_i=1$$$ to $$$-1$$$,it is the value range of all subarrays of appropriate length.

In fact,we only need to find max subsegment sum and min subsegment sum.It's a classic problem.

You may have already guessed:if $$$x_1<y_1$$$,and you get $$$minsum,maxsum$$$,the range of values is continuous — $$$[minsum,maxsum]$$$.Why?

You also need to be careful of the edge cases that $$$x_i=y_i(1 \leq i \leq 2)$$$.

We notice we can calculate each bit independently.

In other words,note $$$f(a_i,j)$$$ as the $$$j^{th}$$$ bit under the binary representation of $$$a_i$$$,the answer is $$$\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$$$.

Let's calculate the sum of the $$$0^{th}$$$ bit.

$$$a_{i,0}=0,1,0,1,...$$$

Note $$$pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$$$,then

$$$pre_{i,0}=0,1,1,0,0,1,1,0,...$$$

We noticed that the loop section of this sequence is $$$4$$$ and can calculate the total number of $$$'1'$$$(note it as $$$c_1$$$).The total number of subarrays with xor-value $$$1$$$ is $$$c_1*(n+1-c_1)$$$.

For the $$$1,2,...30^{th}$$$ bit,use the similar method to calculate it.

Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value and note the set of them as $$$X$$$),how to calculate the number of schemes?

Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...

If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.

This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.

The answer is:

$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.

If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.

The answer is:

$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.

Let's go back to the easier problem.The number of schemes is $$$\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$$$.

Finally, how to calculate the total score?We can convert the formula into:$$$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$$$.

There's another dp solution:$$$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$$$.It's actually do the same thing.

Note $$$c_{i,j}=a_{i,j}⊕b_{i,j}$$$.The problem is equivalent to turning $$$c$$$ into a zero matrix.

Consider $$$l=2$$$.What about the solution?

We can easily get:the answer is $$$YES$$$ if and only if the xor-sum of all numbers is $$$0$$$.

Now let’s consider $$$l=3$$$.The method can be extended to $$$l=k$$$.

We notice we can do:

$$$0000->1110->1001$$$

If we can only filp $$${a_{x,y},a_{x,y+3}}$$$ and $$${a_{x,y},a_{x+3,y}}$$$,what about the answer?

We group the elements in the matrix $$$c$$$ like:

$$$1231231... $$$

$$$4564564... $$$

$$$7897897... $$$

$$$1231231... $$$

$$$... $$$

Note $$$XOR(i)$$$ as xor-sum of all numbers in group $$$i$$$.We can get:if all $$$XOR(i)$$$ are $$$0$$$,the answer is $$$YES$$$.

Now let’s consider the origin flip. In essence,there are only $$$6$$$ different operations:

• Flip $$$XOR(1),XOR(2),XOR(3)$$$;

• Flip $$$XOR(4),XOR(5),XOR(6)$$$;

• Flip $$$XOR(7),XOR(8),XOR(9)$$$;

• Flip $$$XOR(1),XOR(4),XOR(7)$$$;

• Flip $$$XOR(2),XOR(5),XOR(8)$$$;

• Flip $$$XOR(3),XOR(6),XOR(9)$$$.

Construct a $$$l*l$$$ matrix $$$d$$$,$$$d_{i,j}=XOR((i-1)*l+j)$$$.We find that we can turn it into a classical problem:

https://codeforces.net/problemset/problem/1475/F.

What about $$$x*y$$$ span?