1404C - Fixed Point Removal - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 445000
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int mo=998244353;
struct que{
	int x,y,i;
}p[N];
inline int read(){
	int x=0,w=0;char ch=getchar();
	while (!isdigit(ch))w|=ch=='-',ch=getchar();
	while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return w?-x:x;
}
int a[N],c[N],n,m,d[N],ans[N],w[N];
vector<int>v[N];
void add1(int x,int d){
	for (;x;x&=(x-1))c[x]+=d;
}
int q1(int x){
	int res=0;
	for (;x<=n;x+=(x&(-x)))res+=c[x];
	return res;
}
void add(int x,int d){
	for (;x<=n;x+=(x&(-x)))w[x]+=d;
}
int q(int x){
	int res=0;
	for (;x;x&=(x-1))res+=w[x];
	return res;
}
bool cmp(que a,que b){
	return a.x<b.x;
}
signed main(){
	n=read(),m=read();
	for (int i=1;i<=n;++i){
		a[i]=read();
//		if (i-a[i]>=0)v[i-a[i]].push_back(i);
	}
	for (int i=1;i<=n;++i){
		int l=1,r=i;
		while (l<=r){
			int mid=(l+r)>>1;
			if (q1(mid)>=i-a[i])l=mid+1,d[i]=mid;
			else r=mid-1;
		}
		if (i-a[i]>=0&&d[i])add1(d[i],1),v[d[i]].push_back(i),add(i,1);
//		cout<<i<<" "<<i-a[i]<<" "<<d[i]<<"!"<<endl;
	}
	memset(c,0,sizeof(c));
	for (int i=1;i<=m;++i)p[i].x=read()+1,p[i].y=n-read(),p[i].i=i;
	sort(p+1,p+1+m,cmp);
	for (int i=1,j=1;i<=n;++i){
		for (;j<=m&&p[j].x==i;++j){
			ans[p[j].i]=q(p[j].y)-q(p[j].x-1);
		}
		for (int k=0;k<v[i].size();++k)
			add(v[i][k],-1);
	}
	for (int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;	
}