考虑一个不用修改就能删空的序列长什么样子
设\(cnt_i\)表示\(i\)出现的次数，我们可以视为在\(i\)位置有一根高度为\(cnt_i\)的柱子，我们把所有柱子像左边推到，如果这些柱子恰好能覆盖\([1,n]\)这个区间，那么就说明可以删空
这样想想发现非常形象，一次删除操作就相当于把当前最右边的柱子推倒，柱子顶端落地的位置就相当于新的序列的长度
如果不能覆盖\([1,n]\)这个区间，那么就说明有的地方被多次覆盖了，我们只需要把那些多次覆盖的地方给到没有覆盖的地方就行了，所以\([1,n]\)内没有被覆盖到的个数就是使得这个序列能够删空的最小修改次数
这样单点修改就比较好做了，就是修改一下两个柱子的高度，求\([1,n]\)里被覆盖次数为\(0\)的个数，随便维护一下即可
对于整体\(+1,-1\)操作，维护一个整体偏移量\(L,R\)，即当前要覆盖的区间，我们求一下\([L,R]\)这个区间里\(0\)的个数，单点修改时也把修改的值变成当前偏移量下的值
但是现在我们只能推倒\(i\in [L,R]\)内的柱子，对于\(i>R\)但是\(i-cnt_i+1<=R\)这样的柱子尽管能对\([L,R]\)产生覆盖但是这样的覆盖显然不能算，于是我们需要在移动\(L,R\)的时候把加入一根柱子，删除一根柱子
这就相当于区间\(+1,-1\)，询问区间内\(0\)的个数
这一看就不会做了，怎么着也得分块吧，但考虑到不会有地方变成负数，所以我们用线段树维护一下区间最小值，区间最小值出现次数就能维护了
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0,r=1;
while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x*r;
}
const int maxn=6e5+5;
int l[maxn<<2],r[maxn<<2],tag[maxn<<2],mn[maxn<<2],d[maxn<<2];
inline void pushshr(int x,int v) {tag[x]+=v,mn[x]+=v;}
inline void pushdown(int x) {
if(!tag[x]) return;
pushshr(x<<1,tag[x]);
pushshr(x<<1|1,tag[x]);
tag[x]=0;
}
void build(int x,int y,int i) {
l[i]=x,r[i]=y;mn[i]=0;d[i]=r[i]-l[i]+1;
if(x==y) return;
int mid=x+y>>1;
build(x,mid,i<<1),build(mid+1,y,i<<1|1);
}
void change(int x,int y,int i,int v) {
if(x>y) return;
if(x<=l[i]&&y>=r[i]) {pushshr(i,v);return;}
pushdown(i);int mid=l[i]+r[i]>>1;
if(x<=mid) change(x,y,i<<1,v);
if(y>mid) change(x,y,i<<1|1,v);
mn[i]=min(mn[i<<1],mn[i<<1|1]);d[i]=0;
if(mn[i]==mn[i<<1]) d[i]+=d[i<<1];
if(mn[i]==mn[i<<1|1]) d[i]+=d[i<<1|1];
}
int query(int x,int y,int i) {
if(x>y) return 0;
if(x<=l[i]&&y>=r[i]) return !mn[i]?d[i]:0;
pushdown(i);
int mid=l[i]+r[i]>>1,now=0;
if(x<=mid) now+=query(x,y,i<<1);
if(y>mid) now+=query(x,y,i<<1|1);
return now;
}
int n,m,a[maxn],b[maxn],pre[maxn],L,R;
int main() {
n=read(),m=read();L=1+m,R=n+m;
build(1,n+n+m+m,1);int pos,x;
for(re int i=1;i<=n;i++) a[i]=read()+m,b[a[i]]++;
for(re int i=L;i<=R;++i) change(i-b[i]+1,i,1,1);
while(m--) {
pos=read(),x=read();
if(pos) {
int t=L+x-1;
if(a[pos]>=L&&a[pos]<=R) {
change(a[pos]-b[a[pos]]+1,a[pos],1,-1);
b[a[pos]]--;
change(a[pos]-b[a[pos]]+1,a[pos],1,1);
}else b[a[pos]]--;
change(t-b[t]+1,t,1,-1);
b[t]++;
change(t-b[t]+1,t,1,1);
a[pos]=t;
}
else {
if(x==1)
change(R-b[R]+1,R,1,-1),R--,L--,change(L-b[L]+1,L,1,1);
else change(L-b[L]+1,L,1,-1),L++,R++,change(R-b[R]+1,R,1,1);
}
printf("%d\n",query(L,R,1));
}
return 0;
}