TLE on #14 569ms/19.99MB 求调

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
template<typename Tp> Tp read() {
    Tp x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
template<typename Tp> void write(Tp x) {
    if(x<0) {putchar('-');x=-x;}
    static int sta[45];int top=0;
    do {sta[top++]=x%10;x/=10;} while(x);
    while(top) putchar(sta[--top]+'0');
}
constexpr int N=1e5+5;
int n,m,block=4970,k,a[N],ord[N],num[N],vtx[N],buc[N][22],ans[N];
inline int st(int x) {
    return (x-1)*block+1;
}
inline int ed(int x) {
    return x*block;
}
inline int bel(int x) {
    return (x-1)/block+1;
}
int fa[N],siz[N];
inline int find(int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}
struct Option {
    int op,x,y;
} b[N];
struct enode {
    int nxt,to;
} edge[N];
int tot,head[N];
void add(int u,int v) {
    edge[++tot]={head[u],v};
    head[u]=tot;
}
void lsh() {
    sort(ord+1,ord+n+1);
    for(int i=1;i<=n;i++) {
        a[i]=lower_bound(ord+1,ord+n+1,a[i])-ord;
        a[i]+=num[a[i]]++;
        vtx[a[i]]=i;
    }
}
void dfs(int u) {
    int op=b[u].op,x=b[u].x,y=b[u].y,fx=0,fy=0;
    if(op!=2) fx=find(x);
    if(op==1) {
        fy=find(y);
        if(fx!=fy) {
            if(siz[fx]>siz[fy]) swap(fx,fy);
            fa[fx]=fy,siz[fy]+=siz[fx];
            for(int i=1;i<=k;i++) buc[fy][i]+=buc[fx][i];
        }
    }
    else if(op==3) {
        if(siz[fx]<y) ans[u]=-1;
        else {
            for(int i=1;i<=k;i++) {
                if(y<=buc[fx][i]) {
                    int L=st(i),R=ed(i);
                    for(int j=L;j<=R;j++) {
                        int node_id=vtx[j];
                        int root=find(node_id);
                        if(root==fx) {
                            if(--y==0) {
                                ans[u]=ord[j];
                                break;
                            }
                        }
                    }
                    break;
                }
                y-=buc[fx][i];
            }
        }
    }
    for(int i=head[u];i;i=edge[i].nxt) {
        int v=edge[i].to;
        dfs(v);
    }
    if(op==1) {
        if(fx!=fy) {
            fa[fx]=fx,siz[fy]-=siz[fx];
            for(int i=1;i<=k;i++) buc[fy][i]-=buc[fx][i];
        }
    }
}
int main() {
    n=read<int>(),m=read<int>();
    for(int i=1;i<=n;i++) ord[i]=a[i]=read<int>();
    lsh();
    k=n/block+(n%block>0);
    for(int i=1;i<=m;i++) {
        b[i].op=read<int>(),b[i].x=read<int>();
        if(b[i].op==2) add(b[i].x,i);
        else {
            b[i].y=read<int>();
            add(i-1,i);
        }
    }
    for(int i=1;i<=n;i++) {
        fa[i]=i,siz[i]=1;
        buc[i][bel(a[i])]=1;
    }
    dfs(0);
    for(int i=1;i<=m;i++)
        if(b[i].op==3) {
            write(ans[i]);putchar('\n');
        }
    return 0;
}