Luogu

分析

先考虑没有修改怎么用分块做。

一个想法是将序列分块，然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，然而这样子查询是 $\mathcal{O}(n)$ 的。

因此我们再对值域分块，并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量，询问时先把所求在值域的哪一块中求出来，再在这一块中求，复杂度 $\mathcal{O}(\sqrt{n})$。

现在加入修改，可以想到对每块开一个并查集并把相同的数并在一起。这样子整块修改直接合并并维护一下 $s$ 和 $s'$，散块修改直接重构修改前后的两个值对应的并查集即可。

不知道为啥块长调到 $600$ 才能过 /kel

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=166+10;
const int B=600,V=100000;

int n,m,a[N];
int bl[N],L[M],R[M],s[M][N],sb[M][M],c[M][N],o[N],ob[M];

int f[N],rt[M][N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

void modify(int l,int r,int x,int y) {
    for (int i=L[bl[l]];i<=R[bl[l]];++i) a[i]=a[find(i)];
    rt[bl[l]][x]=rt[bl[l]][y]=0; int sx=0;
    for (int i=l;i<=r;++i) if (a[i]==x) a[i]=y,++sx;
    for (int i=L[bl[l]];i<=R[bl[l]];++i) if (a[i]==x||a[i]==y) f[i]=i;
    for (int i=L[bl[l]];i<=R[bl[l]];++i) {
        if (a[i]!=x&&a[i]!=y) continue;
        if (!rt[bl[l]][a[i]]) rt[bl[l]][a[i]]=i;
        else f[i]=rt[bl[l]][a[i]];
    }
    c[bl[l]][x]-=sx,c[bl[l]][y]+=sx;
    for (int i=bl[l];i<=bl[n];++i)
        s[i][x]-=sx,s[i][y]+=sx,sb[i][bl[x]]-=sx,sb[i][bl[y]]+=sx;
}

int main() {
    n=read(),m=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=V;++i) bl[i]=(i-1)/B+1;
    for (int i=1;i<=n;++i) f[i]=i;
    for (int i=1;i<=bl[n];++i) {
        L[i]=(i-1)*B+1,R[i]=min(i*B,n);
        for (int j=1;j<=V;++j) s[i][j]=s[i-1][j];
        for (int j=1;j<=bl[V];++j) sb[i][j]=sb[i-1][j];
        for (int j=L[i];j<=R[i];++j) {
            ++c[i][a[j]],++s[i][a[j]],++sb[i][bl[a[j]]];
            if (!rt[i][a[j]]) rt[i][a[j]]=j;
            else f[j]=rt[i][a[j]];
        }
    }
    while (m--) {
        int op=read();
        if (op==1) {
            int l=read(),r=read(),x=read(),y=read();
            if (x==y) continue;
            if (bl[l]==bl[r]) modify(l,r,x,y);
            else {
                modify(l,R[bl[l]],x,y),modify(L[bl[r]],r,x,y);
                int sx=0;
                for (int i=bl[l]+1;i<=bl[r]-1;++i) {
                    if (rt[i][x]) {
                        if (!rt[i][y]) rt[i][y]=rt[i][x],a[rt[i][x]]=y;
                        else f[rt[i][x]]=rt[i][y];
                        sx+=c[i][x],c[i][y]+=c[i][x],c[i][x]=rt[i][x]=0;
                    }
                    s[i][x]-=sx,s[i][y]+=sx,sb[i][bl[x]]-=sx,sb[i][bl[y]]+=sx;
                }
                for (int i=bl[r];i<=bl[n];++i)
                    s[i][x]-=sx,s[i][y]+=sx,sb[i][bl[x]]-=sx,sb[i][bl[y]]+=sx;
            }
        } else {
            int l=read(),r=read(),k=read();
            if (bl[l]==bl[r]) {
                for (int i=l;i<=r;++i) a[i]=a[find(i)];
                for (int i=l;i<=r;++i) ++o[a[i]],++ob[bl[a[i]]];
                for (int i=1,cnt=0;i<=bl[V];++i) {
                    if (cnt+ob[i]>=k) {
                        for (int j=L[i];j<=R[i];++j) {
                            cnt+=o[j];
                            if (cnt>=k) { printf("%d\n",j); break; }
                        }
                        break;
                    }
                    cnt+=ob[i];
                }
                for (int i=l;i<=r;++i) --o[a[i]],--ob[bl[a[i]]];
            } else {
                for (int i=l;i<=R[bl[l]];++i) a[i]=a[find(i)];
                for (int i=L[bl[r]];i<=r;++i) a[i]=a[find(i)];
                for (int i=l;i<=R[bl[l]];++i) ++o[a[i]],++ob[bl[a[i]]];
                for (int i=L[bl[r]];i<=r;++i) ++o[a[i]],++ob[bl[a[i]]];
                for (int i=1,cnt=0;i<=bl[V];++i) {
                    int now=ob[i]+sb[bl[r]-1][i]-sb[bl[l]][i];
                    if (cnt+now>=k) {
                        for (int j=L[i];j<=R[i];++j) {
                            cnt+=o[j]+s[bl[r]-1][j]-s[bl[l]][j];
                            if (cnt>=k) { printf("%d\n",j); break; }
                        }
                        break;
                    }
                    cnt+=now;
                }
                for (int i=l;i<=R[bl[l]];++i) --o[a[i]],--ob[bl[a[i]]];
                for (int i=L[bl[r]];i<=r;++i) --o[a[i]],--ob[bl[a[i]]];
            }
        }
    }
    return 0;
}