bzoj2733 [HNOI2012]永无乡

题目描述

永无乡包含 n 座岛，编号从 1 到 n ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛aa 出发经过若干座（含 0 座）桥可以 到达岛 b ，则称岛 a 和岛 b 是连通的。

现在有两种操作：

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

输入输出格式

输入格式：

第一行是用空格隔开的两个正整数 \(n\) 和 \(m\) ，分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 \(n\) 个数，依次描述从岛 \(1\) 到岛 \(n\) 的重要度排名。随后的 \(m\) 行每行是用空格隔开的两个正整数\(a_i\)和\(b_i\) ，表示一开始就存在一座连接岛 \(a_i\)和岛\(b_i\)的桥。

后面剩下的部分描述操作，该部分的第一行是一个正整数 \(q\) ，表示一共有 \(q\) 个操作，接下来的 \(q\) 行依次描述每个操作，操作的 格式如上所述，以大写字母 \(Q\) 或 \(B\) 开始，后面跟两个不超过 \(n\) 的正整数，字母与数字以及两个数字之间用空格隔开。

输出格式：

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 \(-1\)。

输入输出样例

输入样例#1：

5  14  3 2 5 11  27Q 3 2Q 2 1B 2 3B 1 5Q 2 1Q 2 4Q 2 3

输出样例#1：

-12512

说明

对于 20% 的数据 \(n \leq 1000, q \leq 1000n≤1000,q≤1000\)

对于 100% 的数据 \(n \leq 100000, m \leq n, q \leq 300000 n≤100000,m≤n,q≤300000\)

题解：

首先，连通性可以用并查集维护

至于连接，暴力启发式合并就可以了

然后直接写splay

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define QAQ int#define TAT long long#define OwO bool#define ORZ double#define F(i,j,n) for(QAQ i=j;i<=n;++i)#define E(i,j,n) for(QAQ i=j;i>=n;--i)#define MES(i,j) memset(i,j,sizeof(i))#define MEC(i,j) memcpy(i,j,sizeof(j))using namespace std;const QAQ N=100005;QAQ n,m,rot,fa[N];struct data{ QAQ fa,son[2],val,size; data(){ fa=0;son[1]=son[0]=0;val=0;size=0; }}tree[N];queue
                
                  q;QAQ find(QAQ x){return fa[x]==x ? x : fa[x]=find(fa[x]);}void push_up(QAQ o){tree[o].size=tree[tree[o].son[1]].size+tree[tree[o].son[0]].size+1;}OwO get(QAQ o){return tree[tree[o].fa].son[1]==o;}void rotate(QAQ o){ QAQ fa=tree[o].fa,ff=tree[fa].fa; OwO pd=get(o); if(ff) tree[ff].son[get(fa)]=o; tree[o].fa=ff; tree[fa].son[pd]=tree[o].son[1-pd]; tree[tree[o].son[1-pd]].fa=fa; tree[fa].fa=o;tree[o].son[1-pd]=fa; push_up(fa);push_up(o);}void splay(QAQ o,QAQ goal){ while(tree[o].fa!=goal){ QAQ fa=tree[o].fa,ff=tree[fa].fa; if(ff!=goal) if(tree[fa].son[1]==o ^ tree[ff].son[1]==fa) rotate(o); else rotate(fa); rotate(o); } if(!goal) rot=o; push_up(o);}void Insert(QAQ x){ QAQ t=rot; while(1){ if(tree[x].val
                 
                  tree[o].size) return -1; QAQ t=rot; while(1){ if(tree[tree[t].son[0]].size>=x) t=tree[t].son[0]; else if(tree[tree[t].son[0]].size==x-1) return t; else x-=(tree[tree[t].son[0]].size+1),t=tree[t].son[1]; }}QAQ main(){ scanf("%d%d",&n,&m); F(i,1,n) scanf("%d",&tree[i].val),fa[i]=i; rot=0; F(i,1,m) { QAQ x,y; scanf("%d%d",&x,&y); x=find(x);y=find(y); if(x==y) continue; splay(x,0);splay(y,0); Merge(x,y); } scanf("%d",&m); while(m--){ char c; QAQ a,b; cin>>c;scanf("%d%d",&a,&b); if(c=='B'){ a=find(a);b=find(b); splay(a,0);splay(b,0); Merge(a,b); } else { a=find(a);splay(a,0); printf("%d\n",K_th(a,b)); } } return 0;}