题目
题解
首先对于一个数列它的答案为
数轴上$1\sim n$中每个数能往左覆盖它的个数个点，答案就是$1\sim n$中没有被覆盖的点
因为最后满足条件的情况肯定是$1\sim n$上有且只有一层覆盖（想象一个接力的过程），修改一个数可以看成把某个重叠的部分挪到空白处
这样可以用线段树维护区间$0$的个数，需要支持区间修改和区间查询
写的有点自闭……借鉴了题解的代码
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=4.5e5+5;
struct p{
int x,cnt,val,tags;
}s[MAX<<2];
int n,m,N,L,R,sL,P;
int a[MAX],cnt[MAX];
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
void pus(int k)
{
if(s[tl].x==s[tr].x) s[k].x=s[tl].x,s[k].cnt=s[tl].cnt+s[tr].cnt;
else if(s[tl].x>s[tr].x) s[k].x=s[tr].x,s[k].cnt=s[tr].cnt;
else if(s[tr].x>s[tl].x) s[k].x=s[tl].x,s[k].cnt=s[tl].cnt;
s[k].val=s[tl].val+s[tr].val;
}
void Add(int k,int d) {s[k].x+=d,s[k].val=(!s[k].x?s[k].cnt:0),s[k].tags+=d;}
void down(int k) {if(s[k].tags) Add(tl,s[k].tags),Add(tr,s[k].tags),s[k].tags=0;}
void build(int l=0,int r=N,int k=1)
{
s[k].val=s[k].cnt=r-l+1;
if(l==r) return;
build(l,mid,tl),build(mid+1,r,tr);
}
void change(int l,int r,int k,int L,int R,int d=1)
{
if(r<L||R<l) return;
if(l>=L&&r<=R) return void(Add(k,d));
down(k),change(l,mid,tl,L,R,d),change(mid+1,r,tr,L,R,d),pus(k);
}
int ask(int l,int r,int k,int L,int R)
{
if(r<L||R<l) return 0;
if(l>=L&&r<=R) return s[k].val;
return down(k),ask(l,mid,tl,L,R)+ask(mid+1,r,tr,L,R);
}
int main()
{
n=read(),m=read(),N=2*m+n,L=m,R=m+n,build();
for(int i=1;i<=n;++i)
++cnt[a[i]=read()+L];
for(int i=1+L;i<=n+L;++i)
if(cnt[i]) change(0,N,1,i-cnt[i]+1,i);
for(int i=1,p,x;i<=m;++i)
{
p=read(),x=read();
if(!p)
{
if(x>0) change(0,N,1,R-cnt[R]+1,R,-1),change(0,N,1,L-cnt[L]+1,L),--L,--R;
else ++L,++R,change(0,N,1,R-cnt[R]+1,R),change(0,N,1,L-cnt[L]+1,L,-1);
}
else
{
if(a[p]>L&&a[p]<=R) change(0,N,1,a[p]-cnt[a[p]]+1,a[p]-cnt[a[p]]+1,-1);
--cnt[a[p]],a[p]=L+x;
if(a[p]>L&&a[p]<=R) change(0,N,1,a[p]-cnt[a[p]],a[p]-cnt[a[p]]);
++cnt[a[p]];
}
printf("%d\n",ask(0,N,1,L+1,R));
}
return 0;
}
