[BJOI2019]删数

拼搏现实的明天。 2023-10-11 05:29 54阅读 0赞

[题目][Link 1]

考虑一个不用修改就能删空的序列长什么样子

设\\(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;
    }

转载于:https://www.cnblogs.com/asuldb/p/11533331.html

[Link 1]: https://www.luogu.org/problem/P5324