Description

永無鄉(xiāng)包含 n 座島，編號從 1 到 n，每座島都有自己的獨一無二的重要度，按照重要度可 以將這 n 座島排名，名次用 1 到 n 來表示。某些島之間由巨大的橋連接，通過橋可以從一個島 到達另一個島。如果從島 a 出發(fā)經(jīng)過若干座（含 0 座）橋可以到達島 b，則稱島 a 和島 b 是連 通的。現(xiàn)在有兩種操作：B x y 表示在島 x 與島 y 之間修建一座新橋。Q x k 表示詢問當前與島 x連通的所有島中第 k 重要的是哪座島，即所有與島 x 連通的島中重要度排名第 k 小的島是哪 座，請你輸出那個島的編號。  

Input

輸入文件第一行是用空格隔開的兩個正整數(shù) n 和 m，分別 表示島的個數(shù)以及一開始存在的橋數(shù)。接下來的一行是用空格隔開的 n 個數(shù)，依次描述從島 1 到島 n 的重要度排名。隨后的 m 行每行是用空格隔開的兩個正整數(shù) ai 和 bi，表示一開始就存 在一座連接島 ai 和島 bi 的橋。后面剩下的部分描述操作，該部分的第一行是一個正整數(shù) q， 表示一共有 q 個操作，接下來的 q 行依次描述每個操作，操作的格式如上所述，以大寫字母 Q 或B 開始，后面跟兩個不超過 n 的正整數(shù)，字母與數(shù)字以及兩個數(shù)字之間用空格隔開。 對于 20%的數(shù)據(jù) n≤1000,q≤1000  對于 100%的數(shù)據(jù) n≤100000,m≤n，q≤300000  

Output

對于每個 Q x k 操作都要依次輸出一行，其中包含一個整數(shù)，表 示所詢問島嶼的編號。如果該島嶼不存在，則輸出-1。  

Sample Input

Sample Output

正解：線段樹啟發(fā)式合并。

以前沒用過啟發(fā)式合并，這回學了一下來用。。

和主席樹很像，動態(tài)開結點，值域線段樹。每次合并時直接將兩顆線段樹的每個結點合并。復雜度。。均攤是log^2嗎？？（其實我也不知道的說，不過學長說復雜度是對的。。）再用一個并查集維護連通性，于是這題就能完美AC了。然而HNOI居然會有水題。。

ps：啟發(fā)式合并復雜度證明，來自巨犇黃嘉泰（并沒有很看懂。。）

線段樹合并的時間復雜度證明

每一次合并的時間復雜度為 公共點個數(shù)

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define N (100010)#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;int sum[20*N],ls[20*N],rs[20*N],rt[N],fa[N],a[N],pos[N],n,m,sz;char s[5];il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int find(RG int x){ return fa[x]==x ? fa[x] : (fa[x]=find(fa[x])); }il void insert(RG int &x,RG int l,RG int r,RG int v){    if (!x) x=++sz; if (l==r){ sum[x]++; return; }    RG int mid=(l+r)>>1;    if (v<=mid) insert(ls[x],l,mid,v);    else insert(rs[x],mid+1,r,v);    sum[x]=sum[ls[x]]+sum[rs[x]]; return;}il int merge(RG int x,RG int y){    if (!x || !y) return x+y;    ls[y]=merge(ls[x],ls[y]);    rs[y]=merge(rs[x],rs[y]);    sum[y]=sum[ls[y]]+sum[rs[y]]; return y;}il int query(RG int x,RG int l,RG int r,RG int k){    if (l==r) return l; RG int mid=(l+r)>>1;    if (k<=sum[ls[x]]) return query(ls[x],l,mid,k);    else return query(rs[x],mid+1,r,k-sum[ls[x]]);}il void work(){    n=gi(),m=gi(); RG int u,v,x,k;    for (RG int i=1;i<=n;++i) a[i]=gi(),pos[a[i]]=i,fa[i]=i;    for (RG int i=1;i<=m;++i) u=gi(),v=gi(),u=find(u),v=find(v),fa[u]=v;    for (RG int i=1;i<=n;++i) insert(rt[find(i)],1,n,a[i]); m=gi();    for (RG int i=1;i<=m;++i){	scanf("%s",s);	if (s[0]=='B'){	    u=gi(),v=gi(),u=find(u),v=find(v);	    if (u!=v) fa[u]=v,rt[v]=merge(rt[u],rt[v]);	}	if (s[0]=='Q'){	    x=gi(),k=gi(),x=find(x);	    if (sum[rt[x]]<k){ PRintf("-1/n"); continue; }	    printf("%d/n",pos[query(rt[x],1,n,k)]);	}    }    return;}int main(){    File("neverland");    work();    return 0;}