My code is a bit crooked, as my left child has a larger index, but let it be. (And this is the first time in my life that I regretted this).

#include "bits/stdc++.h"
 
using namespace std;
 
const int inf = 1e9 + 228;
 
struct SegTree {
    struct mx2node {
        pair<int, int> mx1 = {-inf, 0};
        pair<int, int> mx2 = {-inf, 0};
 
        mx2node() = default;
 
        void add(mx2node other) {
            if (other.mx1.first > mx1.first) {
                mx2 = mx1;
                mx1 = other.mx1;
            } else if (other.mx1.first == mx1.first) {
                mx1.second += other.mx1.second;
            } else if (other.mx1.first == mx2.first) {
                mx2.second += other.mx1.second;
            } else if (other.mx1.first > mx2.first) {
                mx2 = other.mx1;
            }
 
            if (other.mx2.first == mx2.first) {
                mx2.second += other.mx2.second;
            } else if (other.mx2.first > mx2.first) {
                mx2 = other.mx2;
            }
        }
    };
 
    struct node {
        int v;
        int l, r;
        int nxtl, nxtr;
        int ind_level;
        bool is_leaf;
 
        mx2node value;
        pair<int, long long> ans = {-inf, 0};
 
        node() = default;
    };
 
    static pair<int, long long> merge(pair<int, long long> a, pair<int, long long> b) {
        if (a.first == b.first) {
            return {a.first, a.second + b.second};
        }
        return max(a, b);
    }
 
    int n, k;
    vector<node> t;
    vector<vector<int>> lvl;
    vector<pair<int, int>> seg;
 
    void build_first(int v, int l, int r, int h) {
        if (lvl.size() == h) {
            lvl.emplace_back();
        }
        t[v].v = v;
        t[v].l = l, t[v].r = r;
        lvl[h].push_back(v);
        if (r - l == 1) {
            t[v].is_leaf = true;
            t[v].value = mx2node();
            t[v].ans = {-inf, 0};
            return;
        }
 
        int m = (l + r) / 2;
        build_first(v * 2 + 1, l, m, h + 1);
        build_first(v * 2, m, r, h + 1);
        t[v].is_leaf = false;
    }
 
    void calc_next(int h) {
        // v_r - v_l <= k
        int it = 0;
        auto cur = lvl[h];
        int sz = cur.size();
        for (int j = 0; j < sz; ++j) {
            auto i = cur[j];
            while (it + 1 < sz && max(abs(t[i].r - t[cur[it + 1]].l), abs(t[i].l - t[cur[it + 1]].r)) <= k) {
                ++it;
            }
            t[i].nxtr = -1;
            t[i].ind_level = j;
            if (max(abs(t[i].r - t[cur[it]].l), abs(t[i].l - t[cur[it]].r)) <= k && t[i].v != cur[it] && t[i].l != t[cur[it]].r) {
                t[i].nxtr = cur[it];
            }
        }
        it = sz - 1;
        for (int i = sz - 1; i >= 0; --i) {
            while (it - 1 >= 0 && max(abs(t[cur[i]].r - t[cur[it - 1]].l), abs(t[cur[i]].l - t[cur[it - 1]].r)) <= k) {
                --it;
            }
            t[cur[i]].nxtl = -1;
            if (max(abs(t[cur[i]].r - t[cur[it]].l), abs(t[cur[i]].l - t[cur[it]].r)) <= k && t[cur[i]].v != cur[it] && t[cur[it]].r != t[cur[it]].l) {
                t[cur[i]].nxtl = cur[it];
            }
        }
    }
 
    bool valid(const node &v, const node &u) {
        if (v.v == 1) {
            return true;
        }
        const node &a = t[v.v / 2];
        const node &b = t[u.v / 2];
        if (max(abs(b.r - a.l), abs(b.l - a.r)) <= k)
            return false;
        return true;
    }
 
    pair<int, long long> merge(const node &v, const node &u) {
        if (!valid(v, u))
            return {-inf, 0};
        if (v.v == u.v) {
            if (v.value.mx1.second > 1) {
                return {2 * v.value.mx1.first, 1ll * v.value.mx1.second * (v.value.mx1.second - 1) / 2};
            }
            return {v.value.mx1.first + v.value.mx2.first, 1ll * v.value.mx1.second * v.value.mx2.second};
        } else {
            return {v.value.mx1.first + u.value.mx1.first, 1ll * v.value.mx1.second * u.value.mx1.second};
        }
    }
 
    void update_node(node &v, int h, int first_run = 1) {
        if (!v.is_leaf) {
            v.value = mx2node();
            v.value.add(t[v.v * 2 + 1].value);
            v.value.add(t[v.v * 2].value);
        }
 
        pair<int, long long> ans = {-inf, 0};
 
        if (v.nxtr != -1) {
            ans = merge(ans, merge(v, t[v.nxtr]));
            if (t[v.nxtr].ind_level - 1 >= 0) {
                int nxt = lvl[h][t[v.nxtr].ind_level - 1];
                if (nxt != v.v) {
                    ans = merge(ans, merge(v, t[nxt]));
                }
            }
        }
        if (first_run) {
            if (v.nxtl != -1) {
                update_node(t[v.nxtl], h, false);
                if (t[v.nxtl].ind_level + 1 < (int) lvl[h].size()) {
                    int nxt = lvl[h][t[v.nxtl].ind_level + 1];
                    if (nxt != v.v) {
                        update_node(t[nxt], h, false);
                    }
                }
            }
        }
 
        if (v.r - v.l <= k) {
            ans = merge(ans, merge(v, v));
        }
 
        v.ans = ans;
        if (!v.is_leaf) {
            v.ans = merge(v.ans, t[v.v * 2 + 1].ans);
            v.ans = merge(v.ans, t[v.v * 2].ans);
        }
        if (!first_run && v.v != 1) {
            update_node(t[v.v / 2], h - 1, false);
        }
    }
 
    void update(int v, int l, int r, int pos, int value, int h = 0) {
        if (r - l == 1) {
            t[v].value = mx2node();
            t[v].value.mx1 = {value, 1};
            update_node(t[v], h);
            return;
        }
 
        int m = (l + r) / 2;
        if (pos < m) {
            update(v * 2 + 1, l, m, pos, value, h + 1);
        } else {
            update(v * 2, m, r, pos, value, h + 1);
        }
        update_node(t[v], h);
    }
 
    void update(int pos, int value) {
        update(1, 0, n, pos, value, 0);
    }
 
    SegTree(int _n, int k) : k(k) {
        int sz = 1;
        while (sz < _n) {
            sz *= 2;
        }
        n = sz;
        t.resize(2 * sz);
 
        build_first(1, 0, n, 0);
        for (int i = 0; i < (int) lvl.size(); ++i) {
            calc_next(i);
        }
    }
 
    pair<int, long long> get() {
        return t[1].ans;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    SegTree t(n, k);
    for (int i = 0; i < n; ++i) {
        t.update(i, a[i]);
    }
    pair<int, long long> ans = t.get();
    cout << ans.first << ' ' << ans.second << '\n';
    int q;
    cin >> q;
    while (q--) {
        int pos, value;
        cin >> pos >> value;
        pos = (pos + ans.first + ans.second) % n + 1;
        t.update(pos - 1, value);
        ans = t.get();
        cout << ans.first << ' ' << ans.second << '\n';
    }
}

$$$a_2 - a_1 + a_3 - a_2 + \ldots + a_n - a_{n - 1} = a_n - a_1$$$. So we just need to maximize this value, which means the answer is the maximum number in the array minus the minimum.

Let's notice that each cell intersects with no more than two diagonals, so the answer to the problem is at least $$$\frac{k + 1}{2}$$$.

Claim: Let's look at the construction where we color all cells in the first row and leave only two side cells uncolored in the last row. Then each of these cells corresponds to exactly two diagonals. And if $$$k \leq (2n - 2) * 2$$$, then the answer is exactly $$$\frac{k + 1}{2}$$$.

Now let's notice that if we color $$$2n - 1$$$ or $$$2n$$$ cells, then one or two cells will correspond to exactly one diagonal respectively, because in this case we must color the side cells, as they are the only diagonals not touched, but they are already covered by another diagonal corresponding to another corner cell.

Therefore, the answer in case of $$$4n - 3$$$ remains the same due to parity, and for $$$4n - 2$$$ it is $$$\frac{k}{2} + 1$$$.

Let's notice that the condition that we can achieve arbitrarily large values means that we need to guarantee at least a $$$+1$$$ to our coins. At the very first win. In this case, we can repeat this strategy indefinitely.

Also, let's notice that if we have lost a total of $$$z$$$ before, then in the next round we need to bet $$$y$$$ such that $$$y \cdot (k - 1) \gt z$$$, because otherwise the casino can give us a win. In this case, the condition of not losing more than $$$x$$$ times in a row will disappear, and we will end up in the negative. Therefore, the tactic is not optimal.

Therefore, the solution is as follows: we bet $$$1$$$ at first, then we bet the minimum number such that the win covers our loss. And if we have enough to make such a bet for $$$x + 1$$$, then the casino must end up in the negative, otherwise we cannot win.

So the solution is in $$$O(x)$$$ time complexity, where we simply calculate these values in a loop.

Let $$$dpv$$$ be the number of non-empty sets of vertices in the subtree rooted at $$$v$$$ such that there are no pairs of vertices in the set where one vertex is the ancestor of the other.

Then $$$dpv = (dp_{u_1} + 1) \cdot (dp_{u_2} + 1) \cdot \ldots \cdot (dp_{u_k} + 1)$$$, where $$$u_1, \ldots, u_k$$$ are the children of vertex $$$v$$$. This is because from each subtree, you can choose either any non-empty set or an empty set. Choosing an empty set from each subtree implies that only the single vertex $$$v$$$ is selected (since our dynamic programming state cannot be empty).

Now the claim is: the answer to the problem is $$$dp_1 + dp_2 + \ldots + dp_n + 1$$$. This is because if we consider the case where there is a pair of vertices where vertex $$$v$$$ is the ancestor of the other, the answer in this case is $$$dp{u_1} + \ldots + dp{u_k}$$$, as we can select such a set of vertices exactly from one subtree from the dynamic programming states. (And here we are using non-empty sets in the dynamic state, since otherwise, the case where there are no vertices where one is the ancestor of the other would be counted). And $$$dp_1 + 1$$$ (where $$$1$$$ is the root of the tree) accounts for the scenarios where there is no vertex where one is the ancestor of the other.

Let's consider each edge $$$i$$$ and mark the set of pairs $$$S_i$$$ that it covers. Then the claim is: we have a total of $$$O(k)$$$ different sets. This is because we are only interested in the edges that are present in the compressed tree on these $$$k$$$ pairs of vertices. And as it is known, the number of edges in the compressed tree is $$$O(k)$$$.

Then we need to find the minimum number of sets among these sets such that each pair is present in at least one of them. This can be achieved by dynamic programming on sets as follows:

Let $$$dp[mask]$$$ be the minimum number of edges that need to be removed in order for at least one edge to be removed among the pairs corresponding to the individual set bits in $$$mask$$$.

Then the update is as follows: $$$dp[mask | S_i] = \min(dp[mask | S_i], dp[mask] + 1)$$$ for all distinct sets $$$S$$$, where $$$S_i$$$ is the mask corresponding to the pairs passing through the edge. This update is performed because we are adding one more edge to this mask.

As a result, we obtain a solution with a time complexity of $$$O(nk + 2^k k)$$$, where $$$O(nk)$$$ is for precomputing the set of pairs removed by each edge for each edge, and $$$O(2^k k)$$$ is for updating the dynamic programming.

Let's list the numbers of vertices in the order of their values. Let it be $$$v1, \ldots, vn$$$. Then it must satisfy $$$value{vi} \leq value{v{i + 1}}$$$.

Then we have some segments in this order for which we do not know the values. For each segment, we know the maximum and minimum value that the values in this segment can take, let's say $$$L$$$ and $$$R$$$. Then we need to choose a value from the interval $$$(L, R)$$$ for each number in this segment in order to maintain the relative order. This is a known problem, and there are $$$\binom{R - L + len}{len}$$$ possible ways to do this, where $$$len$$$ is the length of the segment. Then we need to multiply all these binomial coefficients.

Now, notice that $$$R - L + len$$$ is large, so for calculation we can simply use the formula $$$\binom{n}{k} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)}{k!}$$$, since the sum $$$len$$$ does not exceed $$$n$$$.

Only the following pairs of numbers are possible: $$$(x, x)$$$, $$$(x, 2 \cdot x)$$$, and $$$(x, 3 \cdot x)$$$

Notice that only the following pairs of numbers are possible: $$$(x, x)$$$, $$$(x, 2 \cdot x)$$$, and $$$(x, 3 \cdot x)$$$.

The number of the pairs of the first kind is $$$n$$$, of the second kind is $$$2 \cdot \lfloor \frac{n}{2} \rfloor$$$, and of the third kind is $$$2 \cdot \lfloor \frac{n}{3} \rfloor$$$ (the factor $$$2$$$ in the latter two formulae arises from the fact that pairs are ordered). Therefore, the answer to the problem is $$$n + 2 \cdot \left( \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor \right)$$$.

Solve the problem for $$$k = 2$$$.

Solve the problem without the "$$$(r, c)$$$ must be colored" limitation.

Try to paint diagonals

No, you don't need casework

Notice that the answer to the problem is at least $$$\frac{n^2}{k}$$$, because you can split the square into so many non-intersecting rectangles of dimensions $$$1 \times k$$$. So let's try to paint exactly so many cells and see if maybe it's always possible.

For simplicity, let's first solve the problem without necessarily painting $$$(r, c)$$$. In this case, we're looking for something like a chess coloring, which is a diagonal coloring.

Let's number the diagonals from the "lowest" to the "highest". Notice that every $$$1 \times k$$$ and $$$k \times 1$$$ subrectangle intersects exactly $$$k$$$ consecutive diagonals, so we can paint every $$$k$$$-th diagonal to obtain the required answer: every such subrectangle will contain exactly one painted cell.

To add the $$$(r, c)$$$ requirement back, notice that $$$(r, c)$$$ lies on the diagonal number $$$r + c$$$. (Because if you trace any path from $$$(0, 0)$$$ to $$$(r, c)$$$ with non-decreasing coordinates, going one cell upwards or rightwards increases exactly one of the coordinates by one, and also increases the number of the diagonal by one). Therefore, all we need to do is paint the cells whose coordinates satisfy $$$(x + y) \% k = (r + c) \% k$$$

We've got a problem if $$$b_{i} \gt b_{i + 1} + 1$$$

It's alright if $$$a_i = b_i$$$

Programmers aren't mathematicians, you don't need to prove the solution

Firstly, we obviously require $$$a_i \le b_i$$$ to hold for all $$$i$$$. With that out of our way, let's consider non-trivial cases. Also let $$$a_{n+1} = a_1, b_{n+1} = b_1$$$ cyclically.

For each $$$i$$$, we require that either $$$a_i = b_i$$$ or $$$b_i \leq b_{i + 1} + 1$$$ holds. That's because if we increment $$$a_i$$$ at least once, we had $$$a_i = b_i - 1$$$ and $$$a_{i + 1} \le b_{i + 1}$$$ before the last increment of $$$a_i$$$, and from here it's just a matter of simple algebraic transformations.

Now let's prove these two conditions are enough. Let $$$i$$$ be the index of the minimal element of $$$a$$$ such that $$$a_i \lt b_i$$$ (i.e. the smallest element that's not ready yet). Notice that in this case we can, in fact, assign $$$a_i := a_i+1$$$, because $$$a_i \leq b_i \leq b_{i + 1} + 1$$$ holds, and now we're one step closer to the required array. It's easy to continue this proof by induction.

Reformulate this problem in terms of a complete binary tree.

It would be strange for the sponsors to changes two nodes of the same depth.

The problem can be reformulated as follows. We've got a complete binary tree with $$$2^n$$$ leaves. There's a marked edge from each intermediate node to one of its children. The winner is the leaf reachable from the root via marked edges. Changes modify the outgoing marked edge of a node.

Now it should be fairly obvious that there's no reason to change more than one node per level, because only one node matters per level--the one on the path from the root to the answer node. So, the winner only depends on the subset of levels we perform changes on, and vice versa: different subsets always yield different winners.

Sponsors can change exactly $$$i$$$ nodes in $$$\binom{n}{i}$$$ ways. Summing this over $$$i$$$, we get $$$\sum_{i=0}^{\min(n, k)} \binom{n}{i}$$$. Call this number $$$m$$$. $$$m$$$ is the number of winners the sponsors choose between--let's call them candidates for brevity. It's easy to see that $$$m$$$ is the answer to the problem, because a) sponsors can guarantee the winner is at least $$$m$$$, as, independent of the list of candidate winners "provided" by Madoka, at least one of them must be at least $$$m$$$, and b) Madoka can guarantee the winner is at most $$$m$$$ by firstly marking edges arbitrarily, then computing the list of candidate nodes, and only then fill them with numbers from $$$1$$$ to $$$m$$$ (and the other nodes arbitrarily).

Bruteforce $$$c$$$

$$$gcd(a, b)$$$ divides $$$a + b$$$.

Recall the existence of the Euler's totient function

Let's bruteforce $$$c$$$, then we have $$$gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$$$. This means that $$$gcd(a, b)$$$ divides $$$n - c$$$, so let's just go through all divisors of $$$n - c$$$. For every factor $$$d$$$, the count of pairs $$$(a, b)$$$ satisfying $$$a + b = n - c$$$ and $$$gcd(a, b) = d$$$ is $$$\phi (\frac{n - c}{d})$$$, because we need $$$d$$$ to divide $$$a$$$ and be coprime with $$$\frac{n - c}{d}$$$, so that the $$$gcd$$$ is equal to $$$d$$$.

Therefore, the answer to the problem is $$$\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$$$, where $$$1 \leq c \leq n - 2$$$ and $$$d$$$ is a factor of $$$n - c$$$.

Try graph theory.

Try flow theory.

No, that won't work, try again.

Let's reformulate the problem in terms of graphs. We are given an undirected graph and we are asked to determine edge directions, subject to fixed indegree minus outdegree (hereinafter balance) values for some vertices.

It is tempting to think of this as a flow problem: edges indicate pipes with capacity of 1, vertices are producers or consumers of flow, and vertices with fixed differencies produce or consume an exact amount of flow. Except that's not quite an equivalent problem: a maxflow algorithm will find a flow, i.e. an orientation of edges, but it might just ignore some edges if it feels like it.

We need to overcome this somehow by introducing incentive to use all edges. To do this, forget about the "edges are edges, vertices are vertices" idea for a while. Create an imaginary source and add a pipe with capacity 1 to every edge of the original graph. Technically, this is interpreting edges of the original graph as vertices of the flow graph. Non-technically, I like to interpret this like magically spawning flow into the middle of the edge.

Now, the flow appearing in the edge has to actually go somewhere if we want the maxflow algorithm to treat it like a treasure it wants to increase. Let's just add two pipes: from the edge to vertex $$$u_i$$$ and from the edge to vertex $$$v_i$$$, because where else would it go? (technically, any capacity works, but let's use 1 for simplicity) This has a nice side effect of determining the orientation of the edge: if the flow from the edge goes into $$$u_i$$$, it's as if it was oriented from $$$v_i$$$ to $$$u_i$$$, and vice versa.

A small problem is that this changes the semantics of the edge orientation somewhat. In the original problem, $$$u_i \to v_i$$$ incremented $$$v_i$$$ and decremented $$$u_i$$$. In the new formulation, only $$$v_i$$$ is incremented, so we need to transform the requirements $$$a_v$$$ on balances into requirements $$$b_v$$$ on indegrees: $$$b_v = \frac{a_v + \mathrm{deg} v}{2}$$$ (and we need to check that the numerator is even and non-negative, otherwise the answer is NO).

How do we enforce the indegree requirements? For all vertices with $$$s_v = 1$$$, add a pipe from the vertex $$$v$$$ to an imaginary sink with capacity $$$b_v$$$. We expect all these pipes to be satiated.

What about vertices with $$$s_v = 0$$$? Unfortunately, we can't just add a pipe from the vertex $$$v$$$ to an imaginary sink with capacity $$$\infty$$$, because if you have an edge with $$$s_v = 0$$$ and $$$s_u = 1$$$, the maxflow algorithm doesn't have any incentive to let the flow go to $$$u$$$ instead of $$$v$$$, so the pipe from $$$u$$$ to the sink might not get satiated and we might erroneously report a negative answer.

How do we require certain pipes to be satiated? We could theoretically use a push-relabel algorithm, but in this case we can use something much simpler. The sum of capacities of all pipes from the imaginary source is $$$m$$$. We expect them all to be satiated, so this is the total flow we're expecting. The sum of capacities of all pipes to the imaginary sink we want to satiate is $$$\sum_v b_v$$$. Therefore, there's a surplus of flow of exactly $$$\Delta = m - \sum_v b_v$$$ (if it's negative, the answer is NO). So: create an intermediate vertex, add a pipe of capacity $$$\infty$$$ from each vertex with $$$s_v = 0$$$ to this intermediate vertex, and a pipe from this intermediate vertex to the imaginary sink with capacity $$$\Delta$$$. This will stop the algorithm from relying too much on non-fixed vertices.

Run a maxflow algorithm. Check that every pipe from the source to an edge and every pipe from a vertex to the sink is satiated, or, alternatively, the maxflow is exactly $$$m$$$. If this does not hold, the answer is NO. If this holds, the answer is YES and the edge orientation can be restored by checking which of the two pipes from an edge is satiated.

Is this fast? That depends on the algorithm heavily.

Firstly, you can use the Edmonds-Karp algorithm. It works in $$$\mathcal{O}(FM)$$$, where $$$F$$$ is the maxflow and $$$M$$$ is the number of pipes. The former is $$$m$$$ and the latter is $$$n + m$$$, so we've got $$$\mathcal{O}((n + m) m)$$$, which is just fine.

Secondly, you can use Dinic's algorithm, which is typically considered an improved version of Edmonds-Karp's, but is worse in some cases. It improves the number of rounds from $$$F$$$ to $$$\mathcal{O}(N)$$$, where $$$N$$$ is the number of vertices in the network, which doesn't help in this particular problem, sacrificing the complexity of a single phase, increasing it to $$$\mathcal{O}(NM)$$$, which is a disaster waiting to happen.

Lots of people submitted Dinic's instead of Edmonds-Karp's. I don't know why, perhaps they just trained themselves to use Dinic's everywhere and didn't notice the unfunny joke here.

Luckily for them, Dinic's algorithm still works. You might've heard it works in $$$\mathcal{O}(M N^{2/3})$$$ for unit-capacity networks, where $$$M$$$ is the number of pipes and $$$N$$$ is the number of vertices, which translates to $$$\mathcal{O}((n + m) n^{2/3})$$$ in our case, which would be good enough if the analysis held.

Our network is not unitary, but it's easy to see how to make it into one. We use non-unit capacities in three cases:

• When we enforce the indegree, we add a pipe with capacity $$$b_v$$$ from the vertex to the sink. We can replace it with $$$b_v$$$ pipes of capacity 1. As $$$\sum_v b_v \le m$$$, this will not increase the number of pipes by more than $$$m$$$, so the complexity holds. Due to how Dinic's algorithm works, replacing a pipe with several pipes of the same total capacity does not slow the algorithm down.

• Similarly, the pipe from the intermediate vertex to the sink has capacity $$$\Delta \le m$$$, so we could theoretically replace it with $$$\Delta$$$ unit pipes and the complexity would hold.

• Finally, when we handle vertices with $$$s_v = 0$$$, we add pipes from such vertices to the intermediate vertex with capacity $$$\infty$$$. However, for each such vertex, the maximum used capacity is actually the count $$$k$$$ of edges incident with $$$v$$$, so the capacity of such pipes could be replaced with $$$k$$$. This would obviously have the same effect, and would not slow Dinic down: even if it tries to push more than $$$k$$$ through the corresponding backedge, it will quickly rollback, which affects the time taken by a single phase (non-asymptotically), but not the count of phases. As the sum of $$$k$$$ is $$$\mathcal{O}(m)$$$, we're fine again.

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = (1 << 19);
 
pair<int, int> t[2 * N]; // сnt, maximum
int mod[2 * N];
bool its_leaf[2 * N];
 
void push(int v) {
    t[v * 2 + 1].second += mod[v];
    t[v * 2].second += mod[v];
    mod[v * 2 + 1] += mod[v];
    mod[v * 2] += mod[v];
    mod[v] = 0;
}
 
int f(int v, int w) {
    if (its_leaf[v]) {
        if (t[v].second > w)
            return 1;
        return 0;
    }
 
    push(v);
    int r = v * 2, l = v * 2 + 1;
    if (t[l].second >= w)
        return f(r, w);
    else
        return f(l, w) + t[v].first - t[l].first;
}
 
void update(int v, int l, int r, int L, int R, int val) {
    if (R <= l || r <= L)
        return;
    if (L <= l && r <= R) {
        t[v].second += val;
        mod[v] += val;
        return;
    }
 
    push(v);
    int m = (l + r) / 2;
    update(v * 2 + 1, l, m, L, R, val);
    update(v * 2, m, r, L, R, val);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
void build(int v, int l, int r, vector<int> &a) {
    if (r - l == 1) {
        its_leaf[v] = 1;
        t[v] = make_pair(1, a[l]);
        return;
    }
 
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m, a);
    build(v * 2, m, r, a);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
pair<int, int> get(int v, int l, int r, int L, int R, int max_val) { // ans, max_val
    if (R <= l || r <= L)
        return {0, max_val};
    if (L <= l && r <= R)
        return {query(v, max_val), max(t[v].second, max_val)};
 
    push(v);
    int m = (l + r) / 2;
    auto z1 = get(v * 2 + 1, l, m, L, R, max_val);
    auto z2 = get(v * 2, m, r, L, R, z1.second);
    return {z1.first + z2.first, max(z1.second, z2.second)};
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    build(1, 0, n, a);
 
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            cout << get(1, 0, n, l - 1, r, -n).first << '\n';
        } else {
            int val;
            cin >> val;
            update(1, 0, n, l - 1, r, val);
        }
    }
}

The optimal answer has the maximum number of digits, so you only need to use the digits $$$1,2$$$.

Alternate these numbers so that there are no adjacent identical numbers.

Since we want to maximize the number we need, we will first find the longest suitable number. Obviously, it is better to use only the numbers $$$1$$$ and $$$2$$$ for this. Therefore, the answer always looks like $$$2121\ldots$$$ or $$$1212\ldots$$$. The first option is optimal when $$$n$$$ has a remainder of $$$2$$$ or $$$0$$$ modulo $$$3$$$, otherwise the second option is optimal.

Below is an example of a neat implementation.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    int type;
    if (n % 3 == 1)
        type = 1;
    else
        type = 2;
    int sum = 0;
    while (sum != n) {
        cout << type;
        sum += type;
        type = 3 - type;
    }
    cout << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

What is a picture if the answer to the problem is "YES".

Think about a square of size $$$2\times 2$$$.

Note that the answer to the problem is "YES" if and only if the picture is a certain number of disjoint rectangles. Now, in this case, let's look at all squares of size $$$2\times 2$$$, note that there cannot be exactly $$$3$$$ filled cells in each of them.

It is also clear that if there are $$$3$$$ such cells, then there will be two intersecting rectangles. Therefore, you just need to check if there is a $$$2\times 2$$$ square in which there are exactly $$$3$$$ colored cells.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j) {
            a[i][j] = s[j] - '0';
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
            if (sum == 3) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

There is always an answer when the upper right cell is painted white.

Imagine that you have only rectangles of size $$$1\times 2$$$.

Paint over the cells from the "end".

According to the condition, if the upper left cell is painted black, then we cannot paint it that way. Otherwise it is possible. Let's colour the cells in the following order: $$$(n,m), (n,m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$$$.

Let the cell $$$(i, j)$$$ be colored black, then if $$$j \gt 1$$$, then just paint the rectangle $$$(i, j - 1)$$$, $$$(i, j)$$$. Otherwise, if $$$j = 1$$$, then we will color the rectangle $$$(i - 1, j)$$$.

After such an operation, no cells that we painted before will be repainted, since they have one coordinate larger than ours, and the cell itself will be painted black.

Thus, we are able to paint the table for a maximum of $$$n\cdot m - 1$$$ operations.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j)
            a[i][j] = s[j] - '0';
    }
    vector<array<int, 4>> ans;
    if (a[0][0] == 1) {
        cout << -1<< '\n';
        return;
    }
    
    for (int j = m - 1; j >= 0; --j) {
        for (int i = n - 1; i >= 0; --i) {
            if (a[i][j]) {
                if (i != 0) {
                    ans.push_back({i, j + 1, i + 1, j + 1});
                } else {
                    ans.push_back({i + 1, j, i + 1, j + 1});
                }
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

A number is beautiful only if it is a multiple of $$$d$$$, but not a multiple of $$$d^2$$$

Let's solve a more general problem: count the number of such partitions.

This problem is solved by dynamic programming.

Keep the remaining number in dynamics, as well as the last divisor.

Let's solve a more complex problem: calculate the number of partitions into such multipliers.

This is easily solved by dynamic programming. Let $$$dp_{n, d}$$$ be the number of factorizations, if we have a number left to decompose the number $$$n$$$, and before that we divided by the number $$$d$$$. Let's go through all such beautiful numbers $$$i\geq d$$$ that divide $$$n$$$, then $$$dp_{n /i, i} += dp_{n, d}$$$.

Note that in this case, we took into account each option exactly once, since we count the divisors in the order of their increase.

Let $$$C$$$ be the number of divisors of the number $$$x$$$, and $$$V$$$ be the number of beautiful divisors of the number $$$x$$$. Then it works for $$$O(C\cdot V)$$$ or $$$O(C\cdot V^2\cdot log)$$$ depending on the implementation (since $$$n$$$ is always a divisor of the number $$$x$$$), but it all comes easily, since $$$V$$$ is no more $$$700$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
bool good(int i, int d) {
    return i % d == 0 && i % (1ll * d * d) != 0;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    map<pair<int, int>, int> dp;
    dp[{x, 1}] = 1;
    int res = 0;
    vector<int> del;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            if (good(i, d))
                del.push_back(i);
            if (x != i * i && good(x / i, d))
                del.push_back(x / i);
        }
    }
    while (dp.size()) {
        auto z = *dp.rbegin();
        if (z.first.first == 1) {
            res += z.second;
        }
        for (auto i : del) {
            if (z.first.first % i == 0 && i >= z.first.second) {
                dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2);
            }
        }
        dp.erase(z.first);
    }
    if (res == 1)
        cout << "NO\n";
    else
        cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
        solve();
}

Consider the case

Let $$$x = d^a\cdot b$$$. Where $$$b$$$ is not a multiple of $$$d$$$.

Then consider a few cases:

• $$$a = 1$$$. Then $$$a$$$ is a beautiful number, since any number multiple of $$$d^2$$$ can be decomposed into $$$d\cdot(a/d)$$$, each of which is colored, and a number multiple of only $$$d$$$, obviously, cannot be decomposed. So in this case there is exactly one option.

• $$$b$$$ is composite, then obviously we can decompose in several ways if $$$a\neq 1$$$.

• $$$d$$$ is simple. If $$$b$$$ is prime, then the statement — we have only one option to decompose the number. Since every beautiful multiplier of the form $$$d\cdot k$$$. But since $$$d$$$ is simple, there are no other ways to decompose it, except to add a multiplier from $$$b$$$, and since $$$b$$$ is simple, then all these options will be equal before the permutation.

• $$$d$$$ is composite and is not a power of prime. If $$$a\leq 2$$$, then this case is no different from the past, since we still have to get two beautiful multipliers and they will all just be equal to $$$d$$$. Otherwise, let $$$d = p\cdot q$$$, where $$$gcd(p, q) = 1$$$. Then we can make the number $$$p\cdot q^{b - 1}$$$ and $$$p^{b - 1}\cdot q$$$. And also $$$q\cdot p, q\cdot p, \ldots , q\cdot p$$$, in this case we have a different number of divisors, so these options will be different, which means we have several options in this case.

• $$$d$$$ is the power of a prime number. Then $$$d = p^k$$$. The statement, if $$$d = p^2$$$, and $$$x =p^7$$$, then it cannot be decomposed in several ways, otherwise, if $$$a \gt 2$$$ and $$$k \gt 1$$$, then let's look at the partition of $$$p^{2k - 1}, p^{k+1}, p^k, \ldots , p^k$$$, it is clear that if $$$k \gt 2$$$, then even if $$$b = p$$$, then the multiplier of $$$p^{k+ 2}$$$ will still be beautiful, so it does not differ from the composite $$$d$$$ in last case. Otherwise, if $$$k = 2$$$, then if $$$a = 3$$$ and $$$b = p$$$, then nothing can be added, otherwise we will have the opportunity to choose $$$3$$$ of the multiplier $$$p^k$$$, and somehow decompose the rest (since in this case $$$a \gt 3$$$, then at least one more multiplier will be) and add $$$b$$$ there. And we can decompose these 3 multipliers into $$$2$$$ or $$$3$$$ multipliers, as written above. Therefore, the only unique case when $$$d$$$ is the degree of a prime is $$$d = p^2, x = p^7$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int prime(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0)
            return i;
    }
    return -1;
}
 
void solve() {
    int x, d;
    cin >> x >> d;
    int cnt = 0;
    while (x % d == 0) {
        ++cnt;
        x /= d;
    }
    if (cnt == 1) {
        cout << "NO\n";
        return;
    }
    if (prime(x) != -1) {
        cout << "YES\n";
        return;
    }
    if (prime(d) != -1 && d == prime(d) * prime(d)) {
        if (x == prime(d) && cnt == 3) {
            cout << "NO\n";
            return;
        }
    }
    if (cnt > 2 && prime(d) != -1) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--)
        solve();
}

After each operation, the maximum number is always increased by a specific number.

Students with a number greater than $$$n$$$ are not interested in us.

Imagine that schoolchildren are not expelled, but at any given time we are just interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.

Understand that every student will move to one particular desk after all the operations.

Write a greedy

After each lesson, the person's number increases from the maximum number by the number of desks where no one goes. Therefore, it is easy to calculate how much time has passed since the very beginning, let it be the number $$$k$$$.

Then let's imagine that schoolchildren are not expelled, but at any given time we are simply interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.

Let $$$to_i$$$ be the desk to which the student will move after $$$k$$$ transfers, who originally sat at $$$i$$$ desk. This is a standard problem that can be solved using binary lifts or not the most pleasant dfs with cycle allocation and the like. (but we do not recommend you to write the latter), we define the set $$$V_i$$$ as the set of all numbers $$$j$$$, where $$$to_j = i$$$.

Let the starting placement of the student be a permutation of $$$b$$$, then we will understand that if someone is transferred to the $$$i$$$ desk after $$$k$$$ operations, then the value in it is the minimum value in $$$V_i$$$. And if no one changes seats for it, then a student with the same number will always sit in it, regardless of the initial seating arrangement. After that, it is not difficult to guess the optimal starting seating of schoolchildren.

Let $$$s$$$ be a lot of schoolchildren for whom we have not yet chosen the desk at which they are sitting. We will iterate over $$$i$$$ from $$$1$$$ to $$$n$$$ in ascending order. Then you need to understand who should sit at the $$$i$$$ desk.

If we know that there is a desk for which $$$min(V_i) = i$$$ must be performed, then we must put a student with the minimum number of $$$V_i$$$ at $$$i$$$, and we can put the remaining people at any desks with a number greater than $$$i$$$, so we will add all the other students to the set $$$s$$$. Otherwise, we just need to take a person from $$$s$$$ with the minimum number and put him in a place under the number $$$i$$$, and then just remove him from the set of $$$s$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int K = 30;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> cnt(n);
    vector<vector<int>> up(n, vector<int> (K));
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        --a;
        ++cnt[a];
        up[i][0] = a;
    }
    for (int k = 1; k < K; ++k) {
        for (int i = 0; i < n; ++i) {
            up[i][k] = up[up[i][k - 1]][k - 1];
        }
    }
    vector<int> a(n);
    int cnt_bad = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (!cnt[i]) {
            ++cnt_bad;
        }
    }
    int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad;
    vector<vector<int>> add(n);
 
    for (int i = 0; i < n; ++i) {
        int v = i, level = k;
        for (int j = K - 1; j >= 0; --j) {
            if (level >= (1 << j)) {
                level -= (1 << j);
                v = up[v][j];
            }
        }
        add[a[v] - 1].push_back(i);
    }
    set<int> now;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        if (add[i].size()) {
            int res = *min_element(add[i].begin(), add[i].end());
            for (int j : add[i]) {
                if (j != res) {
                    now.emplace(j);
                }
            }
            ans[res] = i + 1;
        } else {
            ans[*now.begin()] = i + 1;
            now.erase(*now.begin());
        }
    }
    for (int i : ans)
        cout << i << ' ';
    cout << '\n';
}

Realize that the maximum element is always an "inflection" of the first sequence.

It can be assumed that the "inflection" of the second subsequence will always be to the left of the maximum element (if anything, you can then simply expand the array).

In total, we have $$$3$$$ points in time — both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.

The first and third cases are solved by obvious greed.

For the second one, you can simply write the dynamics.

The inflection of the sequence is the maximum number in the subsequence. Then note that in the first subsequence, the inflection will be the maximum number in our array, let its position in the array be $$$ind$$$.

Then let's say for convenience that the inflection of the second subsequence will be to the right of the maximum element. (then expand the array and run the solution one more time).

In this case, we will have $$$3$$$ states: both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.

Let's solve the first case first:

Let $$$dp1_i$$$ be the minimum possible maximum element in a subsequence that does not contain an $$$i$$$ element. It is considered not difficult. If $$$dp1_{i - 1} \lt a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, a_{i - 1})$$$, since in this case we can add an $$$i$$$ element to a subsequence that does not contain an element of $$$i - 1$$$. Similarly, if $$$a_{i - 1} \lt a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, dp1_{i - 1})$$$.

The third case is considered anologically, but only it needs to be counted from the end. (This array will be $$$dp3$$$)

Now let's deal with the second case:

Let $$$dp2_{i, 0}$$$ be the minimum possible last element in the second subsequence if the $$$i$$$ element belongs to the first subsequence. And $$$dp2_{i, 1}$$$ is the maximum possible last element in the first subsequence if the $$$i$$$ element belongs to the second subsequence. There are several options. If $$$i$$$ and $$$i - 1$$$ lie in the same and different subsequences. And we will count for $$$i\leq ind$$$, since before this section both sub-sequences increase, and this is another calculated case. And then it is not difficult to get the conversion formulas:

• $$$dp2_{ind, 0} = dp1_{ind}$$$, by definition $$$dp2_{ind, 0}$$$
• If $$$a_{i - 1} \gt a_i$$$, then $$$dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$$$.
• If $$$dp2_{i - 1, 1} \gt a_i$$$, then $$$dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$$$.
• If $$$a_{i - 1} \lt a_{i}$$$, then $$$dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$$$.
• If $$$dp2_{i - 1, 0} \lt a_i$$$, then $$$dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$$$.

Now let's understand that the element with the number $$$i$$$ can be an inflection of the second subsequence if $$$i \gt ind$$$, as well as $$$dp2_{i, 1} \gt dp3_{i}$$$. That is, we can move from the second state to the third.

#include <bits/stdc++.h>
 
using namespace std;
 
const int inf = 1e9 + 228;
 
int solve (int n, vector<int> a) {
    int ind = max_element(a.begin(), a.end()) - a.begin();
    vector<int> dp1(n, inf);
    dp1[0] = -1;
    for (int i = 1; i <= ind; ++i) {
        if (a[i] > dp1[i - 1])
            dp1[i] = min(dp1[i], a[i - 1]);
        if (a[i] > a[i - 1])
            dp1[i] = min(dp1[i], dp1[i - 1]);
    }
 
    vector<int> dp2(n, inf);
    dp2[n - 1] = -1;
    for (int i = n - 2; i >= ind; --i) {
        if (a[i] > dp2[i + 1])
            dp2[i] = min(dp2[i], a[i + 1]);
        if (a[i] > a[i + 1])
            dp2[i] = min(dp2[i], dp2[i + 1]);
    }
 
    vector<array<int, 2>> dp3(n, {inf, -inf});
    dp3[ind][0] = dp1[ind];
    int ans = 0;
    for (int i = ind + 1; i < n; ++i) {
        if (a[i - 1] > a[i])
            dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]);
        if (dp3[i - 1][1] > a[i])
            dp3[i][0] = min(dp3[i][0], a[i - 1]);
        
        if (a[i - 1] < a[i])
            dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]);
        if (dp3[i - 1][0] < a[i])
            dp3[i][1] = max(dp3[i][1], a[i - 1]);
        
        if (dp3[i][1] > dp2[i])
            ++ans;
    }
    return ans;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    int ans = solve(n, a);
    reverse(a.begin(), a.end());
    cout << ans + solve(n, a) << '\n';
}