题目概述

CF1405E

解题报告

显然有贪心：当有多个可以删除的元素同时存在时，先删除后面的，因为删后面的不影响前面。

既然如此，我们从左往右考虑一个位置能否被删除。对于一个位置 $i$ ，如果前面已经有 $now$ 个可以被删除的元素，$a_i\le i$ 并且 $i-a_i\le now$ ，就说明肯定存在一个时刻，$i$ 是可以被删除的。

一个询问 $(x,y)$ 其实就是询问一个区间 $[L,R]$ ，我们从 $L$ 位开始执行上述操作，然后询问 $[L,R]$ 中有多少个可以被删除的数即可。不难想到离线之后用线段树维护。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=300000,maxm=300000,maxt=maxn<<2;

int n,m,a[maxn+5],D[maxn+5],c[maxn+5],ans[maxm+5];
struct data {int L,R,id;} q[maxm+5];
int tag[maxt+5],MIN[maxt+5],ID[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline bool cmp(const data &a,const data &b) {return a.L<b.L;}
void Insert(int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]+=y;}
int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
void Build(int L,int R,int p=1){
    if (L==R) {MIN[p]=D[L];ID[p]=L;return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    if (MIN[p<<1]<MIN[p<<1|1]) MIN[p]=MIN[p<<1],ID[p]=ID[p<<1];
    else MIN[p]=MIN[p<<1|1],ID[p]=ID[p<<1|1];
}
void Addtag(int p,int k) {MIN[p]+=k;tag[p]+=k;}
void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) {MIN[p]=1e9;return;}
    int mid=l+(r-l>>1);Pushdown(p);
    if (pos<=mid) Update(pos,l,mid,p<<1); else Update(pos,mid+1,r,p<<1|1);
    if (MIN[p<<1]<MIN[p<<1|1]) MIN[p]=MIN[p<<1],ID[p]=ID[p<<1];
    else MIN[p]=MIN[p<<1|1],ID[p]=ID[p<<1|1];
}
void Dec(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addtag(p,-1);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Dec(L,R,l,mid,p<<1); else if (L>mid) Dec(L,R,mid+1,r,p<<1|1);
    else Dec(L,mid,l,mid,p<<1),Dec(mid+1,R,mid+1,r,p<<1|1);
    if (MIN[p<<1]<MIN[p<<1|1]) MIN[p]=MIN[p<<1],ID[p]=ID[p<<1];
    else MIN[p]=MIN[p<<1|1],ID[p]=ID[p<<1|1];
}
void Delete(int k) {D[k]=1e9;Insert(k,-1);Update(k);if (k<n) Dec(k+1,n);}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(n);readi(m);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1;i<=m;i++) readi(q[i].L),q[i].L++,readi(q[i].R),q[i].R=n-q[i].R,q[i].id=i;
    for (int i=1,now=0;i<=n;i++)
        if (a[i]<=i && i-a[i]<=now) D[i]=now-(i-a[i]),now++,Insert(i,1); else D[i]=1e9;
    Build(1,n);sort(q+1,q+m+1,cmp);
    for (int i=1,j=1;i<=n;i++){
        while (j<=m && q[j].L==i) ans[q[j].id]=Sum(q[j].R),j++;
        if (D[i]<1e9) {Delete(i);while (MIN[1]<0) Delete(ID[1]);}
    }
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}