Sort the numbers as $$$a\le b\le c$$$.

After at least one operation, consider the median.

Doing nothing gives $$$c-a$$$; replacing $$$c$$$ with $$$a+b$$$ gives $$$b$$$.

Suppose the current numbers are $$$x\le y\le z$$$. An operation keeps two numbers and replaces the third with their sum. Since all values are nonnegative, the new sum is no smaller than either retained number. Thus the new median is the larger retained number, which is at least the old median $$$y$$$. The median never decreases.

After an operation that retains $$$u\le v$$$, the numbers are $$$u,v,u+v$$$. Their range is exactly $$$v$$$, also their median. Hence every nonempty sequence of operations ends with a range of at least the initial median $$$b$$$.

With no operation the range is $$$c-a$$$. Replacing $$$c$$$ with $$$a+b$$$ produces $$$a,b,a+b$$$, whose range is $$$b$$$. Therefore the answer is $$$\min(c-a,b)$$$.

The time and space complexities are both $$$O(1)$$$.

Cancel the common term in the inequality between two adjacent dominoes.

The condition is equivalent to $$$s_i\ne s_{i+2}$$$ for every $$$i$$$.

Once the first two characters are fixed, the rest are determined.

Adjacent dominoes have different weights exactly when $$$s_i+s_{i+1}\ne s_{i+1}+s_{i+2}$$$.

Canceling $$$s_{i+1}$$$ gives $$$s_i\ne s_{i+2}$$$. Since the alphabet is binary, this is equivalent to $$$s_{i+2}=1-s_i$$$.

Therefore $$$s_1,s_2$$$ determine the whole string. Enumerate their four assignments and check whether the implied string agrees with every known character. The answer is at most $$$4$$$, so the modulus does not affect it.

The time complexity is $$$O(n)$$$ and the space complexity is $$$O(1)$$$.

Split the 1s on the cycle into maximal runs. Unless a run covers the whole cycle, initially only its last potato can move.

Passing too early gives the next opportunity to players of the other team.

The last player of each run waits until the final round. Every initial 10 becomes 01, all other potatoes stay still, and the exact value of $$$k$$$ is irrelevant.

The total score is always the number of potatoes, so the game is zero-sum. Consider a maximal run of 1s followed by an empty position. Every potato except the last one is blocked.

If the last potato is passed early, it reaches the other team and leaves an empty position behind, enabling the preceding potato. Both newly enabled players belong to the other team, so with another round the opponent may cancel the point just gained. Passing in the final round leaves no response and is optimal.

Thus only the last potato of each run moves one step in the final round. If the whole cycle is filled, nothing moves. For an initial position $$$i$$$:

• if $$$s_i=1$$$ and $$$s_{i+1}=0$$$, the team owning $$$i$$$ scores;
• if $$$s_i=s_{i+1}=1$$$, the other team scores.

Scan the cycle once. The implementation is zero-indexed: even positions belong to red and odd positions to blue. Their scores are printed in that order.

The time complexity is $$$O(n)$$$ and the space complexity is $$$O(1)$$$.

Check whether a valid reversal can change either run count or the first character.

In $$$x^ay^bx^c$$$, choosing one endpoint in each $$$x$$$-run lets us redistribute the total length of those two runs.

Operations redistribute run lengths but do not change the order of run colors.

Split the string into maximal runs. The two endpoints of an operation contain the same character. Internal adjacencies are only reversed, and the endpoint character on either boundary stays unchanged. Hence the numbers of 0-runs and 1-runs are invariant, as are the character counts.

If the reversal contains the first position, the new first character is the old right endpoint, equal to the old first character. Otherwise it is untouched. Thus the first character is invariant. Since run colors alternate, the run counts and first character determine their entire order.

Conversely, consider $$$x^ay^bx^c$$$. A reversal with one endpoint in each $$$x$$$-run can split the total $$$a+c$$$ into any two positive lengths while leaving the middle run unchanged. Repeating this between adjacent runs of the same color realizes any positive composition of all 0s, and independently any positive composition of all 1s. These invariants are therefore sufficient.

If character $$$x$$$ occurs $$$cnt_x$$$ times in $$$seg_x$$$ nonempty runs, its run lengths can be chosen in $$$\binom{cnt_x-1}{seg_x-1}$$$ ways. The two colors are independent, so the answer is $$$\binom{cnt_0-1}{seg_0-1}\binom{cnt_1-1}{seg_1-1}$$$.

An absent character contributes a factor of $$$1$$$.

We can precompute inverses without binary exponentiation. Let the prime modulus be $$$P$$$. Since every required $$$i \lt P$$$, its inverse exists. From $$$P=\left\lfloor\frac Pi\right\rfloor i+(P\bmod i)$$$ we obtain $$$i^{-1}=-\left\lfloor\frac Pi\right\rfloor(P\bmod i)^{-1}\pmod P$$$.

Because $$$P\bmod i \lt i$$$, enumerating $$$i$$$ in increasing order computes each inverse from an earlier one. Factorials and inverse factorials follow in the same loop.

Each test case takes $$$O(n)$$$ time. Preprocessing uses $$$O(N)$$$ time and space, where $$$N=10^6$$$.

Let $$$w$$$ be the number of black cells and $$$S_r,S_c$$$ their coordinate sums modulo $$$n$$$. Observe how they change after a shift.

Since $$$\gcd(w,n)=1$$$, $$$(w^{-1}S_r,w^{-1}S_c)$$$ behaves like the center of mass of the picture.

Swapping a black cell $$$p$$$ with a white cell $$$p+\delta$$$ increases the coordinate sum by $$$\delta$$$.

In the first run, move the center to the target. In the second run, recompute it from the transformed picture.

Identify coordinates $$$1,2,\ldots,n$$$ with $$$0,1,\ldots,n-1$$$ in $$$\mathbb Z_n$$$. Let $$$S=(S_r,S_c)$$$ be the sum of black-cell coordinates. A shift by $$$d$$$ changes it to $$$S+wd$$$. Define $$$C=w^{-1}S$$$. Then $$$C$$$ changes to $$$C+d$$$, exactly as an ordinary cell does.

Every rotation or reflection is an affine map $$$p\mapsto Mp+t$$$. It changes the sum to $$$MS+wt$$$ and therefore changes the center to $$$MC+t$$$, again exactly like a cell.

After color inversion, $$$w'=n^2-w\equiv-w\pmod n$$$. The coordinate sum of the whole board is $$$0$$$ modulo $$$n$$$, so the new black-cell sum is $$$S'=-S$$$. Hence the new center is $$$(-w)^{-1}(-S)=C$$$. Color inversion does not affect it.

In the first run, we want the sum after swapping to be $$$wx$$$. Let $$$\delta=wx-S$$$. If $$$\delta=0$$$, swap one cell with itself. Otherwise find a black cell $$$p$$$ for which $$$p+\delta$$$ is white and swap them.

Such a cell must exist. Otherwise the black-cell set would be invariant under translation by nonzero $$$\delta$$$. Every orbit of this translation has length $$$L \gt 1$$$ with $$$L\mid n$$$. The black cells would be a union of complete orbits, so $$$L\mid w$$$, contradicting $$$\gcd(w,n)=1$$$.

The swap makes the center equal to the target. All later transformations move them together. In the second run, recompute $$$w,S_r,S_c$$$ and output $$$w^{-1}S$$$. Since $$$n\le800$$$, enumerate $$$1\le t \lt n$$$ until $$$wt\equiv1\pmod n$$$; no extended Euclidean algorithm is needed.

Each run takes $$$O(n^2)$$$ time and $$$O(n^2)$$$ space.

Fix the chosen index in every second and work backward from the final zero array. A current upper bound $$$x$$$ becomes either $$$2x+1$$$ or $$$2x$$$ after one backward step.

If index $$$i$$$ is selected in the seconds in $$$S$$$, it can end at zero after $$$T$$$ seconds exactly when $$$a_i\le\sum_{s\in S}2^{s-1}$$$.

For fixed $$$T$$$, distribute $$$1,2,4,\ldots,2^{T-1}$$$ among the demands. Process them in decreasing order and always choose the largest remaining demand.

Fix all choices during the $$$T$$$ seconds and consider position $$$i$$$. Working backward, if values at most $$$x$$$ can already reach zero, then a preceding selected step allows $$$y$$$ exactly when $$$\lfloor y/2\rfloor\le x$$$, or $$$y\le2x+1$$$. A nonselected step gives $$$\lceil y/2\rceil\le x$$$, or $$$y\le2x$$$. Repeating this proves the condition in Hint 2.

Thus feasibility in $$$T$$$ seconds is equivalent to assigning every capacity $$$1,2,\ldots,2^{T-1}$$$ to one demand so that demand $$$a_i$$$ receives total capacity at least $$$a_i$$$.

Process capacities from largest to smallest. Let the current capacity be $$$p$$$ and the largest remaining demand be $$$x$$$. If $$$x \gt p$$$, all smaller capacities sum to only $$$p-1$$$, so every feasible assignment must give $$$p$$$ to $$$x$$$. If $$$x\le p$$$, let $$$p$$$ finish $$$x$$$. In any feasible assignment giving $$$p$$$ to some $$$y\le x$$$ and a set of smaller capacities to $$$x$$$, swapping those two assignments remains feasible. Hence the greedy rule is correct.

Every positive number must be selected at least once, since repeated ceiling division alone never reaches zero. Thus $$$T\ge n$$$. Also $$$a_i \lt 2^{30}$$$, so $$$T=n+30$$$ is always sufficient. Binary-search $$$T$$$ in this interval.

Every capacity at least $$$2^{30}$$$ can finish one demand alone. Remove the largest $$$T-30$$$ demands with these capacities. At most $$$30$$$ demands remain; put them in a max-heap and simulate only $$$2^{29},\ldots,1$$$.

Sorting takes $$$O(n\log n)$$$. Each check takes $$$O(30\log30)$$$, there are $$$O(\log30)$$$ checks, and the space complexity is $$$O(n)$$$.

For each position, its values over all versions form a sequence. Maintain its sum, maximum prefix, maximum suffix, and maximum subarray when appending a segment.

A value is always in $$${-1,0,1}$$$. For each possible initial value, a sequence of operations can store its final value and the summary of the generated history.

This representation is closed under concatenating operation sequences, so it can serve as a lazy segment-tree tag.

Range updates only compose tags. A position's history is materialized when that position is queried by pushing its root-to-leaf tags.

For a nonempty sequence segment, store $$$(S,P,Q,M)$$$: its sum, maximum prefix sum, maximum suffix sum, and maximum nonempty subarray sum. Two adjacent summaries merge in $$$O(1)$$$; a crossing maximum subarray is the left maximum suffix followed by the right maximum prefix.

Fix one array position. Its value lies in $$$V={-1,0,1}$$$. For an operation segment $$$T$$$, let $$$f_T(s)$$$ be the final value from initial state $$$s$$$, and let $$$H_T(s)$$$ summarize the values recorded while executing $$$T$$$. There are only three states, so this representation has constant size.

If $$$A$$$ is followed by $$$B$$$, then $$$f_{AB}(s)=f_B(f_A(s))$$$ and $$$H_{AB}(s)=H_A(s)\mathbin{\Vert}H_B(f_A(s))$$$, where $$$\Vert$$$ concatenates two histories and merges their summaries. Tags therefore compose in $$$O(1)$$$.

Each segment-tree node stores the unpushed operation segment applying to its whole interval. A range update composes tags in $$$O(\log n)$$$ nodes. After each operation, a record-current-value event is applied to the whole tree to create the new version.

A query at $$$p$$$ pushes the tags on its root-to-leaf path and materializes all history since the previous query. If the old history has maximum suffix $$$Q_0$$$ and maximum subarray $$$M_0$$$, while the new segment has $$$(S,P,Q,M)$$$, then $$$M'=\max(M_0,M,Q_0+P)$$$ and $$$Q'=\max(Q,Q_0+S)$$$.

Only these two old values need to persist at each position.

Record version $$$0$$$ initially. A type-4 operation at time $$$i$$$ queries versions $$$0$$$ through $$$i-1$$$, so answer it before recording version $$$i$$$, which equals version $$$i-1$$$. Other operations update first and record afterward. Decode online input modulo $$$2^{64}$$$ exactly as specified.

The total time complexity is $$$O((n+q)\log n)$$$ and the space complexity is $$$O(n)$$$.

The segment tree and historical maximum-subarray framework are unchanged from G1. Only the constant-size operation tag changes.

Before the first assignment, after fixing the sign of the initial $$$x$$$, every value is one of $$$-|x|,0,|x|$$$.

The first assignment removes all dependence on $$$x$$$. Split a tag into a coefficient prefix depending on $$$|x|$$$ and a fixed numeric suffix.

To compose $$$A$$$ followed by $$$B$$$, distinguish whether an assignment has occurred in either segment.

Solution 1

Without assignments, negation changes only the sign and $$$\max(x,0)$$$ only replaces a negative value with zero. For each of the three initial signs, store the summary of the coefficient sequence and the final coefficient in $$${-1,0,1}$$$. Substituting the real input multiplies the sequence by $$$|x|$$$.

The first assignment is a dividing point. Before it, values still depend on $$$x$$$; from it onward, they are fixed. Represent an operation segment by:

• a coefficient prefix depending on $$$|x|$$$, stored for all three initial signs;
• a fixed numeric suffix and the final actual value.

This representation has constant size. It is also closed under concatenation.

If $$$A$$$ contains an assignment, its output is constant. Feeding that constant into $$$B$$$ fixes all history produced by $$$B$$$, so concatenate the fixed histories.

If neither segment contains an assignment, compose their three coefficient states exactly as in G1.

If only $$$B$$$ contains an assignment, append the part of $$$B$$$ before its first assignment to each coefficient prefix of $$$A$$$. The fixed suffix of $$$B$$$ becomes the fixed suffix of the result. Every case takes $$$O(1)$$$.

Assignment, negation, $$$\max(x,0)$$$, and recording a version all have direct tags of this form. The remaining segment-tree logic and version ordering are identical to G1.

The total time complexity is $$$O((n+q)\log n)$$$ and the space complexity is $$$O(n)$$$.

Solution 2

There is also an amortized solution that performs operation $$$3$$$ directly on the segment tree. Store the current minimum $$$mn$$$ and maximum $$$mx$$$ in every node. Range assignment and range negation use ordinary lazy tags. For operation $$$3$$$:

• if $$$mn\ge0$$$, do nothing;
• if $$$mx\le0$$$, assign zero to the whole node;
• otherwise the node contains both positive and negative values, so recurse into its children.

Thus operation $$$3$$$ never has to appear in a historical tag. It is materialized as several range assignments to zero.

Call a segment-tree node bad if $$$mn \lt 0 \lt mx$$$.

Let the potential $$$\Phi$$$ be the number of bad nodes. When a fully covered node is negated, $$$(mn,mx)$$$ becomes $$$(-mx,-mn)$$$, so the bad status of that node and every node below it is preserved. Assignment can only remove bad nodes. A range assignment or negation recomputes nodes only on its two boundary paths, so it creates at most $$$O(\log n)$$$ new bad nodes.

Now consider operation $$$3$$$. Apart from $$$O(\log n)$$$ nodes on the two boundary paths, every internal node into which the recursion continues was bad before the operation. After the operation, its interval contains no negative value, so that bad node has disappeared. A recursion tree has at most one more terminal node than internal nodes. Hence one operation costs $$$O(\log n+D)$$$, where $$$D$$$ is the number of bad nodes destroyed by this operation. Operation $$$3$$$ creates no bad nodes. The initial potential is $$$O(n)$$$, while all other operations increase it by only $$$O(q\log n)$$$ in total. Therefore all operation-3 recursions take $$$O(n+q\log n)$$$ time altogether.

The historical part still uses the four-value sequence summary from G1. After every operation, append one record-current-value event at the root. Since every clamp has already been materialized as assignment to zero, pending historical actions contain only assignment, negation, and recording.

Before the first assignment, an initial value $$$x$$$ can only become $$$x$$$ or $$$-x$$$. It is therefore enough to keep two initial states, negative and nonnegative, storing the generated coefficient-sequence summary and the final sign. After the first assignment, all later values are independent of the initial input, so keep a fixed numeric suffix and the final value. Two such tags still compose in $$$O(1)$$$ in chronological order.

For a query at $$$p$$$, push all tags on the root-to-leaf path and append the new history summary to the already materialized history of that position. Version $$$0$$$ and type-4 recording are handled in the same order as in Solution 1.

The total time complexity is $$$O(n+q\log n)$$$ and the space complexity is $$$O(n)$$$.

View each factor $$$a_u+a_v$$$ as choosing one endpoint of edge $$$(u,v)$$$. Every exponent is $$$0$$$, $$$1$$$, or $$$2$$$. The numbers of vertices with exponents $$$0$$$ and $$$2$$$ are equal, and these two types alternate after all other vertices are removed.

The coefficient of a monomial type depends only on the number of variables appearing twice. Express the answer using $$$e_re_{n-r}$$$, where $$$e_r$$$ is the $$$r$$$-th elementary symmetric polynomial.

Coefficient comparison gives a linear system that can be eliminated from high indices to low indices. Direct elimination is $$$O(n^2)$$$; use the ratio of adjacent $$$c_k$$$ and Pascal's identity to derive a short recurrence.

Adjacent equations give a second-order recurrence in $$$h_r,h_{r+1},h_{r+2}$$$. All $$$e_r$$$ are coefficients of $$$\prod_{i=1}^n(1+a_ix)$$$ and can be computed by divide-and-conquer NTT.

Expand the weight of one cyclic ordering. Choosing one term from $$$a_u+a_v$$$ is equivalent to orienting edge $$$(u,v)$$$ toward the chosen endpoint.

Every vertex has degree two, so its exponent is $$$0$$$, $$$1$$$, or $$$2$$$. The exponent sum is $$$n$$$, hence the numbers of vertices with exponents $$$0$$$ and $$$2$$$ are equal; call both numbers $$$k$$$.

Fix these two sets. An exponent-0 vertex has both edges directed outward, an exponent-2 vertex has both directed inward, and every ordinary vertex has one edge in and one out. After ordinary vertices are removed, the two special types must alternate. Conversely, alternation uniquely determines the orientations of all paths between them.

For $$$k\ge1$$$, the $$$2k$$$ special vertices have $$$(2k-1)!$$$ relative cyclic orders. Fix one exponent-0 vertex as the start. The exponent-2 vertices can be permuted arbitrarily, as can the remaining exponent-0 vertices, giving $$$k!(k-1)!$$$ alternating orders. Inserting the other $$$n-2k$$$ vertices does not change this ratio. Therefore the coefficient of this monomial type over all cyclic orders is

For $$$k=0$$$, every vertex has one edge in and one out. The whole cycle must be consistently clockwise or counterclockwise, so

Now consider a symmetric-polynomial representation. Let $$$e_r$$$ be defined by

In $$$e_re_{n-r}$$$, fix a monomial with $$$k$$$ variables appearing twice and $$$k$$$ absent. Repeated variables must be chosen from both factors and absent variables from neither. Choose $$$r-k$$$ of the remaining $$$n-2k$$$ variables for the first factor, so its coefficient is

Let $$$m=\lfloor n/2\rfloor$$$ and write the answer as

Comparing each monomial type gives

Equation $$$k$$$ contains only $$$h_k,h_{k+1},\ldots,h_m$$$, with coefficient $$$1$$$ on $$$h_k$$$. Thus the variables can be solved from large indices to small indices, but doing so directly takes $$$O(n^2)$$$.

For $$$k\ge1$$$, divide two adjacent coefficients:

The $$$k=0$$$ case follows directly from $$$c_0,c_1$$$. Hence

Define

Fix $$$k$$$, set $$$N=n-2k$$$ and $$$j=r-k$$$, and let $$$A_t=\binom{N-2}{t}$$$, with out-of-range binomial coefficients equal to zero.

Using Pascal's identity twice,

Now use

together with $$$r=k+j$$$ and $$$n=N+2k$$$. The entire coefficient calculation can be displayed as

Substituting into $$$L_k$$$ and shifting the latter two indices gives

where out-of-range $$$h$$$ values are zero. Define

Then

Equation $$$k$$$ contains only $$$E_k,E_{k+1},\ldots,E_m$$$, with coefficient $$$1$$$ on $$$E_k$$$. Apart from the top boundary, backward elimination gives $$$E_r=0$$$, or

The highest two terms come directly from the original system:

If $$$n=2m+1$$$ is odd, these values satisfy $$$E_{m-1}=-E_m$$$. Their binomial coefficients in every sum are equal, so they cancel. The remaining equations give $$$E_{m-2},E_{m-3},\ldots,E_0=0$$$. Apply the second-order recurrence starting from $$$m-2$$$.

If $$$n=2m$$$ is even, the first two values give $$$E_{m-1}=0$$$, but $$$E_m$$$ has no matching boundary term. Compute one more value from the original system:

It satisfies $$$E_{m-2}=-E_m$$$. Again their coefficients are equal and they cancel, giving $$$E_{m-3},E_{m-4},\ldots,E_0=0$$$. Apply the recurrence starting from $$$m-3$$$.

Finally compute all $$$e_r$$$ by multiplying the $$$n$$$ linear polynomials $$$1+a_ix$$$ with divide and conquer, using NTT for every convolution. Substitute the resulting coefficients into $$$\sum_{r=0}^m h_re_re_{n-r}$$$.

The time complexity is $$$O(n\log^2 n)$$$ and the space complexity is $$$O(n\log n)$$$.

From the statement we can conclude that a class can be slept through $$$\textbf{if and only if}$$$:

1. The class itself is not an important class.
2. The class is not within $$$k$$$ classes after any important class.

Here's an $$$O(nk)$$$ approach:

We directly simulate the process: for each important class at position $$$i$$$, mark positions $$$i+1, i+2, \dots, \min(i+k, n)$$$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $$$O(nk)$$$ solution is acceptable under the constraints.

There's also an $$$O(n)$$$ solution:

For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $$$last$$$ storing the index of the most recent important class (or $$$-\infty$$$ if none seen yet), then for each $$$i$$$ from $$$1$$$ to $$$n$$$, if it's an important class we let $$$last = i$$$, otherwise if $$$last + k \lt i$$$, the class is able to be slept through and we add $$$1$$$ to the answer.

#include<bits/stdc++.h>
using namespace std;
int n,k;string s;
void solve(){
	cin>>n>>k>>s;
	int ans=0;
	for(int i=0;i<n;i++){
		if(s[i]=='0'){
			int ok=1;
			for(int j=max(0,(int)i-k);j<i;j++){
				if(s[j]=='1'){
					ok=0;
					break;
				}
			}
			ans+=ok;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	for(;T--;)solve();
	return 0;
}

Consider a simple greedy algorithm: For each turn, choose the option that gives the higher immediate score. That is, if our current score is $$$k$$$, it becomes $$$\max(k - a_i, b_i - k)$$$ after this turn. Why doesn't the algorithm work?

Try to improve the algorithm in Hint 1.

The greedy approach in Hint 1 fails because it assumes that if we know the maximum possible score after turn $$$i$$$ (denoted by $$$max_i$$$), we can determine $$$max_{i + 1}$$$ from it. However, this assumption is wrong and here is a counterexample:

$$$a = [2, 0], b = [1, 0]$$$

Here $$$max_1 = 1$$$ and $$$max_2 = 2$$$. The greedy approach takes the blue card in turn $$$1$$$. But to reach $$$max_2$$$, we must choose the red card in turn $$$1$$$, which turns our score into $$$-2$$$, and then choose the blue card in turn $$$2$$$. So in this example, $$$max_1$$$ does not give $$$max_2$$$.

We see that $$$max_1$$$ does not help us find $$$max_2$$$ if we choose the blue card in the second turn. The reason is, if we want to maximize our score when choosing a blue card, we want our current score to be as small as possible, so we are looking for the minimum possible score. To maximize $$$b_i - k$$$ we should minimize $$$k$$$.

From this we can see that if we have both the maximum possible score $$$max_{i - 1}$$$ and the minimum possible score $$$min_{i - 1}$$$ after turn $$$i - 1$$$, we can determine $$$max_{i} = \max(max_{i - 1} - a_i, b_i - min_{i - 1})$$$, because these two expressions cover the best outcomes from the red and blue options respectively. Similarly, the new minimum $$$min_{i} = \min(min_{i - 1} - a_i, b_i - max_{i - 1})$$$ comes from either taking the red card from the previous minimum, or the blue card from the previous maximum. And from $$$max_{i}, min_{i}$$$ we can move forward to $$$max_{i + 1}, min_{i + 1}$$$ and so on.

Thus, we start with $$$max_0 = min_0 = 0$$$ and calculate each $$$max_i, min_i$$$ throughout the process using the formulas above. The answer is $$$max_n$$$. This runs in $$$O(n)$$$ time complexity.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1e5 + 10;

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

int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];
        ll mx = 0, mn = 0;
        for (int i = 1; i <= n; ++i) {
            ll new_mx = max(mx - a[i], b[i] - mn);
            ll new_mn = min(mn - a[i], b[i] - mx);
            mx = new_mx, mn = new_mn;
        }
        cout << mx << endl;
    }
    return 0;
}

Consider the cases $$$n = 1$$$ and $$$n = 2$$$. What do you observe?

Try to determine the "first" element that must belong to $$$B$$$.

Assume the minimum element in $$$A$$$ is $$$x$$$. We now prove that $$$x$$$ must be included in $$$B$$$.

There are no elements smaller than $$$x$$$, which means $$$x$$$ has no proper divisor (other than $$$x$$$ itself) inside $$$A$$$. If we do not put $$$x$$$ into $$$B$$$, then the second rule would be violated.

Thus we can determine the first element of $$$B$$$, and then check whether all its multiples $$$\le k$$$ are contained in $$$A$$$. We mark these multiples as "finished".

Now think greedily. We never need to process elements that are already marked "finished". Each time, we just find the smallest unfinished element in $$$A$$$, check it, and add it to $$$B$$$ if possible.

A loose upper bound on the running time is $$$O\bigl(n d(n) \log n\bigr)$$$, where $$$d(n)$$$ is the divisor function. However, this bound is rarely attained in practice: many operations are skipped thanks to the "finished" marks, so the algorithm runs much faster than this worst-case estimate.

#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
set<int>s;
map<int,int>u;
int n,a[mxn],k;
void solve(){
	s.clear(),u.clear();
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i],s.insert(a[i]),u[a[i]]=1;
	vector<int>ans;ans.clear();
	while(s.size()){
		int t=*s.begin();
		ans.push_back(t);
		s.erase(s.begin());
		for(int cur=t;cur<=k;cur+=t){
			if(!u[cur]){
				cout<<"-1\n";
				return;
			}
			auto t=s.find(cur);
			if(t!=s.end())s.erase(t);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans)cout<<i<<' ';cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	for(;T--;)solve();
	return 0;
}

What is the answer when $$$k \geq 32$$$?

We can use dynamic programming to solve it.

When $$$k \geq 32$$$, we can, at each step, add the smallest $$$t$$$ such that adding $$$2^{t}$$$ to the current $$$n$$$ produces a carry. After $$$k$$$ such steps, $$$n$$$ will become a power of $$$2$$$, and the answer will be $$$\operatorname{popcount}(n) + k - 1$$$.

Now we observe that the total number of carries in the end is $$$\operatorname{popcount}(n) + k - \operatorname{popcount}(n')$$$, where $$$n'$$$ is the final value of $$$n$$$ after all operations. To maximize this quantity, we want to minimize the final $$$\operatorname{popcount}(n')$$$.

To this end, let $$$dp[i][j][c]$$$ denote the optimal value we can obtain after processing the $$$i$$$ least significant bits, having used $$$j$$$ operations in total, where $$$c \in {0,1}$$$ indicates whether there is a carry from the $$$(i-1)$$$-th bit.

For the $$$i$$$-th least significant bit, we have two options: either select this bit (i.e., use one operation on this bit) or not select it.

Let $$$n_i$$$ be the $$$i$$$-th bit of the original $$$n$$$, and let $$$t_i$$$ be the sum at this bit after adding everything in. If we select this bit, then $$$t_i = 1 + c + n_i$$$; otherwise, $$$t_i = c + n_i$$$. From $$$t_i$$$, we can determine whether this bit produces a carry to the next position (the next carry is $$$c' = \lfloor t_i / 2 \rfloor$$$) and whether the $$$i$$$-th bit of $$$n'$$$ is $$$1$$$ or $$$0$$$ (the resulting bit is $$$t_i \bmod 2$$$), which allows us to perform the DP transition.

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

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
const int mxb=64,mxk=32;
int dp[mxb+2][mxk+2][2];
void Min(int&x,int y){x=min(x,y);}
void solve(){
	int n,k;cin>>n>>k;
	int pc=__builtin_popcount(n);
	if(n==0){
		cout<<max(0ll,k-1)<<'\n';
		return;
	}
	if(k>=32){
		cout<<k+pc-1<<'\n';
		return;
	}
	for(int i=0;i<=mxb;i++)for(int j=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;
	dp[0][0][0]=0;
	for(int i=0;i<mxb;i++){
		int ni=(n>>i)&1ll;
		for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
			int cur=dp[i][u][c];
			if(cur>=inf)continue;
			{
				int sum=ni+c,bit=sum&1,nc=sum>>1;
				Min(dp[i+1][u][nc],cur+bit);		
			}
			if(u+1<=k){
				int sum=ni+1+c,bit=sum&1,nc=sum>>1;
				Min(dp[i+1][u+1][nc],cur+bit);
			}
		}
	}
	int bst=inf;
	for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
		int val=dp[mxb][u][c];
		if(val<inf)Min(bst,val+c);
	}
	int ans=k+pc-bst;
	cout<<ans<<'\n';
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	for(;T--;)solve();
	return 0;
}

$$$\lfloor 2.5n\rfloor$$$ is the expected number of operations. We add $$$800$$$ more to ensure that every correct solution would pass.

Think about how to solve it within $$$3n$$$, and how can we improve that.

We split the process into two phases. In the first phase, we make every pair $$$x$$$ and $$$n - x + 1$$$ symmetric; in the second phase, we turn the permutation into $$$1, 2, \dots, n$$$.

Let $$$pos[x]$$$ be the current position of $$$x$$$. We iterate $$$x$$$ from $$$1$$$ to $$$n$$$ in increasing order. If $$$pos[x] + pos[n + 1 - x] \neq n + 1$$$, then $$$x$$$ and $$$n + 1 - x$$$ are not symmetric. In this case, we query $$$(pos[x],\, n - pos[n + 1 - x] + 1)$$$. No matter whether the interactive judge mirrors the array and then swaps or not, this operation will always make $$$x$$$ and $$$n + 1 - x$$$ symmetric. When $$$n$$$ is odd, we should first move $$$(n+1)/2$$$ to the middle.

Next, we move these groups to their correct target positions in order. Suppose the target positions of a pair are $$$i$$$ and $$$n - i + 1$$$, while it is currently at $$$j$$$ and $$$n - j + 1$$$. We query $$$(i, j)$$$; this will surely place either the pair itself or its mirror into the correct positions.

Now we compute the expectation. Let $$$T$$$ be the expected number of queries spent in this second phase for a single group. After we query once, with probability $$$1/2$$$ the group is already correctly placed and we are done after $$$1$$$ query; with probability $$$1/2$$$ it is mirrored into another group’s target positions, in which case we have spent $$$1$$$ query and still expect $$$T$$$ more. Thus $$$T = 1 + \frac{1}{2} \cdot 1 + \frac{1}{2}(T + 1)$$$, which solves to $$$T = 4$$$.

There are $$$n/2$$$ groups, so this phase needs $$$2n$$$ queries in expectation. The first phase uses exactly $$$n/2$$$ queries (one per group), so the total expected number of queries is $$$5n/2$$$.

#include<bits/stdc++.h>
using namespace std;
const int mxn=40004;
int n,a[mxn],pos[mxn];
int mirror(int x){
	return n-x+1;
}
pair<int,int>ask(int x,int y){
	cout<<"? "<<x<<' '<<y<<endl;
	fflush(stdout);
	int u,v;cin>>u>>v;
	return {u,v};
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[a[i]]=i;
	}
	if(n%2==1){
		int mid=(n+1)/2;
		while(pos[mid]!=mid){
			auto p=ask(mid,pos[mid]);
			int u=p.first,v=p.second;
			swap(a[u],a[v]);
			pos[a[u]]=u,pos[a[v]]=v;
		}
	}
	for(int i=1;i<=n/2;i++){
		int x=pos[i],y=pos[mirror(i)];
		if(x+y!=n+1){//not mirror
			auto p=ask(x,mirror(y));
			int u=p.first,v=p.second;
			swap(a[u],a[v]);
			pos[a[u]]=u,pos[a[v]]=v;
		}
	}
	for(int i=1;i<=n/2;i++){
		while(pos[i]!=i or pos[mirror(i)]!=mirror(i)){
			if(pos[i]!=i){
				auto p=ask(i,pos[i]);
				int u=p.first,v=p.second;
				swap(a[u],a[v]);
				pos[a[u]]=u,pos[a[v]]=v;				
			}else{
				auto p=ask(mirror(i),pos[mirror(i)]);
				int u=p.first,v=p.second;
				swap(a[u],a[v]);
				pos[a[u]]=u,pos[a[v]]=v;	
			}
		}
	}
	cout<<"!"<<endl;
	fflush(stdout);
}
int main(){
	int T=1;
	cin>>T;
	for(;T--;)solve();
	return 0;
}

Consider the process. First note that, because the array $$$a$$$ is non-increasing, the length of each segment whose sum first reaches $$$\ge x$$$ and is then cleared is nondecreasing.

We use the square-root decomposition idea. We fix a threshold $$$B$$$ that separates “short” segments from “long” ones. For segments of length at most $$$B$$$, we handle them using precomputed data; for segments of length greater than $$$B$$$, we use a slower direct procedure.

Since there are at most $$$q$$$ distinct values of $$$x$$$, we can first collect all queries offline and discretize these values. Then we build a table $$$\text{f[i][len]}$$$ that records the rightmost starting position of a segment of length $$$\text{len}$$$ whose sum is at least the $$$i$$$-th largest value of $$$x$$$.

When answering a query, we simply enumerate $$$\text{len} = 1, 2, \dots, B$$$ and, starting from the current left endpoint, quickly skip over and process all segments of length $$$\text{len}$$$. The time complexity for this part is $$$O(B)$$$ per query.

For segments of length $$$ \gt B$$$, we directly binary search the ending position of each such segment. Since every such segment has length at least $$$B$$$, we make at most $$$n/B$$$ jumps, so this part runs in $$$O\bigl((n/B)\log n\bigr)$$$ time.

If we choose $$$B = \sqrt{n\log n}$$$, the two parts balance and the total time complexity becomes $$$O\bigl(n\sqrt{n\log n}\bigr)$$$.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2e5+5;
const int B=512;
int T,f[B+3][mxn],n,a[mxn],q;
ll sum[mxn],N=1000000001;
int l_[mxn],r_[mxn],x_[mxn];
int id[mxn];
void solve(){
	cin>>n>>q;
	vector<int>v;v.clear();
	for(int i=1;i<=n;i++)
		cin>>a[i],
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=q;i++)
		cin>>l_[i]>>r_[i]>>x_[i],
		v.push_back(x_[i]);
	v.push_back(0);
	v.push_back(1000000008);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=q;i++)
		id[i]=lower_bound(v.begin(),v.end(),x_[i])-v.begin();
	for(int i=1;i<=B;i++){
		int k=0;
		for(int j=n-i;j>=0;j--)
			for(;v[k]<=min(sum[j+i]-sum[j],N);k++)
				f[i][k]=j+1;
	}
	for(int t=1;t<=q;t++){
		int l,r,x,cnt=0;
		l=l_[t],r=r_[t],x=x_[t];
		for(int i=1;i<=B;i++)
			if(f[i][id[t]]>=l){
				int w=min(r-l+1,f[i][id[t]]-l+i)/i;
				cnt+=w;
				l+=w*i;
			}l--;
		while(1){
			if(sum[r]-sum[l]<x){
				cout<<cnt<<' '<<sum[r]-sum[l]<<'\n';
				break;
			}cnt++;
			int t=x,lo=l-1,hi=n+1,md;
			ll req=sum[l]+t;
			for(;lo<hi-1;){
				md=lo+hi>>1;
				if(sum[md]<req)lo=md;
				else hi=md;
			}
			l=hi;
		}
	}
	for(int i=0;i<max(n,(int)v.size())+3;i++)sum[i]=0;
	for(int j=0;j<B+3;j++)for(int i=0;i<max(n,(int)v.size())+3;i++)f[j][i]=0;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	T=1;cin>>T;
	while(T--)solve();
	return 0;
}

There exists an $$$O(n\sqrt{n})$$$ solution.

We can notice that when $$$n$$$ is even, it can only generate an even number: the sum of the first half is exactly the same as the second half. However, when $$$n$$$ is odd, we can generate any number by placing $$$n-k+1$$$ in the middle and $$$1$$$ in other positions.

We can prove that the final cost of the number must be 1, and it is between 1 and 9 (possibly with leading zeros). We don't need to remove the leading zeros.

So, which position should we reserve? Greedily, we should reserve as many leading zeros as possible. Therefore, we can reserve the last non-zero position and the zeros before it.

When $$$y \gt 1$$$ and $$$x \neq 1$$$, the number can be divided by $$$x$$$.

Consider dividing the current grid into 4 areas. In which area does our position lie?

Try to solve this problem using recursion.

Stop learning useless algorithms, go solve some problems, and learn how to use binary search.

How do we check whether the mex of a subarray is greater than $$$x$$$? When all the numbers from $$$0$$$ to $$$x-1$$$ have appeared in it.

Greedily split the array.

When should we output -1?

When the array is full (though this may not be entirely correct), we can replace one position with a blank, then fill it with the correct word.

Initially, when the array is completely blank, we choose a neural network. We will need to perform $$$n$$$ operations to fill all the correct words into the array in the worst case.

Consider hint 1. Which neural network should we choose first?

This is a classic problem.If you don't know how to solve it, you should learn about Trie.