Let us discuss a bruteforce solution. Multiply $$$A_i$$$ by $$$-1$$$ for even indices.

Start with $$$S = ans = 0$$$. Then for $$$i = L$$$ to $$$R$$$, do the following updates

• $$$S = S + A_i$$$
• $$$S = \max(S, 0)$$$
• $$$ans = ans + \dfrac{S}{K}$$$
• $$$S = S \bmod K$$$

Now, the optimization. Note that if the step $$$S = \max(S, 0)$$$ never happened, i.e. $$$S \ge 0$$$ always, then the answer is simply $$$\dfrac{A_L + \ldots + A_R}{K}$$$.

For each index $$$i$$$, suppose we found the first index $$$j$$$ such that $$$S = \max(S, 0)$$$ takes place first time at $$$j$$$ if we start from $$$i$$$. Then, we can answer all the queries using binary lifting (the contribution to answer from $$$i$$$ to $$$j$$$ can be found with previous observation).

The condition for $$$j$$$ to be first zero-ing index after $$$i$$$ can be written as $$$(A_i + \ldots + A_{j - 1}) \mod K + A_j \lt 0$$$, or equivalent $$$(P_{j - 1} - P_{i - 1}) \mod + A_j \lt 0$$$, where $$$P$$$ is a prefix sum array.

If $$$A_i \le -K$$$, it is always acting as a bad-index, and otherwise for $$$-K \le A_i \lt 0$$$, it is a bad index for (one or two) subarrays of values (taken modulo $$$K$$$). We can maintain a segment tree modulo $$$K$$$, where each node represents the minimum bad index for that modulo class.

The final complexity becomes $$$O(N \cdot log(N))$$$ after coordinate compression.

Let us try to find $$$R_i = $$$ maximum row of an off limit cell after the first $$$i$$$ days. If we symmetrically find the minimum row, maximum and min columns, we are done.

The core idea is to maintain an incremental pointer.

• Start with $$$T = N$$$, and $$$i = H$$$. Add all the updates that affect this last row.
• While there exists a cell with sum greater than or equal to $$$X$$$, update $$$R_T = i$$$, and decrement $$$T$$$. You should also remove the $$$T$$$-th update in this step (if it affects the current row)
• Decrement $$$i$$$, add some updates that affect upto $$$i$$$, remove some updates that affected $$$i + 1$$$ onwards (remember we only care about updates at time $$$\le T$$$). Rinse and repeat.

Note that this works because of two reasons — firstly, updates only create new off-limit cells, never remove previous ones; and secondly, we only care about the maximum bad row at each time and not some other problem (for example, solving time the $$$i$$$-th row went bad seems hard).

You can maintain a lazy add, max finder segment tree to handle the updates. The final complexity is $$$O(N \cdot log(N))$$$

First, note that exactly one cell in each diagonal will be modified, and we want to transmit $$$64 - 15 + 2 = 51$$$ cells (-15 represents one corrupted cell in each diagonal, +2 because $$$(0, 0)$$$ and $$$(7, 7)$$$ can always be recovered). Now, consider the second diagonal, which has two cells. We can encode "A" in this diagonal as "AA", and "B" in this diagonal as "AB". Then, if we receive "AB" or "BA", we know two things:

1. The original string was "AA".
2. If "AB", then adversary moved right; otherwise, the adversary moved down.

Similar logic applies to the case in which we receive either "AA" or "BB".

Now, how can we generalize this? Assume we are at the $$$i$$$th diagonal, and we also know that the adversary was at position $$$x$$$ in the $$$i - 1$$$th diagonal. Then, it will modify either $$$x$$$ or $$$x + 1$$$ in the $$$i$$$th diagonal, so we just have to be able to figure out which one it picks. Here's one way to do this: if we want to encode a string $$$s$$$ of length $$$l$$$ in a diagonal of length $$$l + 1$$$, set the first $$$l$$$ bits of that diagonal to $$$s$$$. Then, set the last bit such that there are an even number of As that lie on even indices in this diagonal. For instance, if we want to encode $$$s = ABAB$$$, we should set the diagonal to $$$ABABB$$$ (here, we 0-index, so the even indices correspond to [A, A, B]).

Then, after the adversary modifies this diagonal, we can check the parity of the number of As on even indices. If this parity remains even, the adversary modified an odd index; otherwise, the adversary modified an even index. Since exactly one of $$$x$$$ and $$$x + 1$$$ is even, and exactly one is odd, we can then determine precisely which one was changed and therefore recover the entire diagonal.

If we have removed some teleporters, consider how to find the maximum number of warp travels in Bitaro's route. Bitaro starts at $$$1$$$. When Bitaro is at position $$$x$$$, he greedily chooses a teleporter $$$s\to t$$$ that satisfies $$$s\ge x$$$ and has the smallest $$$t$$$.

Consider dynamic programming. Let $$$f_{i,j}$$$ denote the minimum cost required to move Bitaro to point $$$i$$$ in exactly $$$j$$$ steps. The cost of a transition $$$f_{i,j}\to f_{k,j+1}$$$ is the sum of the costs of teleporters satisfying $$$i\le s \lt t \le k-1$$$ (these teleporters must be removed to allow Bitaro to reach $$$k$$$). If we add an artificial point $$$n+1$$$, then $$$f_{n+1,K+1}$$$ gives the answer.

When $$$K$$$ increases, the answer decreases monotonically. Hence we can apply the Aliens trick (WQS binary search) to remove the constraint on $$$K$$$. We then define $$$f_i$$$ as the minimum cost to reach point $$$i$$$, and the transition cost from $$$f_i$$$ to $$$f_k$$$ is the sum of the costs of teleporters with $$$i\le s \lt t\le k-1$$$, plus a constant penalty. This DP can be computed in $$$\mathcal O(n\log n)$$$ using a segment tree.

The overall time complexity is $$$\mathcal O(n\log n\log V)$$$.

During the contest, I noticed that the transition cost satisfies the quadrangle inequality, so I tried using a simplified LARSCH algorithm to compute each round in $$$\mathcal O(n\log^2 n)$$$ with a persistent segment tree. However, this led to TLE, so I switched to running the DP directly with a persistent segment tree, which improved the complexity to $$$\mathcal O(n\log n)$$$.

Consider the $$$1$$$-dimensional problem. Covering each point by $$$K$$$ is equivalent to choosing a regular bracketed sequence of length $$$2 \cdot K$$$ where $$$x \ge X_i$$$ are open brackets, and $$$x \le X_i$$$ are closing brackets.

Now, there are a few ways to solve it. I used Alien's trick. For each pair of brackets matched, make the cost $$$C_i + C_j - L$$$ instead of $$$C_i + C_j$$$ for some parameter $$$L$$$, and then binary search on the optimal $$$L$$$ to have exactly $$$K$$$ matches (including $$$X$$$ and $$$Y$$$ dimensions).

You can solve the above problem with regret greedy. For every opening bracket, insert $$$(C_i - L)$$$ into a set. For every closing bracket, take out the optimal choice from the set and use it if it reduces total cost. Also, insert back $$$(-C_j)$$$ if you are using (to maybe overturn the decision later, regret greedy style).

The final complexity here becomes $$$O(N \cdot log(N) \cdot log(A))$$$

This is a standard centroid decomposition task. Split over the centroid, and then count for each $$$u$$$, how many valid $$$v$$$ exist.

Either the path $$$u \rightarrow root$$$ is good (i.e. we can stamp something on this path), in which case $$$v$$$ just needs to satisfy $$$d(u, v) \le D$$$ and $$$(u, v)$$$ in different subtrees. This is a well known task, and can be done with the observation that each $$$v$$$ induces a prefix of depths of $$$u$$$ to be good.

When $$$u \rightarrow root$$$ is not good, we need $$$root \rightarrow v$$$ to be good. For that case, it is easy to see that let $$$M = \min(a_i - dep_i)$$$ on this path, we must reach $$$root$$$ at time $$$\ge M$$$ only. So, in this case, each $$$v$$$ induces a subarray of depths of $$$u$$$, instead of a prefix.

We can maintain this info in a segment/fenwick tree to get $$$O(N \cdot log^2(N))$$$