分块解决区间等于 x 的数变成 y 问题

问题 1

题目

CF911G. Mass Change Queries
给定长度为 $n$ 的序列，有 $q$ 个操作，每个操作是把区间 $[l,r]$ 中等于 $x$ 的数改成 $y$。
输出 $q$ 步操作完的数列。
$n,q\le 2\times 10^5,a_i\le 100$。

做法

（这个问题有用动态开点线段树的做法，但是线段树难以解决区间询问问题，我们这里介绍分块做法。）

考虑分块，块长为 $B$，用并查集维护每个数的位置，维护每个块每个颜色的代表元素 $rt_{i,x}$（如果没有就是 $0$），并保证 $a[rt_{i,x}]$ 始终对应其真实颜色，空间复杂度 $O\left(V\cdot \dfrac n B\right)$。

修改整块，把 $x$ 变 $y$ 的时候：

• 如果 $x$ 是空的就是什么都不做；
• 否则：
  • 如果 $y$ 是空的，执行 $rt_{i,y}\leftarrow rt_{i,x}$，并修改 $a[rt_{i,x}]$ 为 $y$，将 $rt_{i,x}$ 设为 $0$。
  • 如果 $rt_{i,y}$ 有值，直接修改 $rt_{i,x}$ 的 fa 为 $rt_{i,y}$。

复杂度 $O\left(\dfrac n B\right)$。

对于散块，直接重构，每个元素在并查集查询它的根，注意到这样均摊复杂度是 $O(1)$ 的，复杂度 $O(B)$。（因为路径压缩时，我们每往上跳一次就会把一个点连上真实的根）

令 $B=\sqrt n$，总复杂度 $O(q\sqrt n + n)$。

#include<bits/stdc++.h>
using namespace std;


const int N = 2e5+5;
const int SQRTN = 1e3;
int B ;
int bel[N];

int lft[SQRTN],rht[SQRTN];
int a[N];

int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int rt[SQRTN][101];

// 修改第 id 块散块中的 [l,r] 部分
void modify1(int id,int l,int r,int x,int y){
    // 查询出真实的值
    for(int i=lft[id];i<=rht[id];i++)a[i] = a[find(i)];
    // 重构 x,y
    rt[id][x]=rt[id][y]=0;
    for(int i=lft[id];i<=rht[id];i++){
        if(a[i] != x && a[i] != y)continue;
        if(a[i]==x && l<=i && i<=r)a[i]=y;
        if(!rt[id][a[i]])rt[id][a[i]]=i,fa[i]=i;
        else             fa[i]=rt[id][a[i]];
    }
}
// 修改第 id 块整块
void modify2(int id,int x,int y){
    if(!rt[id][x])return; // 没有 x
    if(rt[id][y])fa[rt[id][x]]=rt[id][y]; // 有 y
    else{ // 没有 y
        rt[id][y] = rt[id][x];
        a[rt[id][y]] = y;
    }
    rt[id][x] = 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n;cin>>n;  B = sqrt(n);

    for(int i=1;i<=n;i++){
        cin>>a[i];
        bel[i] = (i-1)/B+1;
        if(!lft[bel[i]])lft[bel[i]]=i;
        rht[bel[i]]=i;
    }

    int maxb = (n-1)/B+1;
    for(int i=1;i<=maxb;i++){
        for(int j=lft[i];j<=rht[i];j++){
            if(!rt[i][a[j]])rt[i][a[j]]=j,fa[j]=j;
            else            fa[j]=rt[i][a[j]];
        }
    }
    int q; cin>>q;
    while(q--){
        int l,r,x,y; cin>>l>>r>>x>>y;
        if(x==y)continue;
        if(bel[l]==bel[r])modify1(bel[l],l,r,x,y);
        else{
            modify1(bel[l],l,rht[bel[l]],x,y);
            for(int i=bel[l]+1;i<=bel[r]-1;i++)modify2(i,x,y);
            modify1(bel[r],lft[bel[r]],r,x,y);
        }
    }

    for(int i=1;i<=n;i++)cout << a[find(i)] << ' ';
    cout << '\n';
    return 0;
}

问题 2

题目

P8576 「DTOI-2」星之界
给定长度为 $n$ 的序列，有 $q$ 个操作：

1. 把 $[l,r]$ 中等于 $x$ 的数改成 $y$。
2. 给定 $[l,r]$，查询 $\displaystyle \prod_{i=l}^r {\dbinom{\sum_{j=l}^ia_j}{a_i}}$，对 $998244353$ 取模。

$n,q,a_i\le 10^5$，保证任意时刻 $\sum a \le 10^7$。

做法

先推式子：

$$\begin{aligned} &\prod_{i=l}^r {\dbinom{\sum_{j=l}^ia_j}{a_i}}\\ &= \prod_{i=l}^r {\dfrac{\left ( \sum_{j=l}^ia_j \right ) !}{a_i!\left ( \sum_{j=l}^{i-1}a_j \right ) ! }} \\&= {\dfrac{\left ( \sum_{i=l}^ra_i \right ) !}{\prod_{i=l}^r a_i! }} \end{aligned}$$

所以我们只需要查询 $a$ 的区间和和区间阶乘乘积即可。

沿用上文思路，考虑在分块的同时维护这些信息。
对于散块很简单，因为我们直接重构，信息是容易维护的，我们关注整块。
整块要解决的是把所有 $x$ 接到 $y$ 下面，对于并查集维护大小 $sz$，则就是少了 $sz[x]$ 个 $x$，多了 $sz[y]$ 个 $y$。这样就可以维护区间和以及区间阶乘乘积了，这里注意不要用快速幂求出 $(x!)^{sz[x]}$ 和 $(y!)^{sz[x]}$，而是花 $O(V\sqrt n)$ 的代价预处理出 $1\sim \max a$ 的阶乘 $1\sim\sqrt n$ 次方（以及其逆元），否则会多一个 $\log$ 的代价。

区间和的阶乘也同样预处理所有可能值，因为保证保证任意时刻 $\sum a \le 10^7$。

同样取块长 $B=\sqrt n$，复杂度 $O(n\sqrt n)$。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 998244353;

const int P = 1e7+5;
const int N = 1e5+1;
int ksm(int a,int b){
    int r=1;
    while(b){
        if(b&1)r=(ll)r*a%MOD;
        a=(ll)a*a%MOD;
        b>>=1;
    }
    return r;
}


const int B=300;

int f[P];
int fp[N][B+1],invfp[N][B+1];

int bel[N];

int lft[N/B + 5],rht[N/B + 5];
int a[N];

int fa[N],sz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int rt[N/B + 5][N];

int sum[N/B + 5],fprod[N/B + 5]; // 每一块的和/阶乘乘积

// 修改第 id 块散块中的 [l,r] 部分
void modify1(int id,int l,int r,int x,int y){
    // 查询出真实的值
    for(int i=lft[id];i<=rht[id];i++)a[i] = a[find(i)];
    // 重构 x,y
    sz[rt[id][x]]=sz[rt[id][y]]=0;
    rt[id][x]=rt[id][y]=0;
    for(int i=lft[id];i<=rht[id];i++){
        if(a[i] != x && a[i] != y)continue;
        if(a[i]==x && l<=i && i<=r){
            a[i]=y;
            sum[id] = (sum[id]-x+y);
            fprod[id] = (ll)fprod[id]*invfp[x][1]%MOD*fp[y][1]%MOD;
        }
        if(!rt[id][a[i]])rt[id][a[i]]=i,fa[i]=i,++sz[fa[i]];
        else             fa[i]=rt[id][a[i]],++sz[fa[i]];
    }
}
// 修改第 id 块整块
void modify2(int id,int x,int y){
    if(!rt[id][x])return; // 没有 x
    if(rt[id][y]){ // 有 y
        fa[rt[id][x]]=rt[id][y]; 
        sz[rt[id][y]] += sz[rt[id][x]];
        sum[id] = (sum[id]-x*sz[rt[id][x]]+y*sz[rt[id][x]]);
        fprod[id] = (ll)fprod[id]*invfp[x][sz[rt[id][x]]]%MOD*fp[y][sz[rt[id][x]]]%MOD;
        sz[rt[id][x]] = 0;
        rt[id][x] = 0;
    }
    else{ // 没有 y
        rt[id][y] = rt[id][x];
        sz[rt[id][y]] = sz[rt[id][x]];
        sum[id] = (sum[id]-x*sz[rt[id][x]]+y*sz[rt[id][x]]);
        fprod[id] = (ll)fprod[id]*invfp[x][sz[rt[id][x]]]%MOD*fp[y][sz[rt[id][x]]]%MOD;
        a[rt[id][y]] = y;
        rt[id][x] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    f[0]=1;for(int i=1;i<P;i++)f[i]=(ll)f[i-1]*i%MOD;
    for(int i=1;i<N;i++){
        fp[i][0] = invfp[i][0]=1;
        int invi = ksm(f[i],MOD-2);
        for(int j=1;j<=B;j++)fp[i][j]=(ll)fp[i][j-1]*f[i]%MOD,invfp[i][j]=(ll)invfp[i][j-1]*invi%MOD;
    }


    int n;cin>>n; 
    int q; cin>>q;

    for(int i=1;i<=n;i++){
        cin>>a[i];
        bel[i] = (i-1)/B+1;
        if(!lft[bel[i]])lft[bel[i]]=i;
        rht[bel[i]]=i;
    }

    int maxb = (n-1)/B+1;
    for(int i=1;i<=maxb;i++){
        sum[i]=0,fprod[i]=1;
        for(int j=lft[i];j<=rht[i];j++){
            if(!rt[i][a[j]])rt[i][a[j]]=j,fa[j]=j,++sz[fa[j]];
            else            fa[j]=rt[i][a[j]],++sz[fa[j]];
            sum[i] += a[j];
            fprod[i] = (ll)fprod[i]*f[a[j]]%MOD;
        }
    }
    while(q--){
        int op,l,r; cin>>op>>l>>r;
        if(op==1){
            int x,y;cin>>x>>y;
            if(x==y)continue;
            if(bel[l]==bel[r])modify1(bel[l],l,r,x,y);
            else{
                modify1(bel[l],l,rht[bel[l]],x,y);
                for(int i=bel[l]+1;i<=bel[r]-1;i++)modify2(i,x,y);
                modify1(bel[r],lft[bel[r]],r,x,y);
            }
        }
        else{
            int s = 0, p = 1;
            if(bel[l]==bel[r]){
                for(int i=l;i<=r;i++) a[i]=a[find(i)], s += a[i],p = (ll)p*f[a[i]]%MOD;
            }
            else{
                for(int i=l;i<=rht[bel[l]];i++) a[i]=a[find(i)], s += a[i],p = (ll)p*f[a[i]]%MOD;
                for(int i=bel[l]+1;i<=bel[r]-1;i++) s += sum[i],p = (ll)p*fprod[i]%MOD;
                for(int i=lft[bel[r]];i<=r;i++) a[i]=a[find(i)], s += a[i],p = (ll)p*f[a[i]]%MOD;
            }

            cout << (ll)f[s] *ksm(p,MOD-2)%MOD << '\n';
        }
    }

    return 0;
}

问题 3

题目

P8360 [SNOI2022] 军队

给定长度为 $n$ 的序列，每个位置有值 $a_i$ 和颜色 $c_i$，有 $q$ 个操作：

1. 把 $[l,r]$ 中 $c_i$ 等于 $x$ 的位置的 $c_i$ 改成 $y$。
2. 把 $[l,r]$ 中 $c_i$ 等于 $x$ 的位置的 $a_i$ 加上 $v$。
3. 给定 $[l,r]$，查询 $\displaystyle \sum_{i=l}^r a_i$。

$n,q,c_i,x,y\le 2.5\times 10^5$，$a_i,v\le 10^8$。

做法 1（整块暴力重构）

对每种颜色维护加标记，散块自然可以暴力重构，我们考虑整块的处理。

如果整块的颜色 $x,y$ 有一个不存在是简单的。

如果 $x,y$ 都存在，这时候标记比较难处理，有一种很简单的做法是：直接暴力重构这一块。

复杂度是正确的，因为所有块一开始总共最多只有 $O(n)$ 种颜色，每次暴力重构一块会减少一种颜色，只有处理散块时可能增加一种颜色，而我们总共只会处理 $O(q)$ 次散块。

所以时间复杂度依然是 $O((n+q)\sqrt n)$ 的。

为了节省空间，我们采用一个离线 trick，每次只处理一块的修改，查询，然后把每块的内容加起来得到最终答案，这样能够达到线性空间。

对于整块：

• 操作 1：如果 $x,y$ 不是都有简易。如果都有，直接重构当前块。
• 操作 2：把颜色的 $tag$ 加上 $v$，一并维护总和。
• 操作 3：返回当前节点的总和。

对于散块：

• 操作 1：直接暴力修改，重构这一整块，重构的时候把 $tag$ 消除。
• 操作 2：直接暴力查颜色，修改 $a_i$ 即可，可以不用动 $tag$，也不用重构。
• 操作 3：直接暴力查 $a_i$ 和 $tag$ 和，求出答案即可。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 2.5e5+5;
const int B = 500;

ll tag[N],a[N];
int fa[N],c[N],rt[N],sz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
ll sum; // 当前块的总和

ll ans[N];
int op[N][5];

void apply(int l,int r){ // 将 a[l..r] 和 c[l..r] 修改为真实值
    for(int j=l;j<=r;j++){
        c[j] = c[find(j)];
        a[j] = a[j] + tag[c[j]]; 
    }
    for(int j=l;j<=r;j++)tag[c[j]]=0,rt[c[j]]=0,sz[c[j]]=0;
}
void make(int l,int r){ // 重构当前块
    sum = 0;
    for(int j=l;j<=r;j++){
        if(!rt[c[j]])rt[c[j]]=j,fa[j]=j,sz[c[j]]++;
        else         fa[j]=rt[c[j]],sz[c[j]]++;
        sum += a[j];
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n,q,m; cin>>n>>q>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=q;i++){
        cin>>op[i][0];
        if(op[i][0]<=2)cin>>op[i][1]>>op[i][2]>>op[i][3]>>op[i][4];
        else           cin>>op[i][1]>>op[i][2];
    }
    
    
    for(int l=1,r;l<=n;l=r+1){
        r = min(n, l+B-1);
        sum = 0;
        make(l,r);
        
        for(int i=1;i<=q;i++){
            int cmd = op[i][0],ql=op[i][1],qr=op[i][2];
            int x=op[i][3],y=op[i][4];
            if(ql<=l && r<=qr){
                if(cmd == 1){
                    if(!rt[x])continue;
                    if(!rt[y]){
                        swap(rt[x],rt[y]);
                        swap(sz[x],sz[y]);
                        swap(tag[x],tag[y]);
                        c[rt[y]]=y;
                    }
                    else{
                        apply(l,r);
                        for(int j=l;j<=r;j++)if(c[j]==x)c[j]=y;
                        make(l,r);
                    }
                }
                else if(cmd == 2){
                    if(!rt[x])continue;
                    tag[x] += y;
                    sum += (ll)y*sz[x];
                }
                else{
                    ans[i] += sum;
                }
            }
            else{
                int rl = max(l, ql), rr = min(r, qr);
                if(rl > rr)continue;

                if(cmd == 1){
                    apply(l,r);
                    for(int j=rl;j<=rr;j++)if(c[j]==x)c[j]=y;
                    make(l,r);
                }
                else if(cmd == 2){
                    for(int j=rl;j<=rr;j++)if(c[find(j)]==x)a[j]+=y,sum+=y;
                }
                else{
                    for(int j=rl;j<=rr;j++)ans[i]+=a[j]+tag[c[find(j)]];
                }
            }
        }
        
        for(int j=l;j<=r;j++)tag[c[j]]=0,rt[c[j]]=0,sz[c[j]]=0;
    }

    for(int i=1;i<=q;i++){
        if(op[i][0]==3)cout<<ans[i]<<'\n';
    }
    return 0;
}

做法 2（维护加法标记）

我们考虑能不能像带权并查集一样维护一个加法标记。我们设定一个元素的真正的值是原序列中的 $a_i$ 加上它自己到并查集中根的 $tag$ 之和。

在路径压缩的时候像带权并查集一样维护这个 $tag$。

对于整块：

• 操作 1：如果 $x,y$ 不是都有简易。如果都有，把 $x$ 接到 $y$ 上，要把 $rt_x$ 的 $tag$ 减掉 $rt_y$ 的 $tag$ 用于抵消贡献。
• 操作 2：把颜色在并查集中的根 $rt_x$ 的 $tag$ 加上 $v$，并维护当前节点的总和（通过维护每个颜色有几个）。
• 操作 3：返回当前节点的总和。

对于散块：

• 操作 1：直接暴力修改，重构这一块的结构，$tag$ 可以顺便一并拍平重构。
• 操作 2：直接暴力查颜色，修改 $a_i$ 即可，不用动 $tag$，也不用重构。
• 操作 3：直接暴力查 $a_i$ 和 $tag$ 和，求出答案即可。

代码略。

问题 4（第二分块）

题目

P4117 [Ynoi2018] 五彩斑斓的世界

给定长度为 $n$ 的序列，有 $q$ 个操作：

1. 把 $[l,r]$ 中 大于 $x$ 的数减去 $x$。
2. 给定 $[l,r]$，查询 $[l,r]$ 中 $x$ 的出现次数。

$n\le 10^6,q\le 5\times 10^5,a_i,x\le 10^5+1$。
时空限制：7.5s, 64MB。

做法

首先因为空间很小，然后这个查询又具有可加性，我们还是按照套路一块一块分开离线处理。

散块操作依然可以暴力，我们考虑整块如何快速处理。

因为值域不大，考虑利用值域寻找一个均摊复杂度。
具体来说，设当前区间的最大值为 $mx$：

1. 如果 $2x\ge mx$，暴力把所有大于 $x$ 的元素减去 $x$；
2. 否则，暴力把所有小于等于 $x$ 的元素加上 $x$，然后全局减去 $x$。

复杂度证明：设区间真正的最大值减最小值为 $len$，不难发现两种操作都用了 $O(k)$ 的时间使得 $len$ 减少了 $O(k)$，所以每一块总复杂度均摊是 $O(V)$ 的。（需要注意的是，这个条件取不取等不会影响复杂度，但是会影响我们的 $mx$ 的重新计算，所以只能用 $2x\ge mx$，否则要重新考虑下文的 $mx$ 计算）

这两种操作都可以看作是把区间 $x$ 变成 $y$，用上文的并查集维护即可，全局减直接打 tag。

进行操作 1 后，将 $mx$ 设为 $x+tag$。（因为 $2x\ge mx$，所以此时所有的数一定小于等于 $x$，加 $tag$ 是为了抵消 $tag$ 的影响。）

进行操作 2 后，直接把 $tag$ 增加 $x$。

遇到散块直接 $O(\sqrt n)$ 还原出每一个元素的真实值然后暴力修改。

总复杂度 $O(V\sqrt n + q\sqrt n)$。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5, Q = 5e5+5, V = 1e5+5;

int a[N];
bitset<Q> cmd_type;
int cmd[Q][3];
int ans[Q];

const int B = 1000;

int mx,tag;
int rt[V],sz[V],fa[B+2]; // rt 和 sz 值域大小，fa 只要块长大小就够了
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

// 显然已经有 x ≠ y
// 把当前这一块里面所有 x 变成 y
void change(int x,int y){
    if(!rt[x])return;
    if(!rt[y]){
        a[rt[x]]=y;
        swap(rt[x],rt[y]);
        swap(sz[x],sz[y]);
    }
    else{
        fa[rt[x]]=rt[y];   
        sz[y]+=sz[x]; sz[x]=0,rt[x]=0;
    }
}

// 计算出当前这一块的真实 a
void calc(int l,int r){
    for(int i=l;i<=r;i++)a[i]=a[find(i)];
    // 要清理 rt,sz 以备后面重新计算，要不然有可能rt和sz只部分清空
    for(int i=l;i<=r;i++)rt[a[i]]=sz[a[i]]=0; 
    if(tag){
        for(int i=l;i<=r;i++)a[i]-=tag;
        tag = 0;
    }
}

// 我们保证在 build 前整个 rt 和 sz 数组都是 0
// fa 不管清不清空都可以，反正只会全部赋值
// 构建出当前这一块的 rt,sz,fa,mx
void build(int l,int r){
    tag = mx = 0;
    for(int i=l;i<=r;i++){
        if(!rt[a[i]])rt[a[i]]=i;  // 第一个数
        fa[i]=rt[a[i]], sz[a[i]]++; // fa,sz
        mx = max(mx, a[i]);
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    
    int n,q; cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=q;i++){
        int op; cin>>op;
        if(op==2)cmd_type[i]=1;
        cin>>cmd[i][0]>>cmd[i][1]>>cmd[i][2];
    }

    for(int l=1,r;l<=n;l=r+1){
        r = min(n, l+B-1);

        for(int i=l;i<=r;i++)a[i-l+1]=a[i]; // 把 [l,r] 平移到 [1,r-l+1]
        build(1,r-l+1); // 建立

        for(int id=1;id<=q;id++){
            int op = (cmd_type[id])?2:1;
            int ql=cmd[id][0],qr=cmd[id][1],x=cmd[id][2];

            ql = max(ql,l); qr = min(qr, r);
            if(ql > qr)continue; // 是否包含在 [l,r]

            ql=ql-l+1, qr=qr-l+1; // 平移 ql, qr

            if(ql == 1 && qr == r-l+1){ // 整块
                if(op==1){
                    int realmx = mx - tag; // 真正的最大值
                    if(x >= realmx) continue;
                    if(realmx <= 2*x){ // [x+1,realmax] 都减去 x
                        for(int i=x+1;i<=realmx;i++)change(i+tag, i-x+tag);
                        mx = x+tag;
                    }
                    else{ // [1,x] 都加上 x
                        for(int i=1;i<=x;i++)change(i+tag,i+x+tag); 
                        tag += x; // 全局减 x
                    }
                }
                else{
                    // x+tag 在当前的范围内，加上 x+tag 的 sz
                    if(x+tag<=mx)ans[id] += sz[x+tag];
                }
            }
            else{ // 散块
                if(op==1){
                    if(x >= mx - tag) continue;
                    calc(1,r-l+1); // 算出 a[1]~a[r-l+1] 真实值
                    for(int i=ql;i<=qr;i++)if(a[i]>x)a[i]-=x; // 暴力修改
                    build(1,r-l+1); // 重新构建这一块
                }
                else{
                    if(x > mx - tag) continue;
                    for(int i=ql;i<=qr;i++){
                        if(a[find(i)]-tag == x)ans[id]++;
                    }
                }
            }
        }

        // 清理自己的 a[i]，因为 rt[x] 的 a 一定是真实值，不需要 find 了
        for(int i=1;i<=r-l+1;i++)rt[a[i]]=sz[a[i]]=0,fa[i]=0;
    }

    for(int i=1;i<=q;i++){
        if(cmd_type[i])cout<<ans[i]<<'\n';
    }

    return 0;
}

问题 5（最初分块）

题目

P4119 [Ynoi2018]未来日记

给定长度为 $n$ 的序列，有 $q$ 个操作：

1. 把 $[l,r]$ 中等于 $x$ 的数改成 $y$。
2. 给定 $[l,r]$，查询区间 $[l,r]$ 第 $k$ 小的数。

$n,q,a_i,x,y,k\le 10^5$。

做法

区间等于 $x$ 的数改成 $y$ 的操作前面已经叙述的很详尽了，我们考虑如何处理区间第 $k$ 大。

如果二分就会多出一个 $\log$，不能接受。
考虑对值域分块，如果我们能预处理出 $cntV[id][x]$ 表示前 $id$ 块有多少个数等于 $x$ 和 $cntB[id][b]$ 表示前 $id$ 块有多少个数在 $b$ 块之内，那么我们查询区间整块可以 $O(1)$ 用前缀和求出，散块直接暴力扫一遍放在一个辅助数组里，我们就可以花费 $O(\sqrt n)$ 预处理后 $O(1)$ 求出 $[l,r]$ 内有多少个数在 $b$ 块和有多少个 $x$。

然后我们在值域上遍历每一块，找到第一次个数大于等于 $k$ 的那一块，答案就在其中，然后暴力枚举这一块的每一个数，直到第一次总个数大于等于 $k$，我们就找到了答案。
复杂度 $O(\sqrt n)$。

考虑在前文写过的并查集的基础上，如何维护 $cntV[id][x]$，$cntB[id][b]$。

初始化直接 $O(n\sqrt n)$ 处理一遍容易解决。

对于每一个区间修改来说，每一块都能求出这一块里面有多少个 $x$ 变成 $y$。我们在外面维护这个个数，然后不断累加，修改后面的每一块，总共只需要修改 $O(\sqrt n)$ 块，复杂度正确。

综上，我们就成功在 $O((n+q)\sqrt n)$ 的复杂度内解决了本题。（具体见代码）

再介绍一个卡常技巧：在问题 1，问题 2 中的代码中，我们的分块两边一定都有一个散块（问题 3，问题 4 因为块离线了没有这个问题），如果 $l,r$ 正好在某一个块的边界，我们就把一个整块当作散块处理了，这是我们不愿意看到的。（虽然不影响复杂度）
为了解决这个，我们令 $l'=l-1,r'=r+1$，然后处理开区间 $(l',r')$，里面的整块 $bel[l']+1\sim bel[r']-1$ 能包含恰好在边界的情况，两边散块有可能是空的，判断一下就好了。

#include<bits/stdc++.h>
using namespace std;


const int N = 1e5+5;
const int B = 500, BV = 300;

int bel[N],rht[N/B+5],lft[N/B+5];
int belV[N],rhtV[N/BV+5],lftV[N/BV+5]; // 不会修改 

int rt[N/B+5][N],fa[N],sz[N],a[N]; 
int cntV[N/B+5][N],cntB[N/B+5][N/BV+5];
int tmpV[N],tmpB[N/BV+5];


inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

// 修改第 id 块中的 [l,r] 部分
// 会维护rt,fa,sz，但是**不处理** cntV 和 cntB 数组，只返回当前改了几个
inline int modify1(int id,int l,int r,int x,int y){
    if(l>r)return 0; // 没有这一块
    for(int i=lft[id];i<=rht[id];i++)a[i]=a[find(i)];
    sz[rt[id][x]]=sz[rt[id][y]]=0;
    rt[id][x]=rt[id][y]=0;  // fa 不用清空，因为之后都是赋值
    int ret = 0; // 变了几个 x
    for(int i=lft[id];i<=rht[id];i++){
        if(a[i] != x && a[i] != y) continue;
        if(l <= i && i <= r && a[i] == x)a[i]=y,++ret;

        if(!rt[id][a[i]])rt[id][a[i]]=i;
        ++sz[rt[id][a[i]]],fa[i]=rt[id][a[i]];
    }
    return ret;
}
// 修改整个第 id 块
// 会维护rt,fa,sz，但是**不处理** cntV 和 cntB 数组，只返回当前改了几个
inline int modify2(int id,int x,int y){
    if(!rt[id][x])return 0; // 没有 x
    if(!rt[id][y]){ // 没有 y
        // 不需要动 sz 数组，因为 sz 本来就放在 rt[id][x] 的位置
        swap(rt[id][y], rt[id][x]); 
        a[rt[id][y]]=y;
        return sz[rt[id][y]];
    }
    else{ // 都有
        fa[rt[id][x]] = rt[id][y];
        sz[rt[id][y]] += sz[rt[id][x]];
        int ret = sz[rt[id][x]];
        sz[rt[id][x]]=0; rt[id][x] = 0;
        return ret;
    }
}

// 截止到 id 块，前面一共进行了 cnt 个 x 变 y
inline void upd(int id,int x,int y,int cnt){
    if(!cnt)return;
    cntV[id][x]-=cnt;       cntV[id][y] += cnt;
    cntB[id][belV[x]]-=cnt; cntB[id][belV[y]]+=cnt;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    for(int i=0;i<N;i++){
        belV[i]=(i-1)/BV+1;
        if(!lftV[belV[i]])lftV[belV[i]]=i;
        rhtV[belV[i]]=i;
    }
    const int maxbv = N/BV+1;

    int n,q; cin>>n>>q;

    for(int i=1;i<=n;i++){
        cin>>a[i];
        bel[i] = (i-1)/B+1;
        if(!lft[bel[i]])lft[bel[i]]=i;
        rht[bel[i]]=i;
    }
    bel[n+1]=bel[n]+1;
    lft[bel[n]+1]=rht[bel[n]+1]=n+1;

    int maxb = bel[n];
    for(int id=1;id<=maxb;id++){
        for(int i=lft[id];i<=rht[id];i++){
            if(!rt[id][a[i]])rt[id][a[i]]=i;
            ++sz[rt[id][a[i]]],fa[i]=rt[id][a[i]];
            ++cntV[id][a[i]]; ++cntB[id][belV[a[i]]];
        }

        for(int i=1;i<N;i++)     cntV[id][i]+=cntV[id-1][i];
        for(int i=1;i<=maxbv;i++)cntB[id][i]+=cntB[id-1][i];
    }

    while(q--){
        int op,l,r; cin>>op>>l>>r;
        --l,++r; // **注意**：处理开区间 (l,r)
        if(op==1){
            int x,y; cin>>x>>y;
            if(x==y)continue; // 先特判 x=y
            if(bel[l]==bel[r]){ // 都在一块之内
                int cur = modify1(bel[l],l+1,r-1,x,y);
                if(cur)for(int id=bel[l];id<=maxb;id++)upd(id,x,y,cur);
            }
            else{
                int cur = 0; // 目前已经换掉了多少个 x
                // 左边可能有的散块
                cur += modify1(bel[l],l+1,rht[bel[l]],x,y), upd(bel[l], x, y, cur);
                // 中间
                for(int id=bel[l]+1;id<=bel[r]-1;++id)
                    cur += modify2(id,x,y), upd(id,x,y,cur);
                // 右边可能有的散块
                cur += modify1(bel[r],lft[bel[r]],r-1,x,y), upd(bel[r], x, y, cur);
                // 后面其他的块更新前缀和
                for(int id=bel[r]+1;id<=maxb;id++)upd(id, x, y, cur);
            }
        }
        else{
            int k; cin>>k;  
            if(bel[l] == bel[r]){
                for(int i=l+1;i<=r-1;i++)a[i] = a[find(i)],++tmpV[a[i]],++tmpB[belV[a[i]]]; 
                int idv = 1, cur = tmpB[idv];
                while(cur < k){
                    ++idv; cur += tmpB[idv];
                }
                cur -= tmpB[idv];
                for(int iv=lftV[idv];iv<=rhtV[idv];++iv){
                    cur += tmpV[iv];
                    if(cur >= k){
                        cout << iv << '\n';
                        break;
                    }
                }
                for(int i=l+1;i<=r-1;i++)--tmpV[a[i]],--tmpB[belV[a[i]]]; 
            }   
            else{
                // 加上散块的内容
                for(int i=l+1;i<=rht[bel[l]];i++) a[i]=a[find(i)],++tmpV[a[i]],++tmpB[belV[a[i]]]; 
                for(int i=lft[bel[r]];i<=r-1;i++) a[i]=a[find(i)],++tmpV[a[i]],++tmpB[belV[a[i]]]; 

                #define cnt_block(x) (tmpB[x]+cntB[bel[r]-1][x]-cntB[bel[l]][x]);
                #define cnt_value(x) (tmpV[x]+cntV[bel[r]-1][x]-cntV[bel[l]][x]);
                int idv = 1, cur = cnt_block(1);
                while(cur < k){
                    ++idv; cur += cnt_block(idv);
                }
                cur -= cnt_block(idv);

                for(int iv=lftV[idv];iv<=rhtV[idv];++iv){
                    cur += cnt_value(iv);
                    if(cur >= k){
                        cout << iv << '\n';
                        break;
                    }
                }
                // 还原
                for(int i=l+1;i<=rht[bel[l]];i++) --tmpV[a[i]],--tmpB[belV[a[i]]]; 
                for(int i=lft[bel[r]];i<=r-1;i++) --tmpV[a[i]],--tmpB[belV[a[i]]]; 
            }
        }
    }
    return 0;
}