永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000
对于 100%的数据 n≤100000,m≤n，q≤300000
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
权值线段树合并，将并查集连接时将线段树合并，最后查询根节点的值就好了
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 struct trnt{ 5 int ls; 6 int rs; 7 int wgt; 8 }tr[8000000],str; 9 int fa[500000]; 10 int imp[500000]; 11 int root[500000]; 12 int island[500000]; 13 int siz; 14 int n,m; 15 int bin[6000000]; 16 int top; 17 char cmd[100]; 18 void pushup(int spc) 19 { 20 if(!spc) 21 return ; 22 tr[spc].wgt=tr[tr[spc].ls].wgt+tr[tr[spc].rs].wgt; 23 return ; 24 } 25 int finf(int x) 26 { 27 return x==fa[x]?x:fa[x]=finf(fa[x]); 28 } 29 int new_p(void) 30 { 31 int ans; 32 if(top) 33 ans=bin[top--]; 34 ans=++siz; 35 tr[ans]=str; 36 return ans; 37 } 38 void del(int &spc) 39 { 40 bin[++top]=spc; 41 spc=0; 42 return ; 43 } 44 void build(int &spc,int l,int r,int pos) 45 { 46 if(!spc) 47 spc=new_p(); 48 tr[spc].wgt++; 49 if(l==r) 50 return ; 51 int mid=(l+r)>>1; 52 if(pos<=mid) 53 build(tr[spc].ls,l,mid,pos); 54 else 55 build(tr[spc].rs,mid+1,r,pos); 56 return ; 57 } 58 int merge(int spc1,int spc2,int l,int r) 59 { 60 if(!spc1||!spc2) 61 return spc1+spc2; 62 int spc=new_p(); 63 if(l==r) 64 { 65 tr[spc].wgt=tr[spc1].wgt+tr[spc2].wgt; 66 return spc; 67 } 68 int mid=(l+r)>>1; 69 tr[spc].ls=merge(tr[spc1].ls,tr[spc2].ls,l,mid); 70 tr[spc].rs=merge(tr[spc1].rs,tr[spc2].rs,mid+1,r); 71 pushup(spc); 72 del(spc1); 73 del(spc2); 74 return spc; 75 } 76 int kth(int l,int r,int k,int spc) 77 { 78 if(l==r) 79 return l; 80 int mid=(l+r)>>1; 81 if(tr[spc].wgt<k) 82 return -1; 83 if(tr[tr[spc].ls].wgt>=k) 84 return kth(l,mid,k,tr[spc].ls); 85 else 86 return kth(mid+1,r,k-tr[tr[spc].ls].wgt,tr[spc].rs); 87 } 88 int main() 89 { 90 scanf("%d%d",&n,&m); 91 for(int i=1;i<=n;i++) 92 { 93 scanf("%d",&imp[i]); 94 fa[i]=i; 95 build(root[i],1,n,imp[i]); 96 island[imp[i]]=i; 97 } 98 for(int i=1;i<=m;i++) 99 { 100 int a,b; 101 scanf("%d%d",&a,&b); 102 int fx=finf(a); 103 int fy=finf(b); 104 if(a!=b) 105 { 106 fa[fx]=fy; 107 root[fy]=merge(root[fx],root[fy],1,n); 108 } 109 } 110 int q; 111 scanf("%d",&q); 112 while(q--) 113 { 114 scanf("%s",cmd+1); 115 int x,y; 116 scanf("%d%d",&x,&y); 117 if(cmd[1]==‘B‘) 118 { 119 int fx=finf(x); 120 int fy=finf(y); 121 if(fy!=fx) 122 { 123 fa[fx]=fy; 124 root[fy]=merge(root[fx],root[fy],1,n); 125 } 126 }else{ 127 int f=finf(x); 128 int no=kth(1,n,y,root[f]); 129 if(no==-1) 130 printf("%d\n",-1); 131 else 132 printf("%d\n",island[no]); 133 } 134 } 135 return 0; 136 }
BZOJ2733: [HNOI2012]永无乡（线段树合并）
原文：https://www.cnblogs.com/blog-Dr-J/p/9726340.html