枫林晚
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*
*/