\(\color{black}{P4119\ [Ynoi2018]\ 未来日记}\)
思路：分块+值域分块
复杂度：\(O(n\sqrt n+m\sqrt n)\)
主题思路
数列分块需要维护：
| \(nid_{i,j}\) | \(fid_i\) | \(f_i\) |
|---|---|---|
| 块 \(i\) 中数字 \(j\) 的并查集的根 | 以 \(i\) 为根的并查集表示的数字 | 并查集 |
值域分块需要维护：
| \(ncnt_{i,j}\) | \(bcnt_{i,j}\) |
|---|---|
| 前 \(i\) 个块数字 \(j\) 的出现次数 | 前 \(i\) 个块中在值域块 \(j\) 中的个数 |
预处理：
- 序列分块、值域分块块长。
- 序列、值域每个值对应块。
- 每个块用 \(nid,fid\) 建立映射，\(f_i\) 连向此块与当前点值相同的第一个值（的下标），若此块中第一次出现当前点值，则考虑对 \(nid,fid\) 赋值。
- 显著地，扫一遍序列同时现将 \(ncnt,bcnt\) 赋上初值，再进行一遍前缀和。
修改：
- 碎块直接暴力赋值暴力重构，记得更新前缀和。
- 整块直接合并 \(x,y\) 两值，若 \(y\) 值不存在则直接将 \(x\) 并查集根节点所代表值改为 \(y\)。
- 整块的前缀和合并更新，扫整块的时候记录一个 \(temp\) 用来一次性更新前缀和，保证复杂度。
查询：
- 碎块处理需要先访问到序列真实值。
- 考虑开两个数组维护碎块的每个值出现次数、值域块内值个数。
- 查询直接先一点点跳整块（要算上碎块维护的值以及整块的值），然后一个个跳数字找到答案。
- 查询完毕记得清空维护碎块数组，注意要用添加的镜像操作回退，保证复杂度。
整体思路比较清晰，维护时注意细节，考虑每一个变量是否会在操作是变化，再卡卡常即可。
\(\text{code:}\)
#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
//--------------------//
const int N=1e5+5,QN=400,QN2=500;
int n,m;
//--------------------//
struct Dec
{
struct Block
{
int l,r;
int nid[N];
}b[QN];
int ncnt[QN][N],bcnt[QN][QN2];
int fid[N],f[N];
int len1,bcnt1,bl1[N];
int len2,bcnt2,bl2[N];
int s[N];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void init()
{
len1=512;
len2=256;
for(register int i=1;i<=1e5;i++)
bl2[i]=((bl2[i-1]*len2+1)==i?++bcnt2:bcnt2);
int maxt=0;
for(register int i=1;i<=n;i++)
{
bl1[i]=((bl1[i-1]*len1+1)==i?++bcnt1:bcnt1);
if(!b[bl1[i]].nid[s[i]])
{
b[bl1[i]].nid[s[i]]=i;
fid[i]=s[i];
}
f[i]=b[bl1[i]].nid[s[i]];
ncnt[bl1[i]][s[i]]++;
bcnt[bl1[i]][bl2[s[i]]]++;
}
for(register int i=1;i<=bcnt1;i++)
{
b[i].l=(i-1)*len1+1,b[i].r=min(n,i*len1);
for(register int j=1;j<=1e5;j++)
ncnt[i][j]+=ncnt[i-1][j];
for(register int j=1;j<=bcnt2;j++)
bcnt[i][j]+=bcnt[i-1][j];
}
return;
}
inline void cha_pic(int id,int l,int r,int x,int y)
{
int xcnt=0;
//printf("\npic:\n");
for(register int i=b[id].l;i<=b[id].r;i++)
s[i]=fid[find(f[i])];
for(register int i=l;i<=r;i++)
{
if(s[i]==x)
{
xcnt++;
s[i]=y;
}
}
for(register int i=b[id].l;i<=b[id].r;i++)
{
if(f[i]==i)
{
b[id].nid[fid[i]]=0;
fid[i]=0;
}
f[i]=0;
}
for(register int i=b[id].l;i<=b[id].r;i++)
{
if(!b[id].nid[s[i]])
{
b[id].nid[s[i]]=i;
fid[i]=s[i];
}
f[i]=b[id].nid[s[i]];
}
for(register int i=id;i<=bcnt1;i++)
{
ncnt[i][x]-=xcnt,ncnt[i][y]+=xcnt;
bcnt[i][bl2[x]]-=xcnt,bcnt[i][bl2[y]]+=xcnt;
};
return;
}
inline void change(int l,int r,int x,int y)
{
if(x==y)
return;
int now1=bl1[l],now2=bl1[r];
if(!(ncnt[now2][x]-ncnt[now1-1][x]))
return;
if(now1==now2)
{
cha_pic(now1,l,r,x,y);
return;
}
cha_pic(now1,l,b[now1].r,x,y);
cha_pic(now2,b[now2].l,r,x,y);
int tem=0;
for(register int temp,i=now1+1;i<now2;i++)
{
temp=ncnt[i][x]-ncnt[i-1][x];
ncnt[i-1][x]-=tem,ncnt[i-1][y]+=tem;
bcnt[i-1][bl2[x]]-=tem,bcnt[i-1][bl2[y]]+=tem;
tem+=temp;
if(!b[i].nid[y])
{
b[i].nid[y]=b[i].nid[x];
fid[b[i].nid[y]]=y;
}
else
{
fid[b[i].nid[x]]=0;
f[b[i].nid[x]]=b[i].nid[y];
}
b[i].nid[x]=0;
}
if(now1+1<now2)
{
for(register int i=now2-1;i<=bcnt1;i++)
{
ncnt[i][x]-=tem,ncnt[i][y]+=tem;
bcnt[i][bl2[x]]-=tem,bcnt[i][bl2[y]]+=tem;
}
}
return;
}
int temnc[N],tembc[QN];
inline int get_ans(int k,int l,int r)
{
int now=1;
while(k>tembc[now]+bcnt[r][now]-bcnt[l-1][now])
k-=tembc[now]+bcnt[r][now]-bcnt[l-1][now],now++;
for(register int i=(now-1)*len2+1;i<=min(now*len2,100000);i++)
{
k-=temnc[i]+ncnt[r][i]-ncnt[l-1][i];
if(k<=0)
return i;
}
return 114514;
}
inline int query(int l,int r,int k)
{
int now1=bl1[l],now2=bl1[r],res=0;
if(now1==now2)
{
for(register int i=l;i<=r;i++)
s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
res=get_ans(k,1,0);
for(register int i=l;i<=r;i++)
temnc[s[i]]--,tembc[bl2[s[i]]]--;
return res;
}
for(register int i=l;i<=b[now1].r;i++)
s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
for(register int i=b[now2].l;i<=r;i++)
s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
res=get_ans(k,now1+1,now2-1);
for(register int i=l;i<=b[now1].r;i++)
temnc[s[i]]--,tembc[bl2[s[i]]]--;
for(register int i=b[now2].l;i<=r;i++)
temnc[s[i]]--,tembc[bl2[s[i]]]--;
return res;
}
}D;
//--------------------//
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
D.s[i]=rd();
D.init();
for(int op,l,r,x,y,i=1;i<=m;i++)
{
op=rd();
if(op==1)
l=rd(),r=rd(),x=rd(),y=rd(),D.change(l,r,x,y);
else
l=rd(),r=rd(),x=rd(),printf("%d\n",D.query(l,r,x));
}
return 0;
}