題目描述 永無鄉包含 n 座島，編號從 1 到 n，每座島都有自己的獨一無二的重要度，按照重要度可 以將這 n 座島排名，名次用 1 到 n 來表示。某些島之間由巨大的橋連接，通過橋可以從一個島 到達另一個島。如果從島 a 出發經過若幹座（含 0 座）橋可以到達島 b，則稱島 a 和島 b 是連 通 ...
題目描述
永無鄉包含 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
對於聯通性問題，我們可以用並查集維護
對於動態集合第k大，我們可以用平衡樹維護
這樣的話維護n個splay
然後每次暴力合併就好
註意要用啟髮式合併
只有這樣插入點的複雜度才是嚴格$O(logn)$
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int MAXN=1e6+10; 5 const int maxn=0x7fffff; 6 #define ls tree[k].ch[0] 7 #define rs tree[k].ch[1] 8 inline int read() 9 { 10 char c=getchar();int x=0,f=1; 11 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 12 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 13 return x*f; 14 } 15 struct node 16 { 17 int v,fa,ch[2],sum; 18 }tree[MAXN]; 19 int pointnum,tot; 20 int root[MAXN],val[MAXN],f[MAXN],n,m; 21 char opt[10]; 22 int iden(int x){return tree[tree[x].fa].ch[0]==x?0:1;} 23 inline void connect(int x,int fa,int how){tree[x].fa=fa;tree[fa].ch[how]=x;} 24 inline void update(int x) 25 {tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+1;} 26 inline void rotate(int x) 27 { 28 int y=tree[x].fa; 29 int R=tree[y].fa; 30 int Rson=iden(y); 31 int yson=iden(x); 32 int b=tree[x].ch[yson^1]; 33 connect(b,y,yson); 34 connect(y,x,yson^1); 35 connect(x,R,Rson); 36 update(y);update(x); 37 } 38 void splay(int x,int to)// 把編號為pos的節點旋轉到編號為to的節點 39 { 40 while(tree[x].fa!=to) 41 { 42 int y=tree[x].fa,z=tree[y].fa; 43 if(z!=to) 44 (tree[z].ch[0]==y)^(tree[y].ch[0]==x)?rotate(x):rotate(y); 45 rotate(x); 46 } 47 if(to<=n) root[to]=x; 48 } 49 void insert(int v,int pos) 50 { 51 int now=root[pos],fa=pos; 52 while(now&&tree[now].v!=v) 53 fa=now,now=tree[now].ch[v>tree[now].v]; 54 now=++tot; 55 tree[now].sum=1; 56 tree[now].fa=fa; 57 if(fa>n) tree[fa].ch[v>tree[fa].v]=now; 58 tree[now].v=v;tree[now].ch[0]=tree[now].ch[1]=0; 59 splay(now,pos); 60 } 61 int rank(int pos,int k) 62 { 63 int now=root[pos]; 64 if(tree[now].sum<k) return -1; 65 while(1) 66 { 67 if(tree[tree[now].ch[0]].sum+1<k) k-=tree[tree[now].ch[0]].sum+1,now=tree[now].ch[1]; 68 else if(tree[tree[now].ch[0]].sum>=k) now=tree[now].ch[0]; 69 else return tree[now].v; 70 } 71 splay(now,root[pos]); 72 return tree[now].v; 73 } 74 int Gets(int x) 75 { 76 if(f[x]==x) return f[x]; 77 else return f[x]=Gets(f[x]); 78 } 79 void DFS(int k,int fa) 80 { 81 if(ls) DFS(ls,fa); 82 if(rs) DFS(rs,fa); 83 insert(tree[k].v,fa); 84 } 85 void Merge(int x,int y) 86 { 87 x=Gets(x),y=Gets(y); 88 if(x==y) return ; 89 if(tree[root[x]].sum>tree[root[y]].sum) swap(x,y); 90 f[x]=y; 91 DFS(root[x],y); 92 } 93 int main() 94 { 95 #ifdef WIN32 96 freopen("a.in","r",stdin); 97 #else 98 #endif 99 n=read(),m=read(); 100 tot=n*2; 101 for(int i=1;i<=n;i++) 102 { 103 int p=read(); 104 val[p]=i; 105 tree[i+n].v=p; 106 tree[i+n].sum=1; 107 tree[i+n].fa=i; 108 root[i]=i+n; 109 f[i]=i; 110 } 111 for(int i=1;i<=m;i++) 112 { 113 int x=read(),y=read(); 114 Merge(x,y); 115 } 116 int q=read(); 117 while(q--) 118 { 119 int x,y; 120 scanf("%s",opt); 121 x=read();y=read(); 122 if(opt[0]=='B') 123 Merge(x,y); 124 else 125 { 126 int ans=rank(Gets(x),y); 127 printf("%d\n",ans==-1?ans:val[ans]); 128 } 129 } 130 }
