Clubstep
Contest: Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
Difficulty rating: 3500
Tags: binary search, brute force, data structures, greedy, trees

There is an extremely hard video game that is one of Chaneka's favourite video games. One of the hardest levels in the game is called Clubstep. Clubstep consists of $$$n$$$ parts, numbered from $$$1$$$ to $$$n$$$. Chaneka has practised the level a good amount, so currently, her familiarity value with each part $$$i$$$ is $$$a_i$$$.

After this, Chaneka can do several (possibly zero) attempts on Clubstep. In each attempt, she dies on one of the $$$n$$$ parts. If an attempt dies on part $$$p$$$, that means it only successfully passes through every part $$$k$$$ for all $$$1 \leq k \leq p-1$$$ and it does not reach any part $$$k$$$ for all $$$p+1 \leq k \leq n$$$. An attempt that dies on part $$$p$$$ takes $$$p$$$ seconds.

It is known that Chaneka improves much more on the part she dies on than anything else. It is also known that during an attempt, Chaneka does not get to practise that much on the parts she does not reach. So, the effect of an attempt that dies on part $$$p$$$ is as follows:

- Chaneka's familiarity value with part $$$p$$$ increases by $$$2$$$.
- Chaneka's familiarity value with each part $$$k$$$ for all $$$1 \leq k \leq p-1$$$ increases by $$$1$$$.

Note that each question is independent, so the attempt Chaneka does on a question does not affect the familiarity values of any other questions.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 3\cdot10^5$$$) — the number of parts in Clubstep.

The second line contains $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — Chaneka's familiarity value with each part.

The third line contains a single integer $$$q$$$ ($$$1\leq q\leq3\cdot10^5$$$) — the number of questions.

The $$$j$$$-th of the next $$$q$$$ lines contains three integers $$$l_j$$$, $$$r_j$$$, and $$$x_j$$$ ($$$1\leq l_j\leq r_j\leq n$$$; $$$1\leq x_j\leq10^9$$$) — the description of the $$$j$$$-th question.

Output format:
Output $$$q$$$ lines with an integer in each line. The integer in the $$$j$$$-th line represents the minimum time (in seconds) for Chaneka to make it such that the familiarity value for every part $$$p$$$ ($$$l_j \leq p \leq r_j$$$) is at least $$$x_j$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
For the $$$1$$$-st question, one possible strategy is to do the following:

1. Do $$$1$$$ attempt that dies on part $$$1$$$. This takes $$$1$$$ second. The familiarity values become $$$[3, 3, 2, 1, 2]$$$.
2. Do $$$1$$$ attempt that dies on part $$$4$$$. This takes $$$4$$$ seconds. The familiarity values become $$$[4, 4, 3, 3, 2]$$$.
3. Do $$$2$$$ attempts that die on part $$$5$$$. This takes $$$10$$$ seconds. The familiarity values become $$$[6, 6, 5, 5, 6]$$$.

The total time taken (in seconds) is $$$1+4+10=15$$$.

For the $$$2$$$-nd question, one possible strategy is to do the following:

1. Do $$$1$$$ attempt that dies on part $$$3$$$. This takes $$$3$$$ seconds. The familiarity values become $$$[2, 4, 4, 1, 2]$$$.
2. Do $$$2$$$ attempts that die on part $$$4$$$. This takes $$$8$$$ seconds. The familiarity values become $$$[4, 6, 6, 5, 2]$$$.

The total time taken (in seconds) is $$$3+8=11$$$.

Example input:
5
1 3 2 1 2
3
1 5 5
2 4 5
3 3 1

Example output:
15
11
0

Editorial:
Let's try to solve a single query $$$(l,r,x)$$$ in $$$O(n)$$$. It is clear that in the optimal strategy, we do not want to do any attempts that die on parts to the left of $$$l$$$ or to the right of $$$r$$$. There are two cases:
• If $$$a_r\geq x$$$, then we can ignore index $$$r$$$ and solve the query for $$$(l,r-1,x)$$$.
• If $$$a_r<x$$$, then it is optimal to do $$$\lceil\frac{x-a_r}{2}\rceil$$$ attempts that die on part $$$r$$$. This takes $$$r\cdot\lceil\frac{x-a_r}{2}\rceil$$$ seconds and will make all indices from $$$1$$$ to $$$r-1$$$ increase by $$$\lceil\frac{x-a_r}{2}\rceil$$$. After doing that, it is equivalent to ignoring index $$$r$$$ and solving the query for $$$(l,r-1,x-\lceil\frac{x-a_r}{2}\rceil)$$$.
For now, let's ignore $$$l$$$ and focus on $$$(r,x)$$$. For some pair $$$(r,x)$$$, there are two cases it can recurse into. We mainly care about the second case since it is the only one that contributes to the total time. For some pair $$$(r,x)$$$ of a query, we can turn it into $$$(r,x)$$$ where $$$r'$$$ ($$$r'\leq r$$$) is the rightmost index with $$$a_{r'}<x$$$. For some pair $$$(r,x)$$$ with $$$a_r<x$$$, we can see it as the pair recursing immediately to $$$(r',x-\lceil\frac{x-a_r}{2}\rceil)$$$ where $$$r'$$$ ($$$r'<r$$$) is the rightmost index with $$$a_{r'}<x-\lceil\frac{x-a_r}{2}\rceil$$$.
We want to maintain all important pairs $$$(r,x)$$$ that are needed to answer all queries. Two pairs with the same values of $$$r$$$ and $$$x$$$ that comes from different queries can be treated as the same pair.
Let's imagine a process to calculate all important pairs $$$(r,x)$$$. To do this, we iterate $$$r$$$ from $$$n$$$ to $$$1$$$ while maintaining all of the current important values of $$$x$$$, including the ones not bigger than $$$a_r$$$. Each iteration, we just modify the values of $$$x$$$ from the previous iteration. For each $$$r$$$, we first add new values of $$$x$$$ for all queries with this current value of $$$r$$$. Then, the important pairs $$$(r,x)$$$ for this value of $$$r$$$ are all current values of $$$x$$$ that are greater than $$$a_r$$$. And those values of $$$x$$$ are the values of $$$x$$$ which will get updated (changed into $$$x-\lceil\frac{x-a_r}{2}\rceil$$$) for the next iteration. If more than one value of $$$x$$$ updates into the same value, they merge and the number of values decreases.
Using the logic of the process above, it can be obtained that the total number of important pairs $$$(r,x)$$$ is $$$O(n+q\log\max(x))$$$.
Proof.
Notice that the number of important pairs is about equal to the number of updates to the value of $$$x$$$ in all iterations. Let's calculate the total number of updates.
Instead of looking at the values of $$$x$$$ that we maintain, let's sort those values and look at the gaps between adjacent values. For a value of $$$r$$$, the value of $$$a_r$$$ lies in one of the gaps. Then, that gap and all gaps located to the right of it in the number line will get updated. The gap that contains $$$a_r$$$ can change arbitrarily, but each gap that is to the right of that gap will have its length divided by $$$2$$$, either floored or ceilinged.
This means, each gap can only have $$$\log\max(x)$$$ updates before having a length of $$$1$$$. Then, its length can get ceilinged multiple times before getting floored to $$$0$$$. When its length becomes $$$0$$$, the two values at the endpoints of the gap will merge.
It may look like there can be many updates because a length of $$$1$$$ can be ceilinged multiple times. However, for every gap having its length divided by $$$2$$$ in an iteration, the case where a length of $$$1$$$ gets ceilinged cannot happen on two adjacent gaps, so if there are $$$c$$$ gaps updated, that particular case can only happen on $$$\lceil\frac{c}{2}\rceil$$$ gaps. That means, the total number of updates is about two times the total number of times a gap gets its length decreased, plus the total number of gaps that contains $$$a_r$$$.
Therefore, the total number of important pairs is $$$O(n+q\log\max(x))$$$. $$$\blacksquare$$$
Knowing that, we can calculate all important pairs quickly using a stack and a priority queue. The stack maintains the current values of $$$x$$$ that have already been updated at least once. The priority queue only maintains new values of $$$x$$$ that have not been updated yet. In each iteration, we only process several values at the top of the stack and at the top of the priority queue, then each of those gets pushed into the stack with their new values, without changes in their order. The total number of operations in the stack is equal to the number of important pairs, but the total number of changes in the priority queue is only equal to the number of queries. So the total complexity of this is $$$O(n+q(\log\max(x)+\log n))$$$.
While calculating all important pairs, we can simultaneously construct a tree of pairs where the parent of each pair $$$(r,x)$$$ is its corresponding pair $$$(r',x-\lceil\frac{x-a_r}{2}\rceil)$$$.
We can solve each query using a simple binary lifting in the tree, but that would be too slow since there are $$$O(n+q\log\max(x))$$$ vertices. Instead, we can do a DFS traversal from the root while maintaining a stack of the values of $$$r$$$ in the DFS recursion. Solving a query in a vertex is just doing a binary search in the stack. So the total complexity of answering all queries is $$$O(n+(q\log\max(x)+\log n))$$$.
Time complexity: $$$O(n+(q\log\max(x)+\log n))$$$