题解：[Ynoi2014] 等这场战争结束之后

· · 题解

一个很 naive 的做法。

首先，可以先建出操作树，及对于第 i 次操作，若为 2，x 向 i 连边，否则 i-1 向 i 连边，然后我们可以在树上 DFS 一遍求出所有答案。

也就是说，我们要支持连边删边和动态维护连通块内权值信息。

将权值离散化，由于后加进来的边一定先删，考虑并查集+分块，维护连通块中每一块的每一种权值个数。

这样的时空复杂度均为 O(n\sqrt n)，由于毒瘤的空间被卡掉了。

但您可以直接把块长调为 20，然后我 T 了一个点。

但我们可以把分块的数组开成 short，因为 n/块大小 不会炸 short，我们便可以调块长为 40，可以轻松通过。

#include<cstdio>
#include<algorithm>
#define re register
using namespace std;
#define gc getchar
inline int read(){
    re int t=0;re char v=gc();
    while(v<'0')v=gc();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
    return t;
}
int n,m,A[100002],B[100002],head[100002],cnt,ans[100002],blk,K,fa[100002],sz[100002];
short f[100002][47];
char typ[100002];
struct edge{int to,next;}e[100002];
struct node{int x,y;bool operator <(const node &a)const{return x<a.x;};}p[100002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline int root(re int x){return x==fa[x]?x:root(fa[x]);}
inline void dfs(re int x){
    re bool kk=0;
    if(typ[x]==1){
        A[x]=root(A[x]),B[x]=root(B[x]);
        if(A[x]^B[x]){
            kk=1;
            if(sz[A[x]]>sz[B[x]])A[x]^=B[x]^=A[x]^=B[x];
            fa[A[x]]=B[x],sz[B[x]]+=sz[A[x]];
            for(re int i=1;i<=K;++i)f[B[x]][i]+=f[A[x]][i];
        }
    }
    else if(typ[x]==3){
        re int s=B[x],y=0,R=root(A[x]);
        if(s>sz[R])ans[x]=-1;
        else{
            for(re int i=1;i<=K&&!y;++i){
                if(s>f[R][i])s-=f[R][i];
                else y=i;
            }
            for(re int i=(y-1)*blk+1;i<=y*blk&&s;++i)if(root(p[i].y)==R)--s,ans[x]=p[i].x;
        }
    }
    for(re int i=head[x];i;i=e[i].next)dfs(e[i].to);
    if(kk){
        for(re int i=1;i<=K;++i)f[B[x]][i]-=f[A[x]][i];
        fa[A[x]]=A[x],sz[B[x]]-=sz[A[x]];
    }
}
int main(){
    n=read(),m=read(),blk=46,blk=n/blk,K=(n-1)/blk+1;
    for(re int i=1;i<=n;++i)p[i]=(node){read(),i},sz[fa[i]=i]=1;
    sort(p+1,p+n+1);
    for(re int i=1;i<=n;++i){
        re int x=(i-1)/blk+1;
        ++f[p[i].y][x];
    }
    for(re int i=1;i<=m;++i){
        typ[i]=read();
        if(typ[i]==1)add(i-1,i),A[i]=read(),B[i]=read();
        else if(typ[i]==2)add(read(),i);
        else add(i-1,i),A[i]=read(),B[i]=read();
    }
    dfs(0);
    for(re int i=1;i<=m;++i)if(typ[i]==3)printf("%d\n",ans[i]);
}