题目
分析
动态开店线段树+分析性质。
首先我们要找出这个删数操作的性质，也就是：显然题中数的顺序没有关系，于是可以直接在值域上来看，然后发现如果把数轴画出来再按照个数在每一个映射点向前映射，需要修改的数的个数就是数轴上空的个数。
那么现在考虑有修改操作的时候：
对于单点修改，其实就是两个区间的变化，直接暴力修改就好了。
对于全局 (+1) ，我们可以把查询区间（假设之前是 ([l,r])）变成 ([l-1,r-1]) 了，全局 (-1) 也同理。
具体可以见代码。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=2e6+5,V=5e5;
int n,m,root=1,tmp=2e5;
int a[N],num[N],add[N];
struct SGT{int Min,num;}t[N];
SGT operator + (const SGT &a,const SGT &b){
if(a.Min<b.Min) return a;
if(a.Min>b.Min) return b;
return (SGT){a.Min,a.num+b.num};
}
void PushDown(int x){
if(!add[x]) return;
t[x<<1].Min+=add[x],t[x<<1|1].Min+=add[x],
add[x<<1]+=add[x],add[x<<1|1]+=add[x],
add[x]=0;
return ;
}
void Build(int l,int r,int x){
if(l==r) return t[x]=(SGT){0,1},void();
int mid=l+r>>1;
Build(l,mid,x<<1);
Build(mid+1,r,x<<1|1);
t[x]=t[x<<1]+t[x<<1|1];
return ;
}
void Modify(int L,int R,int l,int r,int v,int x){
if(L>R) return;
if(L<=l&&R>=r) return t[x].Min+=v,add[x]+=v,void();
PushDown(x);int mid=l+r>>1;
if(L<=mid) Modify(L,R,l,mid,v,x<<1);
if(R>mid) Modify(L,R,mid+1,r,v,x<<1|1);
t[x]=t[x<<1]+t[x<<1|1];
return ;
}
SGT Query(int L,int R,int l,int r,int x){
if(L<=l&&R>=r) return t[x];
PushDown(x);int mid=l+r>>1;
if(R<=mid) return Query(L,R,l,mid,x<<1);
if(L>mid) return Query(L,R,mid+1,r,x<<1|1);
return Query(L,R,l,mid,x<<1)+Query(L,R,mid+1,r,x<<1|1);
}
int main(){
read(n),read(m),Build(1,V,root);
for(int i=1;i<=n;i++) read(a[i]),a[i]+=tmp,num[a[i]]++;
for(int i=1+tmp;i<=n+tmp;i++) Modify(i-num[i]+1,i,1,V,1,root);
while(m--){
int p,x;
read(p),read(x);
if(p){
if(a[p]<=n+tmp) Modify(a[p]-num[a[p]]+1,a[p]-num[a[p]]+1,1,V,-1,root);
num[a[p]]--,x+=tmp,num[x]++,a[p]=x;
if(x<=n+tmp) Modify(x-num[x]+1,x-num[x]+1,1,V,1,root);
}
else{
if(x==1) p=n+tmp,Modify(p-num[p]+1,p,1,V,-1,root),tmp--;
else tmp++,p=n+tmp,Modify(p-num[p]+1,p,1,V,1,root);
}
SGT Ans=Query(1+tmp,n+tmp,1,V,root);
if(Ans.Min) puts("0");
else write(Ans.num),putchar('
');
}
return 0;
}