P3224 [HNOI2012]永无乡

题目描述

永无乡包含 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： 5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3 输出样例#1： -1 2 5 1 2 这道题用启发式合并,用线段树写的 对于每个连通分量我们维护一棵线段树，每次查询在线段数里面二分，对于加边，若两个点连通分量不同，则连边且合并两棵线段树 #include<iostream> #include<cstdio> using namespace std; #define mxn 100005 #define siz 2000005 int ls[siz],rs[siz],sm[siz],tt,fa[mxn],rt[mxn],sz[mxn],vl[mxn]; int n,m; void ins(int &t,int l,int r,int v){ t=++tt;int mid=(l+r)>>1;sm[t]=1; if(l==r)return; if(v<=mid)ins(ls[t],l,mid,v); if(v>mid)ins(rs[t],mid+1,r,v); } int find(int x){ if(fa[x]==x)return fa[x]; else return fa[x]=find(fa[x]); } void mer(int &a,int b){ if(!a){a=b;return;} sm[a]+=sm[b]; if(ls[b])mer(ls[a],ls[b]); if(rs[b])mer(rs[a],rs[b]); } void merge(int x,int y){ x=find(x),y=find(y); mer(rt[x],rt[y]),fa[y]=x,sz[x]+=sz[y]; } int RANK(int t,int l,int r,int k){ if(l==r)return l; int mid=(l+r)>>1,s=sm[ls[t]]; if(k<=s)return RANK(ls[t],l,mid,k); else return RANK(rs[t],mid+1,r,k-s); } char s[5]; int main(){ //freopen("yongwuxiang.txt","r",stdin); scanf("%d%d",&n,&m);int x,y,q; for(int i=1;i<=n;i++)scanf("%d",&x),fa[i]=vl[x]=i,sz[i]=1,ins(rt[i],1,n,x); for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),merge(x,y); scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%s%d%d",s,&x,&y); if(s[0]=='B'){ merge(x,y); } if(s[0]=='Q'){ int father=find(x); if(sz[father]<y)printf("-1\n"); else printf("%d\n",vl[RANK(rt[father],1,n,y)]); } } }