【题解】「Ynoi2018」未来日记 分块+并查集 — Qiuly

查询 $kth$ 的话，就分块来讲，通常可以考虑值域分块。

具体操作就是将值域分块，然后询问的时候先确定块，再确定目标位置。

令 $sum_{i,j}$ 表示前 $i$ 个序列块，第 $j$ 个数值块的出现次数；$cnt_{i,j}$ 表示前 $i$ 个序列块，第 $j$ 个数的出现次数。

这样话查询的时候拿个桶记录一下散块贡献即可。

修改的话其实就是从左端点的块一直修改到最后面的块，更新 $sum,cnt$ 即可。

这下子就有一个问题：当处理散块时，需要直接访问 $a_i$ 。这就意味着 $a_i$ 必须支持实时查询。怎么维护 $a_i$ 呢？这个时候我们可以想到第二分块中用并查集维护 “ 将所有 $x$ 修改为 $y$ ” 的操作，照搬即可。

关于实现：

• 代码量不算很大，也不怎么卡常，细节也不是很多。（总之很好写
• 注意到 $c$ 数组其实是一个 $n\sqrt{n}$ 大小的数组：
  • 如果第一维开 $n$ ，第二维开 $\sqrt{n}$ ：修改的时候内存访问所占常数太大。
  • 如果第一维开 $\sqrt{n}$ ，第二维开 $n$ ：这样的话内存访问就舒服不少。实测快了不少。
• 并查集的 merge ：如果没有 $x$ 这个颜色就跳过。实测快了不少。（卡了这个点就过了，之前一直是 $64\ pts$
• 如果硬说细节的话：更新 $sum,cnt$ 的时候注意一下更新顺序。

吐槽：感觉这题比第二分块简单一些（

const int N=1e5+5;
const int S=5e2+5;
const int M=1e5;

int n,m,x,y,a[N];

// {{{ Data_Struct_Block

int sqrtn,L[S],R[S],id[N],mi[S],mx[S],blo[N];
int sum[S][S],cnt[N][S],tmp_sum[S],tmp_cnt[N];

// {{{ Data_Struct_Dsu

int rt[S][N],col[N],fa[N];
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}

inline void merge(const int &t) {
    if(!rt[t][x]) return ;
    if(!rt[t][y]) rt[t][y]=rt[t][x],col[rt[t][y]]=y;
    else fa[rt[t][x]]=rt[t][y];
    rt[t][x]=0;
}
inline void rebuild(const int &t,int l,int r) {
    lep(i,L[t],R[t]) a[i]=col[find(i)],rt[t][a[i]]=0;
    lep(i,l,r) if(a[i]==x) a[i]=y;

    lep(i,L[t],R[t]) {
        if(!rt[t][a[i]]) col[rt[t][a[i]]=i]=a[i];
        fa[i]=rt[t][a[i]];
    }
}

// }}}

inline void init() {
    sqrtn=sqrt(n*3/5+1);
    for(int i=1,c=1,j;i<=n;i=j+1,++c) { // seq_block
        L[c]=i,R[c]=j=min(n,i+sqrtn-1);
        lep(t,L[c],R[c]) id[t]=c;
    }
    for(int i=1,c=1,j;i<=M;i=j+1,++c) { // num_block
        mi[c]=i,mx[c]=j=min(M,i+315);
        lep(t,mi[c],mx[c]) blo[t]=c;
    }

    lep(c,1,id[n]) { // cnt & sum
        COPY(sum[c],sum[c-1]);
        lep(i,1,M) cnt[i][c]=cnt[i][c-1];
        lep(i,L[c],R[c]) ++cnt[a[i]][c],++sum[c][blo[a[i]]];
    }
    lep(c,1,id[n]) lep(i,L[c],R[c]) { // dsu
        if(!rt[c][a[i]]) col[rt[c][a[i]]=i]=a[i];
        fa[i]=rt[c][a[i]];
    }
}

inline void modify(int l,int r) {
    if(x==y) return ;

    int res=0,tmp=0,v1=0,v2=0;
    #define upd1 (sum[i][blo[x]]-=res,sum[i][blo[y]]+=res)
    #define upd2 (cnt[x][i]-=res,cnt[y][i]+=res)

    if(id[l]==id[r]) {
        lep(i,l,r) if(col[find(i)]==x) ++res;
        if(!res) return ;
        lep(i,id[r],id[n]) upd1,upd2;
        rebuild(id[l],l,r);
    } else {
        lep(i,l,R[id[l]]) if(col[find(i)]==x) ++res,++v1;
        lep(i,id[l],id[r]-1) res+=tmp,upd1,tmp=cnt[x][i+1]-cnt[x][i],upd2;
        lep(i,L[id[r]],r) if(col[find(i)]==x) ++res,++v2;
        lep(i,id[r],id[n]) upd1,upd2;

        lep(i,id[l]+1,id[r]-1) merge(i);
        if(v1) rebuild(id[l],l,R[id[l]]);
        if(v2) rebuild(id[r],L[id[r]],r);
    }
}
inline void query(int l,int r) {
    int tmp;
    const bool _=(id[l]!=id[r]);
    #define add (tmp=col[find(i)],++tmp_cnt[tmp],++tmp_sum[blo[tmp]])
    #define del (tmp=col[find(i)],--tmp_cnt[tmp],--tmp_sum[blo[tmp]])

    if(_) {lep(i,l,R[id[l]]) add; lep(i,L[id[r]],r) add;}
    else lep(i,l,r) add;

    int res=0,ans=-1;
    lep(t,1,blo[M]) {
        int now=tmp_sum[t]+sum[id[r]-_][t]-sum[id[l]][t];
        if(res+now>=x) lep(i,mi[t],mx[t]) {
            res+=tmp_cnt[i]+cnt[i][id[r]-_]-cnt[i][id[l]];
            if(res>=x) {ans=i; break;}
        }
        if(~ans) break; res+=now;
    }
    printf("%d\n",ans);

    if(_) {lep(i,l,R[id[l]]) del; lep(i,L[id[r]],r) del;}
    else lep(i,l,r) del;
}

// }}}

int op,l,r;
int main() {
    IN(n,m);
    lep(i,1,n) IN(a[i]);
    init();

    while(m--) {
        IN(op,l,r);
        if(op==1) IN(x,y),modify(l,r);
        if(op==2) IN(x),query(l,r);
    }
    return 0;
}