题目
https://codeforces.ml/contest/1404/problem/C
思路
首先将x，y转换成区间L，R
于是对于每个ai可以分三种情况讨论：
i - a[ i ] == 0：当前位置可以直接删除
i - a[ i ] < 0：当前位置永远不可能被删除
i - a[ i ] > 0：当前位置之前删除掉 i - a[ i ] 个数字后，当前位置可以被删除
令s[ i ] = 区间 [ i , r ] 内最多可以删除多少个数
随着 r 的递增，s 数组的每个元素相对于之前，迭代后一定是不减的
所以s有单调性
于是只需要用线段树维护即可
代码
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> a;
vector<pair<int,int> > xy;struct SegTree
{vector<int> t;int n;SegTree(int _n) {n = _n;t.assign(4 * _n,0);};void push(int v) {t[2 * v] += t[v]; t[2 * v + 1] += t[v];t[v] = 0;}void upd(int v,int l,int r,int tl,int tr,int toAdd) {if (l > r) return;if (tl == l && tr == r) {t[v] += toAdd;return;}push(v);int m = (tl + tr) / 2;upd(2 * v,l,min(r,m),tl,m,toAdd);upd(2 * v + 1,max(l,m + 1),r,m + 1,tr,toAdd);}int q(int pos) {int tl = 0,tr = n - 1,tv = 1;while(tl != tr) {push(tv);int m = (tl + tr) / 2;if (pos <= m) tr = m,tv = 2 * tv;else tl = m + 1,tv = 2 * tv + 1;}return t[tv];}
};int main () {while(scanf("%d %d",&n,&q) == 2) {a.assign(n,0);for(auto &x : a) scanf("%d",&x);for(auto &x : a) x--;for(int i = 0; i < n; i++) a[i] = i >= a[i] ? i - a[i] : INF;vector<int> ans(q,-1);xy.assign(q,{ 0,0 });for(auto& [x,y] : xy) scanf("%d %d",&x,&y);for(auto& [x,y] : xy) x = x,y = n - y - 1;map<int,vector<int>> me;for(int i = 0; i < q; i++) me[xy[i].second].push_back(i);SegTree t(n);for(int r = 0; r < n; r++) {int l = 0,b = r,x = a[r];while(l <= b) {int m = (l + b) / 2;if (t.q(m) >= x) l = m + 1;else b = m - 1;}t.upd(1,0,b,0,n - 1,1);for(auto &id : me[r]) ans[id] = t.q(xy[id].first);}for(auto &x : ans) printf("%d\n",x);}
}