加载中…
个人资料
winedia
winedia
  • 博客等级:
  • 博客积分:0
  • 博客访问:83,077
  • 关注人气:31
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

bzoj 2733 - 永无乡 splay+启发式合并

(2013-05-09 13:26:36)
标签:

bzoj

杂谈

分类: bzoj
一道非常裸的启发式合并splay。
SX一试讲课的时候讲到启发式合并神马的就自动无视了,结果发现原来启发式合并还是很好理解的一个东西,就是把小的往大的合并。
启发式合并嘛,最常见的是并查集的启发式合并,HDU3771那道,就是做的时候把小的联通块向大的合并。
链表的启发式合并在HNOI2009的梦幻布丁,也是非常优美的,能把nm的降到mlogn。
永无乡这道就是splay的启发式合并,判断两颗树大小之后就开始暴力合并了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 120020
int f[N],rank[N],size[N],q[N],c[N][2],fa[N];
int head,tail,n,m;
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
inline void update(int x){
   if (!x) return;
   size[x] = size[c[x][0]] + size[c[x][1]] + 1;
}
inline void rotate(int x){
   int y = fa[x],z = fa[y];
   int p = (x == c[y][1]),q = p ^ 1;
   if (fa[y])
       if (c[z][0] == y) c[z][0] = x;
       else c[z][1] = x;
   fa[x] = z;fa[y] = x;fa[c[x][q]] = y;
   c[y][p] = c[x][q];c[x][q] = y;
   update(y);
}
void splay(int x){
   while (fa[x]){
       int y = fa[x],z = fa[y];
       if (fa[y])
           if ((x == c[y][0]) ^ (y == c[z][0])) rotate(x);
           else rotate(y);
       rotate(x);
   }
   update(x);
}
void insert(int &t,int anc,int now){
   if (t == 0){
       t = now;
       fa[t] = anc;
       size[t] = 1;
       splay(t);
       return;
   }
   if (rank[now] <= rank[t]) insert(c[t][0],t,now);
   else insert(c[t][1],t,now);
   update(t);
}
void merge(int x,int y){
   splay(x);splay(y);
   if (size[x] > size[y]) swap(x,y);
   int head = 0,tail = 1;
   q[0] = y;q[1] = x;
   while (head < tail){
       int x = q[++ head];
       if (c[x][0]) q[++ tail] = c[x][0];
       if (c[x][1]) q[++ tail] = c[x][1];
       c[x][0] = c[x][1] = 0;
       insert(q[head - 1],0,x);
   }
}
int search(int x,int y){
   if (y > size[x]) return -1;
   if (y == size[c[x][0]] + 1) return x;
   if (y < size[c[x][0]] + 1) return search(c[x][0],y);
   return search(c[x][1],y - size[c[x][0]] - 1);
}
int main(){
   int x,y;
   scanf("%d%d",&n,&m);
   for (int i = 1;i <= n;i ++) scanf("%d",&rank[i]),f[i] = i,size[i] = 1;
   for (int i = 1;i <= m;i ++){
       scanf("%d%d",&x,&y);
       if (find(x) != find(y)) {
           merge(x,y);
           f[f[x]] = f[y];
       }
   }
   int Q;
   char ctrl[5];
   scanf("%d",&Q);
   while (Q --){
       scanf("%s%d%d",ctrl,&x,&y);
       if (ctrl[0] == 'B'){
           if (find(x) != find(y)){
               merge(x,y);
               f[f[x]] = f[y];
           }
       }else{
           splay(x);
           printf("%d\n",search(x,y));
       }
   }
   return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有