【BJOI2019】删数线段树

题目大意：一个数列若能在有限次数内删空，则称这个数列可以删空，一次删除操作定义如下：

记当前数列长度为$k$，则删掉数列中所有等于$k$的数。

现在有一个长度为$n$的数列$a$，有$m$次修改操作，为单点变值/整体增加或者减少$1$，问每次修改后，最少需要修改序列中多少个数，使得序列可以被删除。

数据范围：$n≤150000$。

我们首先考虑下最少需要修改的次数，我们设$b[i]$为数列$a$中填写了i的值得数量。

对于每一个$i$，我们可以用$b[i]$这么多数，覆盖区间$[i-b[i]+1,i]$。最终的答案就是未被覆盖的格子数量。

证明显然。

基于这个结论，我们就可以在$O(n)$的复杂度内求出一个序列$a$对应的答案，可以获得47分的好成绩。

在只有单点修改的情况下，我们发现我们可以用线段树做一下维护，就可以获得60分的好成绩。

我们发现，整体的$+1$或者$-1$，可以转化为查询的区间出现了移动，移动完查询区间后，我们更新一下两端的值即可。

这么搞就可以过掉这一题了。

时间复杂度：$O(n\log\ n)$。

 #include<bits/stdc++.h>

 #define M (1<<19)

 using namespace std;

 struct seg{int l,r,tag,minn,cnt;}a[M<<];

 void pushup(int x){

     a[x].minn=min(a[x<<].minn,a[x<<|].minn);

     a[x].cnt=(a[x].minn==a[x<<].minn?a[x<<].cnt:)+(a[x].minn==a[x<<|].minn?a[x<<|].cnt:);

 }

 void upd(int x,int k){a[x].minn+=k; a[x].tag+=k;}

 void pushdown(int x){if(a[x].tag) upd(x<<,a[x].tag),upd(x<<|,a[x].tag); a[x].tag=;}

 void build(int x,int l,int r){

     a[x].l=l; a[x].r=r; if(l==r) return void(a[x].cnt=);

     int mid=(l+r)>>;

     build(x<<,l,mid); build(x<<|,mid+,r);

     pushup(x);

 }

 void updata(int x,int l,int r,int k){

     if(l<=a[x].l&&a[x].r<=r) return upd(x,k);

     pushdown(x); int mid=(a[x].l+a[x].r)>>;

     if(l<=mid) updata(x<<,l,r,k);

     if(mid<r) updata(x<<|,l,r,k);

     pushup(x);

 }

 void updata(int x,int id,int k){return updata(x,id,id,k);}

 int query(int x,int l,int r){

     if(a[x].minn>) return ;

     if(l<=a[x].l&&a[x].r<=r) return a[x].cnt;

     pushdown(x); int mid=(a[x].l+a[x].r)>>,cnt=;

     if(l<=mid) cnt+=query(x<<,l,r);

     if(mid<r) cnt+=query(x<<|,l,r);

     return cnt;

 }

 int num[M],n,q,m,orzorz[M*]={};

 int *cnt=orzorz+M;

 int main(){

     scanf("%d%d",&n,&q);

     for(int i=;i<=n;i++) scanf("%d",num+i),cnt[num[i]]++;

     int T=max(n,q),m=T+n+q+,move=;

     build(,,m);

     for(int i=;i<=n;i++) updata(,T+i-cnt[i]+,T+i,);

     while(q--){

         int p,x; scanf("%d%d",&p,&x);

         if(p>){

             x-=move;

             if(num[p]+move>=&&num[p]+move<=n)

                 updata(,num[p]-cnt[num[p]]++T,-);

             cnt[num[p]]--; num[p]=x; cnt[num[p]]++;

             updata(,num[p]-cnt[num[p]]++T,);

         }else{

             if(x<) move--;

             updata(,-move-cnt[-move]++T,-move+T,x);

             updata(,n-move-cnt[n-move]++T,n-move+T,-x);

             if(x>) move++;

         }

         printf("%d\n",query(,T-move+,T-move+n));

     }

 }

巴特西

【BJOI2019】删数线段树

最新文章

热门文章

巴特西

【BJOI2019】删数 线段树

最新文章

热门文章

【BJOI2019】删数线段树