题目

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

\(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;
}
02-10 06:30