[HNOI2012]永无乡

思路：
对于每一个点，建立一棵权值线段树，然后用并查集维护图的连通性，同时合并线段树维护每个连通块的权值。
由于一些奇怪的原因，这道题代码从头到尾总共打了3遍。
交到洛谷上发现是MLE，原因是数组开小了。
然后交到别的OJ上，发现在BZOJ是RE，在CodeVS上是TLE。
然后加了读优两边都AC了。

  1 #include<cstdio>
  2 #include<cctype>
  3 inline int getint() {
  4     char ch;
  5     while(!isdigit(ch=getchar()));
  6     int x=ch^'0';
  7     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
  8     return x;
  9 }
 10 const int N=100001,logN=18;
 11 class DisjointSet {
 12     private:
 13         int anc[N];
 14     public:
 15         DisjointSet() {
 16             for(int i=0;i<N;i++) anc[i]=i;
 17         }
 18         int Find(const int x) {
 19             return x==anc[x]?x:anc[x]=Find(anc[x]);
 20         }
 21         void Union(const int x,const int y) {
 22             anc[Find(x)]=Find(y);
 23         }
 24         bool isConnected (const int x,const int y) {
 25             return Find(x)==Find(y);
 26         }
 27 };
 28 DisjointSet s;
 29 class SegmentTree {
 30     private:
 31         static const int nil=0;
 32         int val[N*logN],left[N*logN],right[N*logN];
 33         int sz;
 34         int newnode() {
 35             return ++sz;
 36         }
 37         void push_up(const int p) {
 38             val[p]=val[left[p]]+val[right[p]];
 39         }
 40     public:
 41         SegmentTree() {
 42             val[nil]=0;
 43             sz=0;
 44         }
 45         int id[N],root[N];
 46         void insert(int &p,const int b,const int e,const int x) {
 47             p=newnode();
 48             if(b==e) {
 49                 left[p]=right[p]=nil;
 50                 val[p]=1;
 51                 return;
 52             }
 53             int mid=(b+e)>>1;
 54             left[p]=right[p]=nil;
 55             if(x<=mid) insert(left[p],b,mid,x);
 56             if(x>mid) insert(right[p],mid+1,e,x);
 57             push_up(p);
 58         }
 59         int merge(int p1,int p2) {
 60             if(!p1||!p2) return p1|p2;
 61             val[p1]+=val[p2];
 62             left[p1]=merge(left[p1],left[p2]);
 63             right[p1]=merge(right[p1],right[p2]);
 64             return p1;
 65         }
 66         int query(const int p,const int b,const int e,const int k) {
 67             if(val[p]<k) return -1;
 68             if(b==e) return id[b];
 69             int mid=(b+e)>>1;
 70             if(val[left[p]]>=k) {
 71                 return query(left[p],b,mid,k);
 72             }
 73             else {
 74                 return query(right[p],mid+1,e,k-val[left[p]]);
 75             }
 76         }
 77 };
 78 SegmentTree t;
 79 int main() {
 80     int n=getint(),m=getint();
 81     for(int i=1;i<=n;i++) {
 82         int x=getint();
 83         t.insert(t.root[i],1,n,x);
 84         t.id[x]=i;
 85     }
 86     while(m--) {
 87         int u=getint(),v=getint();
 88         if(s.isConnected(u,v)) continue;
 89         t.root[s.Find(v)]=t.merge(t.root[s.Find(v)],t.root[s.Find(u)]);
 90         s.Union(u,v);
 91     }
 92     for(int q=getint();q;q--) {
 93         char op[2];
 94         scanf("%s",op);
 95         if(op[0]=='Q') {
 96             int x=getint(),k=getint();
 97             printf("%d
",t.query(t.root[s.Find(x)],1,n,k));
 98         }
 99         if(op[0]=='B') {
100             int u=getint(),v=getint();
101             if(s.isConnected(u,v)) continue;
102             t.root[s.Find(v)]=t.merge(t.root[s.Find(v)],t.root[s.Find(u)]);
103             s.Union(u,v);
104         }
105     }
106     return 0;
107 }