P5324 题解
E_huan
·
·
题解
转换题意+线段树
前言：做法是学习洛谷题解区枫林晚大佬的，补充了一些内容，用自己的理解和表述写了这篇题解，希望能讲清楚。
题目的描述显然不能直接维护，首先肯定是要找到删空的充要条件，然后才能考虑维护。
结论：
数字 i 有 cnt[i] 个，则覆盖区间 [i-cnt[i]+1,i]，那么答案就是 [1,n] 中未被覆盖的个数。
证明：
$2$. 可以构造出取等号的方案。总数是 $n$，那么有 $k$ 个空位，就必然有 $k$ 个重叠或不在该范围的位置。把这些数改到空位上后一定能把空位填满。
#### 操作：
$1$. 单点修改就是删除原本的贡献，加上新的贡献。
细节上注意修改的点是否在当前的 $[start+1,up]$ 之中，如果不在就不修改
。（因为当 $i$ 不在这个范围的时候，可能 $(i-cnt[i]+1)$ 会在，但其实它的贡献是不能算的，回到题目本身的意思就可以理解），还有增加减少改变的是 $cnt[i]$，所以修改的位置是 $(i-cnt[i]+1)$ 不是 $i$。
$2$. 区间 $+1/\!-\!1$ 其实就是把前面说的覆盖区间全部向右平移。
平移可以通过维护一个变量（可以理解成全局懒标记）实现，用变量 $start$ 维护，表示查询的是 $[start+1,up]$ 中 $0$ 的个数。每次区间 $+1$ 就是 $start-1$，区间 $-1$ 就是 $start+1$，细节上注意 $start$ 初值不是 $0$，否则没有减的空间。此外，每次改变 $start$ 就会有一个数移出或移入边界（只需要考虑不让 $i>up$ 造成贡献，因为 $i < start+1$ 的情况 $[i-cnt[i]+1,i]$ 一定不会有贡献，全会在 $start+1$ 左边），所以需要修改 $[up+cnt[up]+1,up]$。
$3$. 查询就查询 $[start+1,up]$ 中 $0$ 的个数即可。
#### 维护：
这些操作都可以用线段树来维护，具体见代码（有注释）。
#### 代码：
``` cpp
#include<bits/stdc++.h>
using namespace std;
#define up start+n
const int N1=150010,N2=N1*3+10;
//注意是3倍，本身start+/-是两倍(向上n向下n)，但是区间是[(i-cnt[i]+1),i]，当i=1的时候还可以向前n的长度，所以是3倍
inline int read()
{
int res=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
res=res*10+ch-'0';
ch=getchar();
}
return res*f;
}
int n,m,start=N1,a[N1];
int cnt[N2];
struct node
{
int cnt0;//0的个数，即答案
int add;//加法懒标记
int mn;//最小值，辅助求出0的个数（最小值>=0,如果是0它的个数就是答案）
int cnt_mn;//最小值个数
//需要求出最小值和最小值个数是因为会有懒标记，不知道这两个值的话一旦有add的修改就可能不能在不递归的情况下求出cnt0
}tr[N2<<2];
inline void pushup(int u)
{
tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
tr[u].cnt_mn=0;
if(tr[u].mn==tr[u<<1].mn) tr[u].cnt_mn=tr[u<<1].cnt_mn;
if(tr[u].mn==tr[u<<1|1].mn) tr[u].cnt_mn+=tr[u<<1|1].cnt_mn;
tr[u].cnt0=tr[u<<1].cnt0+tr[u<<1|1].cnt0;
}
inline void Add(int u,int v)
{
tr[u].mn+=v;
tr[u].add+=v;
tr[u].cnt0=(tr[u].mn==0)?tr[u].cnt_mn:0;
}
inline void pushdown(int u)
{
if(!tr[u].add) return;
Add(u<<1,tr[u].add); Add(u<<1|1,tr[u].add);
tr[u].add=0;
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={1,0,0,1};
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int ml,int mr,int v)
{
if(ml<=l&&r<=mr) {Add(u,v); return;}
pushdown(u);
int mid=(l+r)>>1;
if(ml<=mid) modify(u<<1,l,mid,ml,mr,v);
if(mr>mid) modify(u<<1|1,mid+1,r,ml,mr,v);
pushup(u);
}
int query(int u,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return tr[u].cnt0;
pushdown(u);
int mid=(l+r)>>1,res=0;
if(ql<=mid) res=query(u<<1,l,mid,ql,qr);
if(qr>mid) res+=query(u<<1|1,mid+1,r,ql,qr);
return res;
}
int main()
{
build(1,1,N1*3);//初始全是0，所以要build()来初始化cnt0
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read()+start,cnt[a[i]]++;
for(int i=start+1;i<=up;i++)
if(cnt[i])
modify(1,1,N1*3,i-cnt[i]+1,i,1);
while(m--)
{
int p=read(),x=read();
if(p)
{
if(a[p]<=up) modify(1,1,N1*3,a[p]-cnt[a[p]]+1,a[p]-cnt[a[p]]+1,-1);
cnt[a[p]]--;
a[p]=start+x;//!!!start+x not x
cnt[a[p]]++;
if(a[p]<=up) modify(1,1,N1*3,a[p]-cnt[a[p]]+1,a[p]-cnt[a[p]]+1,1);
}//注意这里是单点修改，因为cnt[]只变化了1
else
{
if(x==1)
{
if(cnt[up])
modify(1,1,N1*3,up-cnt[up]+1,up,-1);
start--;
}
else
{
start++;
if(cnt[up])
modify(1,1,N1*3,up-cnt[up]+1,up,1);
}
}
printf("%d\n",query(1,1,N1*3,start+1,start+n));
}
return 0;
}
```