洛谷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。

輸入輸出樣例

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 }