Fixed Point Removal
题意翻译
给定一个含有 $n$ 个正整数的序列 $a$ ,对于一次操作,你可以任选一个位置 $i$ 且满足 $a_i=i$ ,那么就可以移除这个元素,并将后面所有的元素向前移动一位。
对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下,最多可以进行几次操作。
$n,q \leq 3\times 10^5$
translated by [lory1608](https://www.luogu.com.cn/user/333789#practice)
题目描述
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 $ ?
输入输出格式
输入格式
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 $ ).
输出格式
Print $ q $ lines, $ i $ -th line should contain a single integer — the answer to the $ i $ -th query.
输入输出样例
输入样例 #1
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
输出样例 #1
5
11
6
1
0
输入样例 #2
5 2
1 4 1 2 4
0 0
1 0
输出样例 #2
2
0
说明
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 $ .