解题：HNOI 2012 永无乡

并查集维护连通性，然后暴力启发式合并就完了，记得合并时边DFS边清空数组
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=100005;
  6 int val[N],siz[N],rnk[N],son[N][2];
  7 int aset[N],volu[N],root[N];
  8 int n,m,x,y,t1,t2,tot;
  9 char rd[5];
 10 int finda(int x)
 11 {
 12     return x==aset[x]?x:aset[x]=finda(aset[x]);
 13 }
 14 void Pushup(int nde)
 15 {
 16     siz[nde]=siz[son[nde][0]]+siz[son[nde][1]]+1;
 17 }
 18 int Create()
 19 {
 20     siz[++tot]=1;
 21     rnk[tot]=rand();
 22     return tot;
 23 }
 24 int Merge(int x,int y)
 25 {
 26     if(!x||!y)
 27         return x+y;
 28     else if(rnk[x]<=rnk[y])
 29     {
 30         son[x][1]=Merge(son[x][1],y);
 31         Pushup(x); return x;
 32     }
 33     else
 34     {
 35         son[y][0]=Merge(x,son[y][0]);
 36         Pushup(y); return y;
 37     }
 38 }
 39 void Split(int nde,int &x,int &y,int tsk)
 40 {
 41     if(!nde) x=y=0;
 42     else
 43     {
 44         if(val[nde]<=tsk)
 45             x=nde,Split(son[nde][1],son[nde][1],y,tsk);
 46         else 
 47             y=nde,Split(son[nde][0],x,son[nde][0],tsk);
 48         Pushup(nde);
 49     }
 50 }
 51 int Query(int nde,int tsk)
 52 {
 53     if(tsk<=siz[son[nde][0]]) return Query(son[nde][0],tsk);
 54     else if(tsk==siz[son[nde][0]]+1) return nde;
 55     else return Query(son[nde][1],tsk-siz[son[nde][0]]-1);
 56 }
 57 void Insert(int &nde,int tsk)
 58 {
 59     Split(nde,x,y,val[tsk]);
 60     nde=Merge(Merge(x,tsk),y);
 61 }
 62 void DFS(int &gal,int nde)
 63 {
 64     if(son[nde][0]) DFS(gal,son[nde][0]);
 65     if(son[nde][1]) DFS(gal,son[nde][1]);
 66     son[nde][0]=son[nde][1]=0; Insert(gal,nde);
 67 }
 68 void Unite(int x,int y)
 69 {
 70     int f1=finda(x),f2=finda(y);
 71     if(volu[f1]<volu[f2]) swap(f1,f2);
 72     volu[f1]+=volu[f2],aset[f2]=f1;
 73     DFS(root[f1],root[f2]);
 74 }
 75 int main ()
 76 {
 77     srand(20020513);
 78     scanf("%d%d",&n,&m);
 79     for(int i=1;i<=n;i++)
 80     {
 81         scanf("%d",&val[i]);
 82         root[i]=Create();
 83         aset[i]=i,volu[i]=1;
 84     }
 85     while(m--)
 86         scanf("%d%d",&t1,&t2),Unite(t1,t2);
 87     scanf("%d",&m);
 88     while(m--)
 89     {
 90         scanf("%s%d%d",rd,&t1,&t2);
 91         if(rd[0]=='B') 
 92             scanf("%d%d",&t1,&t2),Unite(t1,t2);
 93         else
 94         {
 95             int ans=Query(root[finda(t1)],t2);
 96             ans?printf("%d
",ans):printf("-1
");
 97         }
 98     }
 99     return 0;
100 }
View Code