题解：很容易发现这样的一个规律：设i出现的次数为cnt[i]，然后覆盖[i-cnt[i]+1,i]这段，空白的部分就是所求的答案。
但我开始根据这个规律写了个错误的O(n)做法，就是直接差分加减，考虑全部覆盖，这样显然是错的！为什么？原因很简单：只有i值在[1,n]内的cnt[i]才能覆盖答案！我的差分做法没有考虑到，还调了半年。
但很容易把它转化成O(nlogn)的线段树，记录一个数组cur，表示当前所求的值的初始位置在[cur+1,cur+n]，每次±1时，只需要平移一次即可，然后用线段树维护区间最小值、最小值出现次数即可，因为很容易发现不存在答案小于0的位置。
#include<bits/stdc++.h> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int N=601000; int n,m,cur,all,a[N],c[N],mn[N<<2],num[N<<2],ans[N<<2],lazy[N<<2]; void pushup(int rt) { mn[rt]=min(mn[rt<<1],mn[rt<<1|1]); num[rt]=(mn[rt]==mn[rt<<1]?num[rt<<1]:0)+(mn[rt]==mn[rt<<1|1]?num[rt<<1|1]:0); ans[rt]=mn[rt]?0:num[rt]; } void build(int l,int r,int rt) { if(l==r){num[rt]=ans[rt]=1;return;} int mid=l+r>>1; build(lson),build(rson); pushup(rt); } void modify(int rt,int v){lazy[rt]+=v,mn[rt]+=v,ans[rt]=mn[rt]?0:num[rt];} void pushdown(int rt) { if(!lazy[rt])return; modify(rt<<1,lazy[rt]),modify(rt<<1|1,lazy[rt]); lazy[rt]=0; } void update(int L,int R,int v,int l,int r,int rt) { if(L<=l&&r<=R){modify(rt,v);return;} pushdown(rt); int mid=l+r>>1; if(L<=mid)update(L,R,v,lson); if(R>mid)update(L,R,v,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R)return ans[rt]; pushdown(rt); int mid=l+r>>1,ret=0; if(L<=mid)ret+=query(L,R,lson); if(R>mid)ret+=query(L,R,rson); return ret; } void change(int x,int v) { int k=c[x]+(v>0);c[x]+=v; if(x>cur&&x<=cur+n)update(x-k+1,x-k+1,v,1,all,1); } int main() { scanf("%d%d",&n,&m); cur=m+n,all=2*(m+n); build(1,all,1); for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]+=cur,c[a[i]]++; for(int i=1;i<=n;i++) if(c[cur+i])update(cur+i-c[cur+i]+1,cur+i,1,1,all,1); while(m--) { int p,x;scanf("%d%d",&p,&x); if(p>0)change(a[p],-1),a[p]=cur+x,change(a[p],1); else if(x==1) { int pos=cur+n; if(c[pos])update(pos-c[pos]+1,pos,-1,1,all,1); if(c[cur])update(cur-c[cur]+1,cur,1,1,all,1); cur--; } else{ cur++; int pos=cur+n; if(c[cur])update(cur-c[cur]+1,cur,-1,1,all,1); if(c[pos])update(pos-c[pos]+1,pos,1,1,all,1); } printf("%d ",query(cur+1,cur+n,1,all,1)); } }