自动搬运

查看原文

来自洛谷，原作者为

	枫林晚 **

搬运于2025-08-24 22:09:34，当前版本为作者最后更新于2019-04-24 19:49:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

%%yyb

这里说详细一些

推性质+猜结论

考虑没有修改。如何快速算出。再数据结构维护修改什么的

显而易见的是，答案和数列的顺序无关，只和出现的数有关

如果开一个桶，把每个数摞成若干个柱子，然后往左推倒，那么答案就是[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

#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*
*/