题解 P5324 【[BJOI2019] 删数】

[%%yyb](https://www.cnblogs.com/cjyyb/p/10750238.html#4238627) 这里说详细一些 **推性质+猜结论** 考虑没有修改。如何快速算出。再数据结构维护修改什么的 显而易见的是，答案和数列的顺序无关，只和出现的数有关 如果开一个桶，把每个数摞成若干个柱子，然后往左推倒，那么答案就是[1,n]中未被覆盖的个数。 证明： 1.首先这是答案的下界。对于一个空位，比它大的柱子删掉之后不能跨越它，比它小的柱子又不能提前删掉。所以必须变动一个数使得这里被遮盖上。 2.可以构造出至少一种方案达到这个下界。总数是n，那么有k个空位，就必然有k个重叠的位置。把这些柱子消掉一些，放到空位上，显然没有问题。 考虑维护 1.只有p>0，就是单点高度修改了，用个桶就可以O(m)做 2.还有p=0的整体操作，发现，就是查询区间进行了平移！用一个变量st记录当前0的位置，移动时候直接--st或者++st 用线段树维护每个点被覆盖的情况 但是，当一个柱子没有落到[st+1,st+n]的区间上，并且>st+n，这样的柱子并不能贡献覆盖的，一定是之后需要修改的累赘。 所以，当st--时候，对于原来的最右端的位置，把这个位置的柱子对[p-buc+1,p]的贡献减掉1。++st时候还原 线段树维护：区间最小值，最小值出现次数，0的个数，加法标记 这样，查询时候直接区间查询0个数即可 注意，单点修改的时候，也要判断是否<=st+n ```cpp #include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{ const int N=150000*3+10; #define mid ((l+r)>>1) #define ls (x<<1) #define rs (x<<1|1) int n,m; struct node{ int mi,cnt; int ans,ad; }t[4*N]; int a[N],buc[N]; int st,lim; void pushup(int x){ t[x].mi=min(t[ls].mi,t[rs].mi); t[x].cnt=(t[ls].mi==t[x].mi?t[ls].cnt:0)+(t[rs].mi==t[x].mi?t[rs].cnt:0); t[x].ans=t[ls].ans+t[rs].ans; } void tag(int x,int c){ t[x].mi+=c; t[x].ans=(t[x].mi==0)?t[x].cnt:0; t[x].ad+=c; } void pushdown(int x){ if(t[x].ad){ tag(ls,t[x].ad);tag(rs,t[x].ad); t[x].ad=0; } } void build(int x,int l,int r){ if(l==r){ t[x].cnt=1;t[x].ans=1; return; } build(ls,l,mid); build(rs,mid+1,r); pushup(x); } void upda(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ tag(x,c);return; } pushdown(x); if(L<=mid) upda(ls,l,mid,L,R,c); if(mid<R) upda(rs,mid+1,r,L,R,c); pushup(x); } int query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R) return t[x].ans; pushdown(x); if(R<=mid) return query(ls,l,mid,L,R); if(mid<L) return query(rs,mid+1,r,L,R); return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R); } void chan(int x,int c){ int k=x-buc[x]+1-(c>0); upda(1,1,lim,k,k,c); buc[x]+=c; } int main(){ rd(n);rd(m); st=150000+1,lim=450000+5;//开始0位置和线段树上界 build(1,1,lim); for(reg i=1;i<=n;++i){ rd(a[i]);a[i]+=st;chan(a[i],1); } int p,x; while(m--){ rd(p);rd(x); if(p>0){//单点修改 if(a[p]<=st+n){ chan(a[p],-1); }else{//判断是否<=st+n --buc[a[p]]; } a[p]=st+x; if(a[p]<=st+n){ chan(a[p],1); }else{//判断是否<=st+n ++buc[a[p]]; } }else if(x>0){ int pos=st+n; if(buc[pos]) upda(1,1,lim,pos-buc[pos]+1,pos,-1);//清除贡献 --st; }else{ ++st; int pos=st+n; if(buc[pos]) upda(1,1,lim,pos-buc[pos]+1,pos,1);//加上贡献 } printf("%d\n",query(1,1,lim,st+1,st+n)); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */ ```