[DS记录]P4119 [Ynoi2018]未来日记
command_block
·
·
个人记录
大 分 块 开 始 了 。
题意 : 最初分块。
区间替换，区间 kth。
------------
首先来考虑静态的区间 $kth$ 怎么分块。
- 经典的值域分块 :
回忆经典的权值线段树上二分，类似地有权值块状树组上的 $kth$。
记录 $c[x]$ 表示 $x$ 有几个，然后对该数组造一棵三层树 ( $n-\sqrt{n}-1$ ) ，在上面爬的复杂度就是$O(\sqrt{n})$。
接下来我们就是要得知一个区间的权值块状树组。
类似主席树的做法，此处可以差分。
给序列分块。我们可以维护**前缀块**的值域分块，这样差分就能得到**完整块**的值域分块。
然后 $O(\sqrt{n})$ 将散块的信息加入即可。
注意，值域分块的外层块只有 $O(\sqrt{n})$ 的信息，所以写法可以比较暴力。
好现在我们会 $O(n\sqrt{n})$ 的静态区间 $kth$ 了，接着来观察这个 $x\rightarrow y$ 的修改。
显然，其只会更新权值块状树组前缀和中的 $O(\sqrt{n})$ 个位置，可以直接暴力。
对于散块，可以暴力修改 $a$。
( 由于有值域整块前缀和，容易快速判定某个块内是否有 $x$ )
对于整块，若其中无 $x$ ，可以忽略。若无 $y$ ，可以直接将所有的 $x$ 修改成 $y$。
若 $x,y$ 均有，则直接暴力修改。
- 分析暴力重构的次数。
若所有的操作都只涉及整块，某个块内经过 $O(\sqrt{n})$ 次有效合并必然变为纯色。
一次合并的代价，块数也均是 $O(\sqrt{n})$ ，这部分总复杂度就是 $O(\sqrt{n}^3)=O(n\sqrt{n})$。
接下来考虑散块重构造成的影响，其可以把块中的一部分 $x$ 变为 $y$。
不妨直接视为加入一种新的颜色，则最多导致一次新的合并。
由于每次只有两个散块重构，最多导致额外的 $O(m)$ 次合并，复杂度仍然是 $O\big(n\sqrt{n}\big)$。
考虑如何处理 “$x$ 改名为 $y$” 这一操作，可以搞个数组维护映射。
具体地，为了减小常数，我们维护下列三个值 ：
`r1[t][i]` 表示块 $t$ 的第 $i$ 个编号对应的值。
`r2[i]` 表示整个序列的第 $i$ 个位置对应的块内编号。
`tp[t][x]` 表示值 $x$ 在块 $t$ 中的编号。可以用 `short` 存储。
具体修改见代码。
时空复杂度均为 $O(n\sqrt{n})$。
将值域分块数组的值维度放在前面，这能显著提升空间局限性。
将值域分块的第二层分叉数目置为为 $256$ ，这样能利用位运算减小常数。
然后调一个合适的块大小，我选的是 $\sqrt{2n/3}$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MaxN 105000
using namespace std;
const int lim1=400,lim2=100000,bas1=255,bas2=130816;
int BS,r1[405][305],a[MaxN],r2[MaxN];short tp[405][MaxN];
int las[MaxN];
void getre(int t)
{
int tl=t*BS;
for (int i=0;i<BS;i++)las[a[i+tl]]=-1;
for (int i=0;i<BS;i++){
if (las[a[i+tl]]==-1)
tp[t][r1[t][i]=a[i+tl]]=las[a[i+tl]]=i;
r2[i+tl]=las[a[i+tl]];
}
}
int c1[405][405],c2[MaxN][405];
inline void add(int t,int x,int c)
{c1[x>>8][t]+=c;c2[x][t]+=c;}
int Bn;
void gmap(int t)
{
int tl=t*BS,tr=tl+BS;
for (int i=tl;i<tr;i++)
a[i]=r1[t][r2[i]];
}
int st[405];
void chg(int l,int r,int x,int y)
{
if (x==y)return ;
int bl=l/BS,br=r/BS;
if (bl==br){
int c=0;
gmap(bl);
for (int i=l;i<=r;i++)
if (a[i]==x){a[i]=y;c++;}
getre(bl);
for (int i=bl;i<=Bn;i++)
{add(i,x,-c);add(i,y,c);}
return ;
}
gmap(bl);gmap(br);
memset(st,0,sizeof(st));
for (int i=l;i<bl*BS+BS;++i)
if (a[i]==x){a[i]=y;st[bl]++;}
for (int i=br*BS;i<=r;++i)
if (a[i]==x){a[i]=y;st[br]++;}
getre(bl);getre(br);
for (int i=bl+1;i<br;i++){
if (!(st[i]=c2[x][i]-c2[x][i-1]))continue;
if (c2[y][i]-c2[y][i-1]==0){
int u=tp[i][x];
tp[i][r1[i][u]=y]=u;
}else {
gmap(i);
int tl=i*BS,tr=tl+BS;
for (int j=tl;j<tr;++j)
if (a[j]==x)a[j]=y;
getre(i);
}
}
for (int i=bl,buf=0;i<=Bn;i++){
buf+=st[i];
add(i,x,-buf);add(i,y,buf);
}
}
int qry(int l,int r,int k)
{
int bl=l/BS,br=r/BS;
if (bl==br){
int tot=0;gmap(bl);
for (int i=l;i<=r;i++)st[++tot]=a[i];
nth_element(st+1,st+k,st+tot+1);
return st[k];
}
gmap(bl);gmap(br);
for (int i=0;i<=lim1;++i)
st[i]=c1[i][br-1]-c1[i][bl];
for (int i=l;i<bl*BS+BS;++i)++st[a[i]>>8];
for (int i=br*BS;i<=r;++i)++st[a[i]>>8];
int ans;
for (int i=0;i<=lim1;++i)
if (k>st[i])k-=st[i];
else {ans=i<<8;break;}
for (int i=0;i<=bas1;++i)
st[i]=c2[ans|i][br-1]-c2[ans|i][bl];
for (int i=l;i<bl*BS+BS;++i)
if ((a[i]&bas2)==ans)++st[a[i]&bas1];
for (int i=br*BS;i<=r;++i)
if ((a[i]&bas2)==ans)++st[a[i]&bas1];
for (int i=0;i<=bas1;++i){
if (k>st[i])k-=st[i];
else return ans|i;
}
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
BS=sqrt(n*2/3)+1;Bn=(n-1)/BS;
for (int i=0;i<n;i++){
scanf("%d",&a[i]);
add(i/BS,a[i],1);
}
getre(0);
for (int i=1;i<=Bn;i++)getre(i);
for (int j=0;j<=lim1;j++)
for (int i=1;i<=Bn;i++)
c1[j][i]+=c1[j][i-1];
for (int j=0;j<=lim2;j++)
for (int i=1;i<=Bn;i++)
c2[j][i]+=c2[j][i-1];
for (int i=0,op,l,r,x,y;i<m;++i){
scanf("%d%d%d%d",&op,&l,&r,&x);
l--;r--;
if (op==1){
scanf("%d",&y);
chg(l,r,x,y);
}else printf("%d\n",qry(l,r,x));
}return 0;
}
```
[评测记录](https://www.luogu.com.cn/record/46719225) （常数较大）