题意：
对于任意一个数列，如果能在有限次进行下列删数操作后将其删为空数列，则称这个数列可以删空。一次删数操作定义如下：
- 记当前数列长度为$k$，则删掉数列中所有等于$ k $的数。
现有一个长度为$ n $的数列$ a$，有$ m $次修改操作，第$ i $次修改后你要回答：
经过$ i $次修改后的数列$ a$，至少还需要修改几个数才可删空？
每次修改操作为单点修改或数列整体加一或数列整体减一。
$n,mleq 150000$。
题解：
发现数列$a$只在修改的时候有用，于是先把所有数转到值域上。
一个东西能删成空数列的条件不太明显，我们先想一些直观的做法。
考虑怎么暴力：设$dp(i)$表示将$[1,i]$修改成能删空序列的最小修改次数，那么有$dp(i)=dp(j)+max(i-j-cnt_{i},0)$。
虽然$[1,i]$不一定有$i$个数，但将不在该值域中的数修改到$[1,j]$里的次数已经计算过了，我们实际上只需要用$cnt_{i}$把$[j+1,i]$铺满。
而且不需要考虑用$j+1leq kleq i$的$cnt_{k}$来铺，因为如果它更优，那么在$dp(k)$处已经转移过去了。
这样可以获得47分（我记得我去年是这么写的，为什么获得了0分呢？QAQ）
发现这个东西实际上就相当于有若干条$[i-cnt_{i}+1,i]$的线段覆盖$[1,n]$，需要修改的数目就是没有被覆盖的位置数。
证明：首先每次修改相当于一个点$-1$，一个点$+1$，那么答案下界就是没被覆盖的位置数，而每次选择有重复的结尾位置$-1$即可构造出一组达到下界的解。
如果没有区间修改的话可以用线段树维护这个东西，但区间修改相当于支持平移操作，没法直接维护。
正难则反，我们考虑不将原区间平移，而是用lazy标记的思想将询问区间平移。区间加向左平移，区间减向右平移。
注意可能平移到负数，所以值域需要加$n+m$，在单点修改的时候也要考虑平移的增量。
复杂度$O(mlog {n+m})$。
套路：
- dp时某些状态实际上不能满足条件$ ightarrow$dp时所考虑的范围可以超出实际的范围。
- 与值域有关的问题$ ightarrow$在数轴上立体建模。
代码：
#include<bits/stdc++.h> #define maxn 600005 #define maxm 150000 #define inf 0x7fffffff #define ll long long #define mp make_pair #define pii pair<int,int> #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; int A[maxn<<4],cnt[maxn<<4],mn[maxn<<4],mnc[maxn<<4],lz[maxn<<4]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void pushup(int k){ if(mn[k<<1]==mn[k<<1|1]) mn[k]=mn[k<<1],mnc[k]=mnc[k<<1]+mnc[k<<1|1]; else if(mn[k<<1]<mn[k<<1|1]) mn[k]=mn[k<<1],mnc[k]=mnc[k<<1]; else mn[k]=mn[k<<1|1],mnc[k]=mnc[k<<1|1]; } inline void pushdown(int k){ if(lz[k]){ lz[k<<1]+=lz[k],lz[k<<1|1]+=lz[k]; mn[k<<1]+=lz[k],mn[k<<1|1]+=lz[k],lz[k]=0; } } inline void add(int x,int y,int z,int l,int r,int k){ if(x<=l && r<=y){lz[k]+=z,mn[k]+=z;return;} pushdown(k); int mid=l+r>>1; if(x<=mid) add(x,y,z,l,mid,k<<1); if(y>mid) add(x,y,z,mid+1,r,k<<1|1); pushup(k); } inline void build(int l,int r,int k){ mn[k]=lz[k]=0,mnc[k]=r-l+1; if(l==r) return; int mid=l+r>>1; build(l,mid,k<<1),build(mid+1,r,k<<1|1); } inline pii merge(pii a,pii b){ if(a.first==b.first) return mp(a.first,a.second+b.second); else if(a.first<b.first) return a; else return b; } inline pii qry(int x,int y,int l,int r,int k){ if(x<=l && r<=y) return mp(mn[k],mnc[k]); pushdown(k); int mid=l+r>>1; pii res=mp(inf,0); if(x<=mid) res=merge(res,qry(x,y,l,mid,k<<1)); if(y>mid) res=merge(res,qry(x,y,mid+1,r,k<<1|1)); pushup(k); return res; } int main(){ int n=read(),m=read(),t=(n+m),p0=t; for(int i=1;i<=n;i++) A[i]=read()+t,cnt[A[i]]++; build(1,2*t,1); for(int i=1;i<=2*t;i++) if(cnt[i]) add(i-cnt[i]+1,i,1,1,2*t,1); while(m--){ int p=read(),x=read(); if(!p){ if(x>0){int pp=p0+n;p0--;if(cnt[pp])add(pp-cnt[pp]+1,pp,-1,1,2*t,1);} else{p0++;int pp=p0+n;if(cnt[pp])add(pp-cnt[pp]+1,pp,1,1,2*t,1);} } else{ int pp=A[p]; A[p]=x+p0; if(pp<=p0+n) add(pp-cnt[pp]+1,pp-cnt[pp]+1,-1,1,2*t,1); cnt[pp]--; if(A[p]<=p0+n) add(A[p]-cnt[A[p]],A[p]-cnt[A[p]],1,1,2*t,1); cnt[A[p]]++; } pii res=qry(p0+1,p0+n,1,2*t,1); if(res.first!=0) printf("%d ",0); else printf("%d ",res.second); } return 0; }