注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2733】【Hnoi2012】【永无乡】  

2014-04-18 20:06:26|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:维护n个集合,初始时候每个集合有一个数,保证互不相同,有以下操作:
    1)合并两个集合。
    2)询问某集合内部的第K大。
    0.0平衡树可以做第二个,关于第一个合并...可以直接启发式合并,也就是说,如果要合并两个平衡树u,v,先把u,v旋到根得到整棵树的size(有一个size域表示该平衡树的节点个数),然后咱们将size小的平衡树的所有节点插入到size大的平衡树内部,可以证明这样子的总的复杂度就是O(nlog^2 n)

    咱们可以来证明一下这个结论,咱们考虑某一个节点所在的树,由于咱们是启发式合并,所以这棵树如果被合并了,那么显然这棵树的size会变成原来的两倍以上(小的插入大的),而一棵树的size每次都被合并的话可以变成2倍,那么由于size最大只有n,所以一个节点只能被插入到其他平衡树logn次,然后每一次插入都是O(logn)的,所以总的合并的复杂度就是O(n^2logn)

    由于这道题并没有添加新的节点,也没有删除操作,咱们可以类似link-cut-tree一样的,用一个bool数组表示每一个点是否为根,然后就不需要记住每一棵平衡树的根了。非常方便,写的也很愉快0v0...
    然后不知道是数据的问题还是什么...数据里面有 合并编号0的点(没有询问0的点),编号0的点在原题目是不存在的,所以咱们可以跳过这个合并(如果不跳过就会去splay这个0号节点..)。因为这个问题RE一次。
==================================

program bzoj2733;
type node=record
     son:array[0..1]of longint;
     f,size:longint;
     a:int64;
     end;

var t:array[0..100010]of node;
    root:array[0..100010]of boolean;
    n,q,m:longint;

function wh(p:longint):longint;
begin
  if t[t[p].f].son[1]=p then exit(1)
  else exit(0);
end;

procedure rotate(p:longint);
var y,w:longint;
begin
  with t[p] do
   begin
     y:=f;w:=wh(p);
     f:=t[y].f;
     t[t[y].f].son[wh(y)]:=p;
     t[son[w xor 1]].f:=y;
     t[y].son[w]:=son[w xor 1];
     son[w xor 1]:=y;
     t[y].f:=p;
     root[p]:=root[p] xor root[y];
     root[y]:=root[p] xor root[y];
     t[y].size:=t[t[y].son[0]].size+t[t[y].son[1]].size+1;
     size:=t[son[0]].size+t[son[1]].size+1;
   end;
end;

procedure splay(p:longint);
begin
  while not root[p] do
   if root[t[p].f] then rotate(p)
   else begin
     if wh(p) xor wh(t[p].f)=0 then rotate(t[p].f)
                               else rotate(p);
     rotate(p);
   end;
end;

function find(p:longint;aim:longint):longint;
begin
  splay(p);
  while p<>0 do
   begin
     if t[t[p].son[0]].size+1=aim then exit(p);
     if t[t[p].son[0]].size+1>aim then p:=t[p].son[0]
     else begin
       dec(aim,t[t[p].son[0]].size+1);
       p:=t[p].son[1];
     end;
   end;
  exit(-1);
end;

procedure insert(p,c:longint);
begin
  root[c]:=false;
  while t[p].son[ord(t[p].a<t[c].a)]<>0 do
    p:=t[p].son[ord(t[p].a<t[c].a)];
  t[p].son[ord(t[p].a<t[c].a)]:=c;
  t[c].f:=p;
  t[c].son[1]:=0;
  t[c].son[0]:=0;
  t[c].size:=1;
  splay(c);
end;

function same(u,v:longint):boolean;
var p,q:longint;
begin
  p:=u;
  splay(u);
  while t[p].son[0]<>0 do
   p:=t[p].son[0];
  q:=v;
  splay(v);
  while t[q].son[0]<>0 do
   q:=t[q].son[0];
  splay(q);
  if p=q then exit(true)
         else exit(false);
end;

procedure dfs(v:longint;var u:longint);
var l,r:longint;
begin
  l:=t[v].son[0];r:=t[v].son[1];
  insert(u,v);
  u:=v;
  if l<>0 then dfs(l,u);
  if r<>0 then dfs(r,u);
end;

procedure stop;
begin
end;

procedure init;
var i,u,v:longint;
    ch:char;
begin
  read(n,m);
  for i:=1 to n do
   begin
     read(t[i].a);
     t[i].f:=0;
     t[i].son[0]:=0;
     t[i].son[1]:=0;
     t[i].size:=1;
     root[i]:=true;
   end;
  for i:=1 to m do
   begin
     read(u,v);
     if (u=0)or(v=0) then continue;
     if not same(u,v) then
      begin
        splay(u);
        splay(v);
        if t[u].size<t[v].size then
         dfs(u,v)
        else
         dfs(v,u);
      end;
   end;
  readln(q);
  for i:=1 to q do
   begin
     read(ch);
     case ch of
      'Q':begin
            readln(u,v);
            if (u=0)or(v=0)then continue;
            writeln(find(u,v));
          end;
      'B':begin
            readln(u,v);
            if (u=0)or(v=0)then continue;
            if u=v then continue;
            if not same(u,v) then
             begin
               splay(u);
               splay(v);
               if t[u].size<t[v].size then
                dfs(u,v)
               else
                dfs(v,u);
             end;
          end;
      end;
   end;
end;

begin
  init;
end.


  评论这张
 
阅读(30)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017