区间x->y，kth值...

不管了，先序列分块...

查询

第k值，假定知道每个数的权值，对值域分块。

对于整块，维护前\(i\)个块当中，值域在\(j\)块里以及值为\(j\)的数的个数，可以方便的询问。

对于边角，直接记值域在\(j\)块里以及值为\(j\)的数的个数，显然\(o(\sqrt n)\)。

那么接下来只要先按值域块扫，确定第k值在哪个值域块内，然后块内扫一遍，复杂度\(o(\sqrt n)\)。

修改

对于边角，大力重构，暴力修改 前\(i\)个块当中，值域在\(j\)块里以及值为\(j\)的数的个数。

对于整块，可以维护一个并查集，每个点指向相同权值的位置，用top数组记录每种权值的并查集顶端位置。然后x->y就很轻松了对吧...从左到右逐块累加，修改 前\(i\)块 值域在\(j\)块里以及值为\(j\)的数的个数。

总体复杂度\(o((n+m) \sqrt n)\)。

#include
    
     #define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)#define mem(a,b) memset(a,b,sizeof a )#define debug(a) cerr<<#a<<' '<
     <<"___"<
      
       47);}const int mn=100005;const int BLK1=290;const int BLK2=320;int n,K,K1,val[mn],F[BLK2][BLK1],T[mn][BLK1];//F[i][j] 值域i块，在前j块里的数个数//T[i][j] 值i，在前j块里的数个数 int fa[mn];int find(int x){    return fa[x]==x?x:fa[x]=find(fa[x]);}int last[mn],top[BLK1][mn];#define get_val(x) val[find(x)]int rebuild(int id,int l1,int r1,int x,int y){    int l=K*id,r=min(K*id+K-1,n),ct=0;    int *tp=top[id];    rep(q,l,r)val[q]=get_val(q),tp[val[q]]=0;    rep(q,l,r){        if(q>=l1&&q<=r1&&val[q]==x)val[q]=y,++ct;        fa[q]=(!last[val[q]]?(tp[val[q]]=q+1,last[val[q]]=q+1):last[val[q]])-1;    }    rep(q,l,r)last[val[q]]=0;    return ct;}void cg(int id,int v,int v1,int num){    int *F1=F[v/K1],*F2=F[v1/K1],*T1=T[v],*T2=T[v1];    rep(q,id,n/K){        F1[q]-=num,F2[q]+=num,T1[q]-=num,T2[q]+=num;    }}void change(int l,int r,int fr,int to){    if(fr==to)return;    int l_id=l/K,r_id=r/K;    if(l_id==r_id){        int ct=rebuild(l_id,l,r,fr,to);        cg(l_id,fr,to,ct);    }else{        int *td,*F1=F[fr/K1],*F2=F[to/K1],*T1=T[fr],*T2=T[to],num=0;        int ct=rebuild(l_id,l,l_id*K+K-1,fr,to);        rep(q,l_id,r_id-1){            F1[q]-=ct,F2[q]+=ct,T1[q]-=ct,T2[q]+=ct;        }                ct+=rebuild(r_id,r_id*K,r,fr,to);                int ld=T1[l_id+1]-T1[l_id];        rep(q,l_id+1,r_id-1){            num+=ld;            ld=T1[q+1]-T1[q];            F1[q]-=num,F2[q]+=num,T1[q]-=num,T2[q]+=num;                        td=top[q];            if(td[fr]){                if(td[to])fa[td[fr]-1]=td[to]-1;                else val[td[fr]-1]=to,td[to]=td[fr];                td[fr]=0;            }        }        num+=ct;        rep(q,r_id,n/K){            F1[q]-=num,F2[q]+=num,T1[q]-=num,T2[q]+=num;        }    }}int X[BLK2],Y[mn];int ask(int l,int r,int k){    int l_id=l/K,r_id=r/K;    int ans=0;    if(l_id==r_id){                rep(q,l,r){            int v=get_val(q);            ++X[v/K1],++Y[v];        }                for(int q=0;;++q){            if(X[q]>=k){                rep(w,q*K1,q*K1+K1-1){                    if(Y[w]>=k){                        ans=w;                        break;                    }                    k-=Y[w];                }                break;            }            k-=X[q];        }                rep(q,l,r){            int v=get_val(q);            --X[v/K1],--Y[v];        }    }else{        rep(q,l,l_id*K+K-1){            int v=get_val(q);            ++X[v/K1],++Y[v];        }        rep(q,r_id*K,r){            int v=get_val(q);            ++X[v/K1],++Y[v];        }                        for(int q=0;;++q){            int v=F[q][r_id-1]-F[q][l_id]+X[q];            if(v>=k){                rep(w,q*K1,q*K1+K1-1){                    if(T[w][r_id-1]-T[w][l_id]+Y[w]>=k){                        ans=w;                        break;                    }                    k-=T[w][r_id-1]-T[w][l_id]+Y[w];                }                break;            }            k-=v;        }                rep(q,l,l_id*K+K-1){            int v=get_val(q);            --X[v/K1],--Y[v];        }        rep(q,r_id*K,r){            int v=get_val(q);            --X[v/K1],--Y[v];        }    }    return ans;}void init(){    rep(q,0,n)fa[q]=q;    rep(q,0,n/K){        int *tp=top[q];        rep(w,q*K,min(n,q*K+K-1)){            fa[w]=(!last[val[w]]?(tp[val[w]]=w+1,last[val[w]]=w+1):last[val[w]])-1;        }        rep(w,q*K,min(n,q*K+K-1))last[val[w]]=0,++F[val[w]/K1][q],++T[val[w]][q];        if(q){            rep(w,0,100000/K1)F[w][q]+=F[w][q-1];            rep(w,0,100000)T[w][q]+=T[w][q-1];        }    }}bool cur2;int main(){//  cerr<<(&cur2-&cur1)/1024.0/1024<