P4119 [Ynoi2018] 未来日记
Utilokasteinn
·
·
题解
Link
题目大意：
给定一个长度为 n 的序列 a，进行 m 次操作，分两种：
-
将区间 [l,r] 中所有 x 变成 y。
-
查询区间 [l,r] 中的第 k 小值。
数据保证 1\le n,m,a_i\le 10^5。
前置知识：数列分块，值域分块，并查集。
令 A=\max_{i=1}^{n}a_i。
似乎可以用树套树实现。但是 O(m\log^2n\log A) 显然是过不去的。考虑分块。
观察数据范围，发现值域很小，只有 10^5，可以在值域上做文章。
我们将序列和值域都分块，假定块长分别为 \sqrt{n} 和 \sqrt{A}。
设 pos_i 表示 a_i 所在的块，belong_i 表示数字 i 所在的块。再设 L_i,R_i,L'_i,R'_i 分别表示在序列和值域中第 i 块的左右端点。
将以上信息预处理，时间复杂度 O(n+A)。
代码：
n=read(),m=read();
for(int i=1;i<=n;++i)
a[i]=read(),fa[i]=i,maxv=max(maxv,a[i]);
len1=sqrt(n),block1=n/len1;
len2=sqrt(maxv),block2=maxv/len2;
for(int i=1;i<=block1;++i)
L[i]=R[i-1]+1,R[i]=i*len1;
R[block1]=n;
for(int i=1;i<=block1;++i)
for(int j=L[i];j<=R[i];++j)
pos[j]=i;
for(int i=1;i<=block2;++i)
LL[i]=RR[i-1]+1,RR[i]=i*len2;
RR[block2]=maxv;
for(int i=1;i<=block2;++i)
for(int j=LL[i];j<=RR[i];++j)
belong[j]=i;
通过值域分块来求区间第 k 小值相信大家都会。在值域中，先枚举整块直到个数大于等于 k，然后再枚举该块中的每个数，知道个数大于等于 k，此时的那个数就是答案。
所以，要先预处理出 cnt_{i,j},ans_{i,j} 以及 all_{i,j}。
$ans_{i,j}$ 表示前 $i$ 块中值为 $j$ 的数的个数。
$all_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块的数的个数。
时间复杂度 $O(n+A\sqrt{n})$。
再考虑如何维护块内相同的数。
设 $root_{i,j}$ 表示在第 $i$ 块中值为 $j$ 的数第一次出现的位置。若没有出现则为 $0$。
可以用并查集维护。在第 $i$ 块中，将所有值为 $j$ 的数的 $fa$ 都指向 $root_{i,j}$。$fa_j$ 表示在 $a_j$ 所在的块 $i$ 中，第一个值为 $a_j$ 的数的位置。
预处理 $root$ 和 $fa$，时间复杂度 $O(n)$。
代码：
```cpp
for(int i=1;i<=block1;++i)
{
for(int j=L[i];j<=R[i];++j)
{
if(!root[i][a[j]])root[i][a[j]]=j;
else fa[j]=root[i][a[j]];
++cnt[i][a[j]],++all[i][belong[a[j]]];
}
for(int j=1;j<=maxv;++j)
ans[i][j]=ans[i-1][j]+cnt[i][j];
for(int j=1;j<=block2;++j)
all[i][j]+=all[i-1][j];
}
```
故所有预处理的时间复杂度为 $O(n+A\sqrt{n})$。
------------
对于将区间 $[l,r]$ 的所有 $x$ 变成 $y$，考虑分块修改。
令 $p=pos_l,q=pos_r$。设函数 ```update(l,r,x,y,p)``` 表示将块 $p$ 中区间 $[l,r]$ 的所有 $x$ 变成 $y$，保证 $l$ 和 $r$ 在块 $p$ 中。
若 $p=q$，直接 ```update(l,r,x,y,p)``` 即可。
若 $p\not=q$，则将区间 $[l,r]$ 分为三部分。先修改左右的散块，再修改中间的整块。即直接 ```updagte(l,R[p],x,y,p)``` 再 ```update(L[q],r,x,y,q)```，最后再修改整块。
------------
### 整块修改
因为有并查集，所以我们只需要修改块内第一个出现的 $x$。之后我们查询 $a_i$ 的值时，只需要调用 $a_{find(i)}$。
若当前修改块 $i$。
若块内没有 $x$，直接跳过并查集的部分。
若块内有 $x$ 无 $y$，就把 $a_{root_{i,x}}$ 赋值为 $y$，然后将 $root_{i,y}$ 赋值为 $root_{i,x}$ 即可。
若块内有 $x$ 有 $y$，就直接将 $root_{i,x}$ 链到 $root_{i,y}$ 上，也就是 $fa_{root_{i,x}}=root_{i,y}$。
在修改完之后，还要维护 $cnt,ans$ 和 $all$ 数组。
注意，当块 $p+1$ 到块 $q-1$ 修改完后，还要修改块 $q$ 和之后的块的 $ans$ 和 $all$ 数组。
时间复杂度 $O(\sqrt{n})$。
------------
### 散块修改
散块修改即 ```update(l,r,x,y,p)```，暴力重构并查集即可。
我们先将表示 $x$ 和 $y$ 的两个并查集清空，即 $root_{p,x}=root_{p,y}=0$。
然后，我们开一个数组，把 $L_p$ 和 $R_p$ 中的所有 $x$ 和 $y$ 的位置都存进去。接着，直接将区间 $[l,r]$ 为 $x$ 的数赋为 $y$。并记录修改了几个数，设为 $res$。
然后就可以暴力重构并查集了。
最后还要记得维护块 $p$ 的 $cnt$ 数组，以及块 $p$ 和之后的块的 $ans$ 和 $all$ 数组。
时间复杂度 $O(\sqrt{n})$。
代码：
```cpp
inline void update(int l,int r,int x,int y,int p)
{
int res=0,top=0;
root[p][x]=root[p][y]=0;
for(int i=L[p];i<=R[p];++i)
{
a[i]=a[find(i)];
if(a[i]==x||a[i]==y)
st[++top]=i;
}
for(int i=l;i<=r;++i)
if(a[i]==x)a[i]=y,++res;
for(int i=1,ps,val;i<=top;++i)
{
ps=st[i],val=a[ps];
if(!root[p][val])root[p][val]=ps;
fa[ps]=root[p][val];
}
cnt[p][x]-=res,cnt[p][y]+=res;
for(int i=p;i<=block1;++i)
{
ans[i][x]-=res,ans[i][y]+=res;
if(belong[x]!=belong[y])
all[i][belong[x]]-=res,all[i][belong[y]]+=res;
}
}
```
------------
### 区间查询
现在我们要查询区间 $[l,r]$ 内第 $k$ 小的数。
设 $p=pos_l,q=pos_r$。
开一个桶 $t$ 记录散块内每个数的个数，再开一个桶 $sum$ 记录散块内值在块 $j$ 的数的个数。
时间复杂度 $O(\sqrt{n})$。
```cpp
for(int i=l;i<=R[p];++i)
{
a[i]=a[find(i)];
++t[a[i]],++sum[belong[a[i]]];
}
for(int i=L[q];i<=r;++i)
{
a[i]=a[find(i)];
++t[a[i]],++sum[belong[a[i]]];
}
```
然后枚举值域块，从第一个块开始往后，$res$ 每次加上值在当前块内的的个数，若 $res\ge k$，则说明答案在当前块内。减去当前块 $i$ 内的个数。
从 $L'_i$ 开始枚举 $j$，若 $res+t_j\ge k$，则说明 $j$ 为第 $k$ 小的数，清空桶然后返回。
时间复杂度 $O(\sqrt{A})$。
```cpp
for(int i=1;i<=block2;++i)
{
res+=sum[i]+all[q-1][i]-all[p][i];
if(res>=k)
{
res-=sum[i]+all[q-1][i]-all[p][i];
for(int j=LL[i];j<=RR[i];++j)
if((res+=t[j]+ans[q-1][j]-ans[p][j])>=k)
{
for(int u=l;u<=R[p];++u)
t[a[u]]=sum[belong[a[u]]]=0;
for(int u=L[q];u<=r;++u)
t[a[u]]=sum[belong[a[u]]]=0;
return j;
}
}
}
```
单次查询的时间复杂度为 $O(\sqrt{n}+\sqrt{A})$。
------------
代码的时间复杂度为 $O(m(\sqrt{n}+\sqrt{A})+n)$。
不知道是我人傻常数大还是什么，别人块长 $\sqrt{n}$ 可以稳过，我会 T 两个点……
经过数个小时的调整块长以及卡常，我的代码最终在块长为 $420$ 的情况下，以最大点 $998ms$ 的时间通过该题……
[评测记录](https://www.luogu.com.cn/record/68853717)。
[AC Code](https://www.luogu.com.cn/paste/1sena9ca)。