题目：https://loj.ac/problem/3094
弱化版是 AGC017C 。
用线段树维护那个题里的序列即可。
对应关系大概是：
真实值的范围是 [ 1-m , n+m ] ；考虑设偏移量 fx ，使得 a[ i ]+fx 是真实值。如果整体 +1 ，就 fx+1 。
因为要记录每个值的个数，所以 a[ i ] 最好都是非负的。那么令 fx 的初值是 -m ，a[ i ] 的最小值是 “最小的真实值 - fx ”，就是 1-m+m 了。
已经有了 a[ ] 的范围是 [ 1 , n+2*m ] 。考虑其个数 cnt ，覆盖的范围就是 [ 1-n , n+2*m ] 。所以令 fx2=n ， a[ ] 加上 fx2 对应到线段树角标即可。
注意如果是在 [ 1 , n ] 之外的值带来的覆盖，不应该考虑。因为覆盖是在值的左边，所以只需要管 >n 的值对 [ 1 , n ] 的影响。因为 n 每次最多移动 1 的位置，所以可以维护。
如果是 >n 的值因为单点修改而使得 [ 1 , n ] 的位置上的值改变，也应该忽略，只修改 “值等于该值的元素个数” 即可。
原来维护了 “区间里 0 的个数” 。这样无法应对区间减。考虑到如果需要 “区间1的个数” ，那么此时区间里一定没有 0 ，所以（看题解）想到维护区间最小值的个数即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mn(int a,int b){return a<b?a:b;}
const int N=,N2=N*,M=N*;
int n,m,a[N],tp[N2],fx,fx2,lm;
int tot,Ls[M],Rs[M],tg[M];
struct Node{
int mn,ct;
Node(int m=,int c=):mn(m),ct(c) {}
Node operator+ (const Node &b)const
{
int tmn=Mn(mn,b.mn),tct=;
if(mn==tmn)tct+=ct; if(b.mn==tmn)tct+=b.ct;
return Node(tmn,tct);
}
}vl[M];
void build(int l,int r,int cr)
{
vl[cr].mn=; vl[cr].ct=r-l+;
if(l==r)return; int mid=l+r>>;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
}
void pshd(int cr)
{
if(!tg[cr])return; int w=tg[cr]; tg[cr]=;
tg[ls]+=w; tg[rs]+=w; vl[ls].mn+=w; vl[rs].mn+=w;
}
void mdfy(int l,int r,int cr,int L,int R,int k)
{
if(l>=L&&r<=R){ tg[cr]+=k; vl[cr].mn+=k; return;}
int mid=l+r>>; pshd(cr);
if(L<=mid)mdfy(l,mid,ls,L,R,k);
if(mid<R)mdfy(mid+,r,rs,L,R,k);
vl[cr]=vl[ls]+vl[rs];
}
Node qry(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)return vl[cr];
int mid=l+r>>; pshd(cr);
if(R<=mid)return qry(l,mid,ls,L,R);
if(mid<L)return qry(mid+,r,rs,L,R);
return qry(l,mid,ls,L,R)+qry(mid+,r,rs,L,R);
}
int main()
{
n=rdn();m=rdn(); fx=-m; fx2=n; lm=n+m-fx+fx2;
for(int i=;i<=n;i++)
{ a[i]=rdn()-fx; tp[a[i]]++;}
tot=; build(,lm,);
for(int i=;i<=n;i++)
{
int k=i-fx;
if(tp[k]) mdfy(,lm,,k-tp[k]++fx2,k+fx2,);
}
for(int i=,x,y;i<=m;i++)
{
x=rdn(); y=rdn();
if(x>)
{
int d=a[x]-tp[a[x]]+;
if(a[x]<=n-fx) mdfy(,lm,,d+fx2,d+fx2,-);
tp[a[x]]--;
a[x]=y-fx; tp[a[x]]++; d=a[x]-tp[a[x]]+;
if(a[x]<=n-fx) mdfy(,lm,,d+fx2,d+fx2,);
}
else
{
if(y==)
{
int k=n-fx; fx++;
if(tp[k]) mdfy(,lm,,k-tp[k]++fx2,k+fx2,-);
}
else
{
fx--; int k=n-fx;
if(tp[k]) mdfy(,lm,,k-tp[k]++fx2,k+fx2,);
}
}
Node tp=qry(,lm,,-fx+fx2,n-fx+fx2);
if(tp.mn>)tp.ct=; printf("%d\n",tp.ct);
}
return ;
}