LuoguP4119 [Ynoi2018] 未来日记

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,S=452,M=N/S+5,SS=385,MM=N/SS+5;
int n,m,b[M][S+5],sz[M],L[M],cnt[M][N],cntS[M][MM],F[M][S+5],H[M][N],tot,stk[N],top,tcnt[N],tcntS[MM],T[M];
I int Find(CI k,CI x,CI t=0){return x==F[k][x]?x:F[k][x]=Find(k,F[k][x],t);}//并查集
I void B(CI k,CI x=-1,CI y=-1,CI l=0,CI r=0,CI v=0){//暴力重构块
    RI i,t;for(i=0;i<sz[k];i++) t=b[k][Find(k,i,1)],b[k][i]=t,H[k][t]=-1;//并查集重置
    if(~x) for(i=(v?l:0);i<=(v?r:sz[k]-1);i++) if(b[k][i]==x) b[k][i]=y,T[k]++;//暴力修改
    for(i=0;i<sz[k];i++) F[k][i]=((~H[k][b[k][i]])?H[k][b[k][i]]:H[k][b[k][i]]=i);//重构并查集
}
I void P(CI k,CI l,CI r,CI x,CI y){RI i;B(k,x,y,l,r,1);}//边角暴力重构
I void R(CI x,CI y){RI i,t=0;for(i=1;i<=tot;i++) t+=T[i],cnt[i][x]-=t,cntS[i][x/SS]-=t,cnt[i][y]+=t,cntS[i][y/SS]+=t,T[i]=0;}//开临时数组记录，最后直接扫一遍累加更新前缀和
I void U(RI l,RI r,CI x,CI y){
    if(x==y) return ;RI i,bL=(l-1)/S+1,bR=(r-1)/S+1;if(l-=L[bL],r-=L[bR],bL==bR) return P(bL,l,r,x,y),R(x,y);
    for(P(bL,l,sz[bL]-1,x,y),P(bR,0,r,x,y),i=bL+1;i<=bR-1;i++) if(cnt[i][x]^cnt[i-1][x]&&cnt[i][y]==cnt[i-1][y]) T[i]+=cnt[i][x]-cnt[i-1][x],F[i][H[i][x]]=H[i][y]=H[i][x],b[i][H[i][x]]=y,H[i][x]=-1;//如果没有y，直接映射
    else if(cnt[i][x]^cnt[i-1][x]&&cnt[i][y]^cnt[i-1][y]) B(i,x,y);return R(x,y);//如果有y，直接暴力重构
}
I void G(CI k,CI l,CI r){RI i;for(i=l;i<=r;i++) stk[++top]=b[k][Find(k,i)],tcnt[stk[top]]++,tcntS[stk[top]/SS]++;}//散块暴力统计
I void C(){W(top) tcnt[stk[top]]--,tcntS[stk[top]/SS]--,top--;}//记得清空
I int Q(RI l,RI r,RI k){//值域分块，基本套路
    RI i,j,bL=(l-1)/S+1,bR=(r-1)/S+1;if(l-=L[bL],r-=L[bR],bL==bR) for(G(bL,l,r),i=0;;i++) if(tcntS[i]<k) k-=tcntS[i];
    else for(j=SS*i;;j++) if(k>tcnt[j]) k-=tcnt[j];else return C(),j;
    else for(G(bL,l,sz[bL]-1),G(bR,0,r),i=0;;i++) if(k>tcntS[i]+cntS[bR-1][i]-cntS[bL][i]) k-=tcntS[i]+cntS[bR-1][i]-cntS[bL][i];
    else for(j=SS*i;;j++) if(k>tcnt[j]+cnt[bR-1][j]-cnt[bL][j]) k-=tcnt[j]+cnt[bR-1][j]-cnt[bL][j];else return C(),j;
}
int main(){
    RI i,j,k,opt,l,r,x,y;for(read(n,m),i=1;i<=n;i++) read(x),!((i-1)%S)&&(L[++tot]=i),b[tot][sz[tot]++]=x;
    memset(F,-1,sizeof(F));memset(H,-1,sizeof(H));for(i=1;i<=tot;i++) for(j=0;j<sz[i];j++) for(F[i][j]=((~H[i][b[i][j]])?H[i][b[i][j]]:H[i][b[i][j]]=j),k=i;k<=tot;k++) cnt[k][b[i][j]]++,cntS[k][b[i][j]/SS]++;
    W(m--) if(read(opt,l,r,x),opt==1) read(y),U(l,r,x,y);else writeln(Q(l,r,x));return 0;
}