[BZOJ2733] 永無鄉 線段樹合并

Description

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

Input

輸入檔案第一行是用空格隔開的兩個正整數

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 

題解

Output

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

線段樹合并模闆題。

對每個島先建一顆權值線段樹（隻有logn長度的一條鍊），樹上節點維護權值為[l,r]的島的個數。

對于要建橋但不聯通的島要合并權值線段樹。

合并操作：

x y代表要合并的兩棵樹的節點，若x*y==0，則x或y或x&y不存在，即子樹不需要合并權值，不需改動，直接将父節點指向該節點；

否則将y的權值加到x上，還用root[x]這棵樹，可以減少空間複雜度，然後遞歸merge()。siz[x]+=siz[y];  等效 siz[x]=siz[lc[x]]+siz[rc[x]];  分别為直接合并、由子樹更新（子樹可能僅改了指向）

查找kth：

同平衡樹，在權值線段樹上二分即可，如果k<=siz[lc[rt]]，說明kth在左子樹，反之kth在右子樹且在右子樹的排名為k-siz[lc[rt]]　　(這不同于平衡樹因為線段樹的節點含義不同)

用并查集維護聯通關系即是否已合并權值線段樹。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define reg register
#define F(i,a,b) for(i=a;i<=b;++i)
using namespace std;
int lc[2000005],rc[2000005],rk[100005],fa[100005],siz[2000005],rt[100005],o;
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void insert(int &root,int l,int r,int w)
{
    root=++o;
    siz[root]=1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(w<=mid) insert(lc[root],l,mid,w);
    else insert(rc[root],mid+1,r,w);
    siz[root]=siz[lc[root]]+siz[rc[root]];
}
int merge(int x,int y)
{
    if(x*y==0) return x+y;                //該子樹xy不重疊，不用更改，隻改指向 
    siz[x]+=siz[y];                        //權值合并到x 
    lc[x]=merge(lc[x],lc[y]);
    rc[x]=merge(rc[x],rc[y]);
    siz[x]=siz[lc[x]]+siz[rc[x]];
    return x;
}
int ask(int rt,int l,int r,int k)
{
    if(l==r) return rk[l];
    int mid=(l+r)>>1;
    if(k<=siz[lc[rt]]) return ask(lc[rt],l,mid,k);
    else return ask(rc[rt],mid+1,r,k-siz[lc[rt]]);
}
void merge2(int x,int y)
{
    int a,b;
    a=find(x); b=find(y);
    if(a!=b) fa[b]=a,rt[a]=merge(rt[a],rt[b]);            //不能換，x為合并後根 
}
int main()
{
    int n,m,q;
    scanf("%d%d",&n,&m);
    reg int i,t,a,b;
    F(i,1,n)
        scanf("%d",&t),rk[t]=i,fa[i]=i,insert(rt[i],1,n,t);
    F(i,1,m)
        scanf("%d%d",&a,&b),merge2(a,b);
    scanf("%d",&q);
    reg char s[5];
    while(q--)
    {
        scanf("%s",s);
        scanf("%d %d",&a,&b);
        if(s[0]=='B') merge2(a,b);
        else printf("%d\n",siz[rt[find(a)]]<b?-1:ask(rt[find(a)],1,n,b));
    }
    return 0;
}