题目传送门。
题意：维护一长为 \(n\) 的序列，有 \(m\) 次操作，操作分为区间 \(x\) 变为 \(y\) 和求区间第 \(k\) 小两种。\(n,m\le 10^5,1\le V\le 10^5\).
大分块一血。
其实一万年前就码出来了，只是前几天刚卡过去，今天才想起要写。
按照 04/21 讲课的思路记述一遍。
也就是说，这里介绍的是 lxl 本人在课件里记载的的做法，没有用到并查集。（虽说思想也差不多？）
弱化版 \(1\)：单点修改，全局第 \(k\) 小
直接维护一个值域分块。第 \(i\) 个值域块维护块内数出现次数和 \(v_i\)，每个数 \(v\) 维护其出现次数 \(h_v\)；于是不难做到 \(O(1)\) 修改，\(O(\sqrt n)\) 查询。
具体地，对于查询，我们先暴力找到第一个使块间前缀和 \(\ge k\) 的块，这一步是 \(O(\sqrt n)\) 的；随后暴力找块内第一个使前缀和 \(\ge k\) 的数，次数即为第 \(k\) 小。
弱化版 \(2\)：单点修改，区间第 \(k\) 小
也即 P2617 Dynamic Rankings。
我们发现，按弱化版 \(1\) 的做法求 kth 时，我们只用到了 \(v\) 数组和 \(h\) 数组；所以考虑在区间上还原这两个数组，然后套用上述做法。
散块是可以直接暴力的，复杂度 \(O(\sqrt n)\)；考虑整块。
把序列中每个位置拆成 \((i,a_i)\) 的点，放到二维平面上考虑。
不难发现可以预处理出值域块和数的块间前缀和。具体地，设 \(f_{x,i}\) 为数 \(x\) 在前 \(i\) 个序列块中的出现次数，\(g_{x,i}\) 为在前 \(i\) 个序列块中的所有数中，属于第 \(x\) 个值域块的数的个数。这两个东西都可以 \(O(n \sqrt n)\) 预处理出来，修改时也可以 \(O(\sqrt n)\) 更新。
这样我们就可以 \(O(1)\) 求得整块的贡献。于是每轮查询都可以 \(O(\sqrt n)-O(1)\) 得到所需的 \(v\) 和 \(h\) 的每一项，于是做完了。
回到本题：区间 \(x\) 变 \(y\)，区间第 \(k\) 小
以下称“原始值”为当前结构中实际存储的数，“真实值”为经历所有修改后，应当呈现出的数。
我们肯定是不想直接维护真实值的；所以不难想到在每个序列块内维护一个映射，修改时利用映射高效完成。
具体地，设 \(\text{fwd}_{x,i}\) 为在第 \(i\) 个序列块内，原始值 \(x\) 对应的真实值；\(\text{rev}_{x,i}\) 为第 \(i\) 个序列块中，真实值 \(x\) 对应的原始值。
然后对于修改过程中经过的每一个序列块 \(i\)，简单分讨。
如果块内没有 \(x\)，跳过。
如果块内有 \(x\) 且没有 \(y\)，直接令 \(\text{fwd}_{\text{rev}_{x,i},i}\leftarrow y,\text{rev}_{x,i}\leftarrow\text{rev}_{y,i}\) 即可。这不难理解。
如果块内有 \(x\) 且有 \(y\)，暴力重构。
为什么这样的复杂度是对的？势能分析一下。
定义一个序列块的势能为其中不同数的数量；那么我们对其重构的必要条件就是其势能至少为 \(2\)。
而每一轮重构，一个序列块的势能至少 \(-1\)，也就是对于一个序列块，我们至多重构 \(O(\sqrt n)\) 次。单次重构的代价是 \(O(\sqrt n)\)，一共有 \(O(\sqrt n)\) 个序列块，因此重构的总代价就是 \(O(\sqrt n)\times O(\sqrt n)\times O(\sqrt n)=O(n \sqrt n)\)，不影响总复杂度。
另外，得益于这样的重构机制，我们发现任意时刻，\(\text{fwd}\) 和 \(\text{rev}\) 都是双射。所以我们可以直接用二维数组维护。
至此已经做完了，剩下的就是一些不太难想但有点难调的小细节和轻微的卡常，可以看代码。
#include<iostream>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
const int M=370;int n,m;
int idx;//值域大小int a[N];namespace OIfast{char buf[1<<21],*p1,*p2,*top, buffer[1<<21];#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)#define gc getchar()inline int read(){int n=0;static char c=gc;while(!isdigit(c))c=gc;while(isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=gc;return n;}inline void print(int n){static short sta[7];short top=0;do{sta[top++]=n%10,n/=10;}while(n);while(top)putchar(sta[--top]^48);return ;}inline void write(int n,char c){return print(n),putchar(c),void();}}using namespace OIfast;namespace FK{//变量名后带 _ 表示这个变量属于值域分块，否则属于序列分块const int B=320,B_=320;//块长int tot,tot_;//块数int L[M],R[M],L_[M],R_[M];//块的左右端点int loc[N],loc_[N];//loc[i] -> 下标 i 所在的序列块，loc_[i] 同理int f[M][N]/*f[blk][val] -> 真实值 val 在前 blk 个序列块中的出现次数*/,g[M][M]/*g[blk][blk_] -> 属于第 blk_ 个值域块的所有数在前 blk 个序列块中出现的次数之和*/;int v[M]/*v[blk_] -> （当前查询中）第 blk_ 个值域块内的数的个数*/,h[N]/*h[val] -> （当前查询中）数 val 的出现次数*/;int rev[N][M]/*rev[val][blk] -> 在第 blk 个序列块中，真实值 val 对应的原始值*/,fwd[N][M]/*fwd[val][blk] -> 在第 blk 个序列块中，原始值 val 对应的真实值*/;int topv,toph;//查询时用于清空的栈int stkv[N],stkh[N];int cntx[M]/*cntx[blk] -> （当前查询中）第 blk 个序列块里 x 的出现次数，cnty 同理*/,cnty[M],cx[M]/*cx[blk] -> （当前查询中）第 blk 个序列块里与 x 属于同一个值域块的数的个数，cy 同理*/,cy[M];inline void init(){idx=*max_element(a+1,a+n+1);tot=ceil((1.0*n)/(1.0*B)),tot_=ceil((1.0*idx)/(1.0*B_));for(int i=1;i<=tot_;++i){L_[i]=R_[i-1]+1,R_[i]=min(idx,L_[i]+B_-1);for(int j=L_[i];j<=R_[i];++j)loc_[j]=i;}for(int i=1;i<=tot;++i){L[i]=R[i-1]+1,R[i]=min(n,L[i]+B-1);if(i==1){for(int j=L[i];j<=R[i];++j){loc[j]=i;++f[i][a[j]];++g[i][loc_[a[j]]];}} else {for(int val=1;val<=idx;++val)f[i][val] = f[i-1][val];for(int blk_=1;blk_<=tot_;++blk_)g[i][blk_] = g[i-1][blk_];for(int j=L[i];j<=R[i];++j)loc[j]=i,++f[i][a[j]],++g[i][loc_[a[j]]];}}for(int pos=1;pos<=tot;++pos)for(int val=1;val<=idx;++val)fwd[val][pos]=rev[val][pos]=val;return ;}inline int kth(int locl,int locr,int k){int sum=0;int i=1;for(;sum+(g[locr][i]-g[locl-1][i]+v[i])<k;sum+=(g[locr][i]-g[locl-1][i]+v[i++]));i=L_[i];for(;sum+(f[locr][i]-f[locl-1][i]+h[i])<k;sum+=(f[locr][i]-f[locl-1][i]+h[i++]));return i;}inline int bf_qry(int l,int r,int k){int pos=loc[l];for(int i=l;i<=r;++i){int val=fwd[a[i]][pos];if(!v[loc_[val]])stkv[++topv]=loc_[val];++v[loc_[val]];if(!h[val])stkh[++toph]=val;++h[val];}int res=kth(loc[l]+1,loc[r],k);while(topv)v[stkv[topv--]]=0;while(toph)h[stkh[toph--]]=0;return res;}inline int qry(int l,int r,int k){if(loc[l]==loc[r])return bf_qry(l,r,k);for(int i=l;i<=R[loc[l]];++i){int val=fwd[a[i]][loc[l]];if(!v[loc_[val]])stkv[++topv]=loc_[val];++v[loc_[val]];if(!h[val])stkh[++toph]=val;++h[val];}for(int i=L[loc[r]];i<=r;++i){int val=fwd[a[i]][loc[r]];if(!v[loc_[val]])stkv[++topv]=loc_[val];++v[loc_[val]];if(!h[val])stkh[++toph]=val;++h[val];}int res=kth(loc[l]+1,loc[r]-1,k);while(topv)v[stkv[topv--]]=0;while(toph)h[stkh[toph--]]=0;return res;}inline void pushdown(int pos,int x,int y){f[pos][x]=f[pos-1][x];f[pos][y]=f[pos-1][y];g[pos][loc_[x]]=g[pos-1][loc_[x]];g[pos][loc_[y]]=g[pos-1][loc_[y]];for(int i=L[pos];i<=R[pos];++i){if(a[i]==x)++f[pos][x];else if(a[i]==y)++f[pos][y];if(loc_[a[i]]==loc_[x])++g[pos][loc_[x]];else if(loc_[a[i]]==loc_[y])++g[pos][loc_[y]];fwd[a[i]][pos]=rev[a[i]][pos]=a[i];}return ;}inline void bf_mdf(int l,int r,int x,int y){int pos=loc[l];for(int i=L[pos];i<=R[pos];++i)a[i]=fwd[a[i]][pos];for(int i=l;i<=r;++i)if(a[i]==x)a[i]=y;return pushdown(pos,x,y),void();}inline void bf_upd(int l,int r,int x,int y){int pos=loc[l];bf_mdf(l,r,x,y);for(int i=pos+1;i<=tot;++i){g[i][loc_[x]]=g[i-1][loc_[x]]+cx[i];g[i][loc_[y]]=g[i-1][loc_[y]]+cy[i];f[i][x]=f[i-1][x]+cntx[i];f[i][y]=f[i-1][y]+cnty[i];}return ;}inline void upd(int l,int r,int x,int y){if(x==y)return ;for(int i=loc[l]+1;i<=tot;++i){cntx[i]=f[i][x]-f[i-1][x];cnty[i]=f[i][y]-f[i-1][y];cx[i]=g[i][loc_[x]]-g[i-1][loc_[x]];cy[i]=g[i][loc_[y]]-g[i-1][loc_[y]];}if(loc[l]==loc[r])bf_upd(l,r,x,y);else{bf_mdf(l,R[loc[l]],x,y);for(int i=loc[l]+1;i<=tot;++i){if((!cntx[i])||i>loc[r]){g[i][loc_[x]]=g[i-1][loc_[x]]+cx[i];g[i][loc_[y]]=g[i-1][loc_[y]]+cy[i];f[i][x]=f[i-1][x]+cntx[i];f[i][y]=f[i-1][y]+cnty[i];continue ;}if(i==loc[r]){bf_mdf(L[loc[r]],r,x,y);continue ;}if(cnty[i]){bf_mdf(L[i],R[i],x,y);continue ;}fwd[rev[x][i]][i]=y,rev[y][i]=rev[x][i],rev[x][i]=0;if(loc_[x]^loc_[y]){g[i][loc_[x]]=g[i-1][loc_[x]]+cx[i]-cntx[i];g[i][loc_[y]]=g[i-1][loc_[y]]+cy[i]+cntx[i];}else{g[i][loc_[x]]=g[i-1][loc_[x]]+cx[i];}f[i][x]=f[i-1][x];f[i][y]=f[i-1][y]+cntx[i];}}return ;}}using namespace FK;inline void work(){int op=read();if(1==2){puts("wow");}else if(op==1){int l=read(),r=read(),x=read(),y=read();upd(l,r,x,y);}else if(op==2){int l=read(),r=read(),k=read();write(qry(l,r,k),'\n');}return ;
}signed main(){n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read();init();while(m--)work();return 0;
}
注意到上面的代码是未经卡常的，而我卡常后的代码（虽说在最优解第 \(18\) 页，还比榜一慢两倍多）在 \(n=m=10^5\) 的随机数据下比它快了一倍多。
放一个卡常后的代码。其实并没有用循环展开、逐多块处理这种高阶卡常手法，只是完全用全局变量替代局部变量、交换二维数组两维和一些其他约等于 gunmu 的修改。
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;const int N=1e5+5;
const int M=320;int n,m;
int idx;int a[N];namespace OIfast{char buf[1<<21],*p1,*p2,*top,buffer[1<<21];#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)#define gc getchar()inline int read(){static int n;n=0;static char c(gc);while(!isdigit(c))c=gc;while(isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=gc;return n;}inline void print(int n){static short sta[7];static short top;top=0;do{sta[top++]=n%10,n/=10;}while(n);while(top)putchar(sta[--top]^48);return ;}inline void write(int n,char c){return print(n),putchar(c),void();}}using namespace OIfast;namespace FK{#define tr(x) __builtin_expect(!!(x),1)#define fs(x) __builtin_expect(!!(x),0)const int B=600,B_=380;int tot,tot_;int L[M],R[M],L_[M],R_[M];int loc[N],loc_[N];int f[M][N],g[M][M];int v[M],h[N];int rev[M][N],fwd[M][N];int topv,toph;int stkv[N],stkh[N];int cntx[M],cnty[M],cx[M],cy[M];int i_init,j_init,pos_init,val_init,blk__init;inline void init(){idx=*max_element(a+1,a+n+1);tot=ceil((1.0*n)/(1.0*B)),tot_=ceil((1.0*idx)/(1.0*B_));for(i_init=1;i_init<=tot_;++i_init){L_[i_init]=R_[i_init-1]+1,R_[i_init]=min(idx,L_[i_init]+B_-1);for(j_init=L_[i_init];j_init<=R_[i_init];++j_init)loc_[j_init]=i_init;}for(i_init=1;i_init<=tot;++i_init){L[i_init]=R[i_init-1]+1,R[i_init]=min(n,L[i_init]+B-1);if(i_init==1){for(j_init=L[i_init];j_init<=R[i_init];++j_init){loc[j_init]=i_init;++f[i_init][a[j_init]];++g[i_init][loc_[a[j_init]]];}}else{for(val_init=1;val_init<=idx;++val_init)f[i_init][val_init]=f[i_init-1][val_init];for(blk__init=1;blk__init<=tot_;++blk__init)g[i_init][blk__init]=g[i_init-1][blk__init];for(j_init=L[i_init];j_init<=R[i_init];++j_init){loc[j_init]=i_init;++f[i_init][a[j_init]];++g[i_init][loc_[a[j_init]]];}}}for(pos_init=1;pos_init<=tot;++pos_init)for(val_init=1;val_init<=idx;++val_init)fwd[pos_init][val_init]=rev[pos_init][val_init]=val_init;return ;}int sum_kth,i_kth;inline int kth(int locl,int locr,int k){sum_kth=0;i_kth=1;for(;sum_kth+(g[locr][i_kth]-g[locl-1][i_kth]+v[i_kth])<k;sum_kth+=(g[locr][i_kth]-g[locl-1][i_kth]+v[i_kth++]));i_kth=L_[i_kth];for(;sum_kth+(f[locr][i_kth]-f[locl-1][i_kth]+h[i_kth])<k;sum_kth+=(f[locr][i_kth]-f[locl-1][i_kth]+h[i_kth++]));return i_kth;}int pos_bf_qry,i_bf_qry,res_bf_qry,val_bf_qry;inline int bf_qry(int l,int r,int k){pos_bf_qry=loc[l];for(i_bf_qry=l;i_bf_qry<=r;++i_bf_qry){val_bf_qry=fwd[pos_bf_qry][a[i_bf_qry]];if(!v[loc_[val_bf_qry]])(stkv[++topv]=loc_[val_bf_qry]);++v[loc_[val_bf_qry]];if(!h[val_bf_qry])(stkh[++toph]=val_bf_qry);++h[val_bf_qry];}res_bf_qry=kth(loc[l]+1,loc[r],k);while(topv)v[stkv[topv--]]=0;while(toph)h[stkh[toph--]]=0;return res_bf_qry;}int i_qry,res_qry,val_qry;inline int qry(int l,int r,int k){if(loc[l]==loc[r])return bf_qry(l,r,k);for(i_qry=l;i_qry<=R[loc[l]];++i_qry){val_qry=fwd[loc[l]][a[i_qry]];if(!v[loc_[val_qry]])(stkv[++topv]=loc_[val_qry]);++v[loc_[val_qry]];if(!h[val_qry])(stkh[++toph]=val_qry);++h[val_qry];}for(i_qry=L[loc[r]];i_qry<=r;++i_qry){val_qry=fwd[loc[r]][a[i_qry]];if(!v[loc_[val_qry]])(stkv[++topv]=loc_[val_qry]);++v[loc_[val_qry]];if(!h[val_qry])(stkh[++toph]=val_qry);++h[val_qry];}res_qry=kth(loc[l]+1,loc[r]-1,k);while(topv)v[stkv[topv--]]=0;while(toph)h[stkh[toph--]]=0;return res_qry;}int i_pushdown;inline void pushdown(int pos,int x,int y){f[pos][x]=f[pos-1][x];f[pos][y]=f[pos-1][y];g[pos][loc_[x]]=g[pos-1][loc_[x]];g[pos][loc_[y]]=g[pos-1][loc_[y]];for(i_pushdown=L[pos];i_pushdown<=R[pos];++i_pushdown){if(a[i_pushdown]==x)++f[pos][x];else if(a[i_pushdown]==y)++f[pos][y];if(loc_[a[i_pushdown]]==loc_[x])++g[pos][loc_[x]];else if(loc_[a[i_pushdown]]==loc_[y])++g[pos][loc_[y]];fwd[pos][a[i_pushdown]]=rev[pos][a[i_pushdown]]=a[i_pushdown];}return ;}int pos_bf_mdf,i_bf_mdf;inline void bf_mdf(int l,int r,int x,int y){pos_bf_mdf=loc[l];for(i_bf_mdf=L[pos_bf_mdf];i_bf_mdf<=R[pos_bf_mdf];++i_bf_mdf)a[i_bf_mdf]=fwd[pos_bf_mdf][a[i_bf_mdf]];for(i_bf_mdf=l;i_bf_mdf<=r;++i_bf_mdf)a[i_bf_mdf]=(a[i_bf_mdf]==x?y:a[i_bf_mdf]);return pushdown(pos_bf_mdf,x,y),void();}int i_bf_upd,pos_bf_upd;inline void bf_upd(int l,int r,int x,int y){pos_bf_upd=loc[l];bf_mdf(l,r,x,y);for(i_bf_upd=pos_bf_upd+1;i_bf_upd<=tot;++i_bf_upd){g[i_bf_upd][loc_[x]]=g[i_bf_upd-1][loc_[x]]+cx[i_bf_upd];g[i_bf_upd][loc_[y]]=g[i_bf_upd-1][loc_[y]]+cy[i_bf_upd];f[i_bf_upd][x]=f[i_bf_upd-1][x]+cntx[i_bf_upd];f[i_bf_upd][y]=f[i_bf_upd-1][y]+cnty[i_bf_upd];}return ;}int i_upd;inline void upd(int l,int r,int x,int y){if(x==y)return ;for(i_upd=loc[l]+1;i_upd<=tot;++i_upd){cntx[i_upd]=f[i_upd][x]-f[i_upd-1][x];cnty[i_upd]=f[i_upd][y]-f[i_upd-1][y];cx[i_upd]=g[i_upd][loc_[x]]-g[i_upd-1][loc_[x]];cy[i_upd]=g[i_upd][loc_[y]]-g[i_upd-1][loc_[y]];}if(loc[l]==loc[r])bf_upd(l,r,x,y);else{bf_mdf(l,R[loc[l]],x,y);for(i_upd=loc[l]+1;i_upd<=tot;++i_upd){if(i_upd>loc[r]||(!cntx[i_upd])){g[i_upd][loc_[x]]=g[i_upd-1][loc_[x]]+cx[i_upd];g[i_upd][loc_[y]]=g[i_upd-1][loc_[y]]+cy[i_upd];f[i_upd][x]=f[i_upd-1][x]+cntx[i_upd];f[i_upd][y]=f[i_upd-1][y]+cnty[i_upd];continue ;}if(i_upd==loc[r]){bf_mdf(L[loc[r]],r,x,y);continue ;}if(cnty[i_upd]){bf_mdf(L[i_upd],R[i_upd],x,y);continue ;}fwd[i_upd][rev[i_upd][x]]=y;rev[i_upd][y]=rev[i_upd][x];if(loc_[x]^loc_[y]){g[i_upd][loc_[x]]=g[i_upd-1][loc_[x]]+cx[i_upd]-cntx[i_upd];g[i_upd][loc_[y]]=g[i_upd-1][loc_[y]]+cy[i_upd]+cntx[i_upd];}else g[i_upd][loc_[x]]=g[i_upd-1][loc_[x]]+cx[i_upd];f[i_upd][x]=f[i_upd-1][x];f[i_upd][y]=f[i_upd-1][y]+cntx[i_upd];}}return ;}}using namespace FK;int op_work,l_work,r_work,x_work,y_work,k_work;inline void work(){op_work=read();(op_work==1)&&(l_work=read(),r_work=read(),x_work=read(),y_work=read(),upd(l_work,r_work,x_work,y_work),1);(op_work==2)&&(l_work=read(),r_work=read(),k_work=read(),write(qry(l_work,r_work,k_work),'\n'),1);return ;
}signed main(){n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read();init();while(m--)work();return 0;
}
跑了 \(7.76s\)，还是人傻常数大导致的。
提交记录。