Fixed Point Removal
Contest: Codeforces Round 668 (Div. 1)
Difficulty rating: 2300
Tags: binary search, constructive algorithms, data structures, greedy, two pointers

Let $$$a_1, \ldots, a_n$$$ be an array of $$$n$$$ positive integers. In one operation, you can choose an index $$$i$$$ such that $$$a_i = i$$$, and remove $$$a_i$$$ from the array (after the removal, the remaining parts are concatenated).

The weight of $$$a$$$ is defined as the maximum number of elements you can remove.

You must answer $$$q$$$ independent queries $$$(x, y)$$$: after replacing the $$$x$$$ first elements of $$$a$$$ and the $$$y$$$ last elements of $$$a$$$ by $$$n+1$$$ (making them impossible to remove), what would be the weight of $$$a$$$?

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$)  — the length of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of the array.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$x, y \ge 0$$$ and $$$x+y < n$$$).

Output format:
Print $$$q$$$ lines, $$$i$$$-th line should contain a single integer  — the answer to the $$$i$$$-th query.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first query:

After making first $$$x = 3$$$ and last $$$y = 1$$$ elements impossible to remove, $$$a$$$ becomes $$$[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$$$ (we represent $$$14$$$ as $$$\times$$$ for clarity).

Here is a strategy that removes $$$5$$$ elements (the element removed is colored in red):

- $$$[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$$$
- $$$[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$$$
- $$$[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$$$
- $$$[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$$$
- $$$[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$$$
- $$$[\times, \times, \times, 9, 4, 5, 3, \times]$$$ (final state)

It is impossible to remove more than $$$5$$$ elements, hence the weight is $$$5$$$.

Example input:
13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12

Example output:
5
11
6
1
0

Example input:
5 2
1 4 1 2 4
0 0
1 0

Example output:
2
0

Editorial:
Convenient transformation
Replace $$$a_i$$$ by $$$i - a_i$$$. The new operation becomes: remove a zero, and decrement all elements after by one.
For each query, note $$$l = 1+x$$$ and $$$r = n-y$$$ the endpoints of the non-protected subarray.
The main idea of the solution is iterating over $$$r$$$, maintaining answers for each $$$l$$$ in a BIT (increment on prefix) and answer queries offline (when we meet a right endpoint). What follows is a detailed explanation of this idea.
Simplified version
Let's suppose that $$$l = 1$$$ holds for all queries.
We can intuitively see that $$$a_i$$$ is removable iff $$$a_i \ge 0$$$ and we can remove at least $$$a_i$$$ elements before. We're going to rewrite this more formally.
Let $$$f(r)$$$ be the maximum number of elements we can remove in the subarray $$$a[1 \ldots r]$$$. If $$$a_r < 0$$$ or $$$a_r > f(r-1)$$$, then it's obviously impossible to remove $$$a_r$$$ and in that case, $$$f(r) := f(r-1)$$$.
Otherwise, if $$$0 \le a_r \le f(r-1)$$$, then $$$f(r) := f(r-1)+1$$$. We can reach this with the following strategy:
• Perform the $$$a_r$$$ first steps in the prefix $$$[1, r-1]$$$
• Remove $$$a_r$$$ (which is equal to $$$0$$$ at that moment)
• Perform the remaining $$$f(r-1) - a_r$$$ steps in the prefix $$$[1, r-1]$$$.
Hence, we can compute successively $$$f(1), f(2), \ldots, f(n)$$$ with a single loop: maintain current $$$f(r)$$$ in a variable $$$s$$$, and at each iteration increment $$$s$$$ if and only if $$$0 \le a_r \le s$$$.
Complete version
Note $$$f(l, r)$$$ the maximum number of elements we can remove in the subarray $$$a[l \ldots r]$$$ (zero if $$$l > r$$$). During our iteration over $$$r$$$, we're going to maintain the answers for each $$$l$$$: $$$$$$s = [f(1, r), f(2, r), \ldots, f(n, r)]$$$$$$
When the iteration continues, discovering a new element $$$a_r$$$, what happens? If $$$a_r < 0$$$, nothing happens. Otherwise, $$$s_l$$$ is incremented by one if and only if $$$s_l \ge a_r$$$.
Let $$$l_\max$$$ be the greatest $$$l$$$ such that $$$l \le r$$$ and $$$s_{l_\max} \ge a_r$$$. We should increment the prefix ending here by one:
$$$$$$\boxed{s_1 \ge \ldots \ge s_{l_\max}} \ge a_r > s_{l_\max + 1} \ge \ldots \ge s_n$$$$$$
A binary indexed tree (aka Fenwick tree) is obviously the structure we need in order to maintain $$$s$$$, since it allows to add on segment and get one element in $$$\mathcal{O}(\log n)$$$ (segment tree could work, but is slower in practice).
In order to find $$$l_\max$$$, the easiest solution is to binary search, it takes $$$\mathcal{O}(\log^2 n)$$$ time which is fast enough to get AC. We can also use binary lifting in order to optimize the search in $$$\mathcal{O}(\log n)$$$. This technique is explained in this blog.
We have to read all queries in advance (offline algorithm). When the iteration over $$$r$$$ meets the right endpoint of a query, we set its answer to the current weight of $$$s_l$$$.
In order to get an online algorithm (answer the query before reading the next one), we would have to use a persistent data structure.
Final complexity: $$$\mathcal{O}((n + q) \log n)$$$ with low constant factor.
Under given time limit, $$$\log^2$$$ solutions with reasonable constant factor could also pass.