emm自己想这道题想到一个nlog^2的东西，空间是nlog的，因为空间常数太大大概是过不了的，在这里想分享一下（而且也不知道可不可行）

就是首先建出来操作树，然后每个节点由于都是因为新加了一条边，必然合并了某两个连通块，然后这个节点我们开一个权值线段树记录下来这个新的连通块的点权，然后我们需要的几个操作如下：

1, 支持合并查k大的权值线段树

2，快速找到某一个节点最后一个被更新的位置（方便合并）这个我们可以用可持久化并查集合并，然后暴力用主席树记录每一个代表元素所最后一次被更新的位置。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,w[N],P[N],id_p,root[N],tot;
//外面的root代表每一个操作对应的编号，内层的root代表操作编号所对应的树上节点
void divide(void)
{
 for(int i=1;i<=n;i++) P[++id_p]=w[i];
 sort(P+1,P+n+1);
 id_p=unique(P+1,P+n+1)-P-1;
 for(int i=1;i<=n;i++) w[i]=lower_bound(P+1,P+id_p+1,w[i])-P;
 P[0]=-1;
}//离散化

struct Segment1
{
 int ls[5*N],rs[5*N],sum[5*N],root[N],tot;
 void insert(int &p,int l,int r,int site)
 {
     if(!p) p=++tot;  //注意动态开点
     sum[p]++;
     if(l==r) return;
     int mid=(l+r)>>1;
     if(site<=mid) insert(ls[p],l,mid,site);
     else insert(rs[p],mid+1,r,site);
 }
 int ask(int p,int l,int r,int k)
 {
     if(k>sum[p]) return 0;  //P[0]=-1;  
     if(l==r) return l;
     int mid=(l+r)>>1;
     if(sum[ls[p]]>=k) return ask(ls[p],l,mid,k);
     else return ask(rs[p],mid+1,r,k-sum[ls[p]]);
 }
 int Merge(int l,int r)
 {
     if(!l || !r) return l+r;
     int u=++tot;//不覆盖原本节点
     sum[u]=sum[l]+sum[r];
     ls[u]=Merge(ls[l],ls[r]);
     rs[u]=Merge(rs[l],rs[r]);
     return u;
 }
 //插入 合并 查第k大
}T1;

struct Segment2
{
 int ls[5*N],rs[5*N],fa[5*N],ize[5*N],val[5*N],tot,root[N];
 //实现可持久化并查集 以及记录每一个代表节点最后一次被修改的操作编号
 void build(int &p,int l,int r)
 {
     if(!p) p=++tot;
     if(l==r) {fa[p]=l;ize[p]=1;val[p]=0;return;}  //初始化,一开始每一个节点都没有被修改
     int mid=(l+r)>>1;
     build(ls[p],l,mid);build(rs[p],mid+1,r);
 }
 void insert(int &p_now,int p_ago,int l,int r,int site,int a,int b,int c)
 {
     p_now=++tot;
     ls[p_now]=ls[p_ago];rs[p_now]=rs[p_ago];
     if(l==r) {fa[p_now]=a;ize[p_now]=b;val[p_now]=c;return;}  //只修改叶节点即可,可持久化数组
     int mid=(l+r)>>1;
     if(site<=mid) insert(ls[p_now],ls[p_ago],l,mid,site,a,b,c);
     else insert(rs[p_now],rs[p_ago],mid+1,r,site,a,b,c);
 }
 int ask(int p,int l,int r,int site,int &b,int &c)  //返回可持久化数组该位置的三个元素
 {
     if(l==r) 
     {
         b=ize[p];c=val[p];
         return fa[p];
     }
     int mid=(l+r)>>1;
     if(site<=mid) return ask(ls[p],l,mid,site,b,c);
     else return ask(rs[p],mid+1,r,site,b,c);
 }
 int find(int x,int root)  //并查集 不用路径压缩
 {
     int b,c,a=ask(root,1,n,x,b,c);
     if(a==x) return x;
     return find(a,root);
 }
}T2;

void Merge(int x,int y,int s,int &id)  //实现合并并查集和线段树，更新代表节点最后一次被修改的操作编号
{
 int ize_x,ize_y,opt_x,opt_y;
 int a=T2.find(x,T2.root[s]),b=T2.find(y,T2.root[s]);
 if(a==b) {id=s;tot--;return;}
 T2.ask(T2.root[s],1,n,a,ize_x,opt_x);T2.ask(T2.root[s],1,n,b,ize_y,opt_y);
 //首先找到x,y代表元素以及其的ize val
 //cout<<ize_x<<" "<<opt_x<<" "<<ize_y<<" "<<opt_y<<endl;
 int u=T1.root[opt_x],v=T1.root[opt_y];
 if(!opt_x) u=0,T1.insert(u,1,id_p,w[a]);
 if(!opt_y) v=0,T1.insert(v,1,id_p,w[b]);
 T1.root[id]=T1.Merge(u,v);   //在线段树1将合并
 
 if(ize_x>ize_y) swap(x,y);
 T2.insert(T2.root[id],T2.root[s],1,n,a,b,0,0);
 T2.insert(T2.root[id],T2.root[id],1,n,b,b,ize_x+ize_y,id);
 //按秩合并 更新a的代表元素 更新b的size以及val
}

int ask(int x,int y,int s)  //找到最后一次被修改的操作编号，并利用其线段树查k大
{
 int a=T2.find(x,T2.root[s]),ize,opt;
 T2.ask(T2.root[s],1,n,a,ize,opt);
 if(!opt) return (y==1);
 return T1.ask(T1.root[opt],1,id_p,y);
}

int main(void)
{
 scanf("%d%d",&n,&m);
 T2.build(T2.root[0],1,n);
 for(int i=1;i<=n;i++) scanf("%d",&w[i]);
 divide();
 for(int i=1,p=0;i<=m;i++)
 {
     int opt,x,y;
     scanf("%d",&opt);
     if(opt==1) 
     {
         scanf("%d%d",&x,&y);
         Merge(x,y,p,root[i]=++tot);
         p=root[i];
     }
     if(opt==2)
     {
         scanf("%d",&x);
         p=root[x];
     }
     if(opt==3)
     {
         scanf("%d%d",&x,&y);
         printf("%d\n",P[ask(x,y,p)]);
     }
     root[i]=p;
 }
 
 return 0;
}

代码放这了，（不知道代码有没有写挂） 不知道能不能成，求助各位大佬