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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2049】【SDOI2008】【洞穴勘测】  

2014-03-04 17:46:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     裸的入门link-cut-tree。
     但是这题就是名副其实的动态树了,而且是”会动的动态树“(百度),不像之前几道题只是树的一些信息改变,这里是树的形态全都发生改变了....
     所以还是得老老实实写。
     一直在纠结不能用提根的操作,因为咱们不能找到根自顶向下传递翻转标记(如果额外记录信息不太美观),一个节点的翻转标记只用于它的子树,而它的翻转标记可以与它的子树叠加,对于一个子树,它所受到的翻转的影响实际上就只是其根节点往上走的祖先中翻转标记的个数。我们一开始只拥有一个节点x,我们使用了父亲的翻转节点之后,那么它连同它的父亲的子树的形态就固定了(就是只有这么一堆东西了),对于这一个子树,往上走碰到的那些标记只需要打到该子树的根x上即可。所以我们每一次往上走,首先影响当前子树的是x的父亲节点的标记,但是为了合并x这棵子树和父亲及其兄弟子树,我们还需要父亲的父亲的翻转标记的关系,也就是说,我们不需要自顶向下的传递标记,只需要从下面开始,每一次旋转之后找父亲和父亲的父亲,先把父亲的父亲的标记下放,再把父亲的标记下放,再把X的标记下放,最后两步实现了X与其父亲的合并,第一步是固定了它们的形态。这样子就好写许多。
    然后就是判两个点在同一分量里面,这个两个都access一次,然后找最左边的元素,判相等即可。
========================================

program bzoj2049;
const maxn=10010;
type
  node=record
  son:array[0..1]of longint;
  f:longint;
  flip:boolean;
  end;

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

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

procedure swap(var a,b:longint);
var t:longint;
begin
  t:=a;a:=b;b:=t;
end;

procedure release(p:longint);
begin
  with t[p] do
   if flip then
    begin
      t[son[0]].flip:=not t[son[0]].flip;
      t[son[1]].flip:=not t[son[1]].flip;
      swap(t[son[0]].son[0],t[son[0]].son[1]);
      swap(t[son[1]].son[0],t[son[1]].son[1]);
      flip:=not flip;
    end;
end;

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

procedure splay(p:longint);
begin
  release(p);
  while not root[p] do
   if root[t[p].f] then
    begin
      release(t[p].f);
      release(p); {这里注意每一次都要把父亲下放一次,然后自己再下放一次,维护子树合法}
      rotate(p);
    end
   else begin
     release(t[t[p].f].f);
     release(t[p].f);
     release(p);
     if wh(p) xor wh(t[p].f)=0 then rotate(t[p].f)
                               else rotate(p);
     rotate(p);end;
end;

procedure access(p:longint);
var y:longint;
begin
  splay(p);
  root[t[p].son[1]]:=true;
  t[p].son[1]:=0;
  while t[p].f<>0 do
   begin
     y:=t[p].f;
     splay(y);
     root[t[y].son[1]]:=true;
     root[p]:=false;
     t[y].son[1]:=p;
     splay(p);
   end;
end;

procedure init;
var i,u,v,tt,j,k:longint;
    ch:char;
begin
  readln(n,m);
  fillchar(root,sizeof(root),true);
  for i:=1 to n do
   begin
     t[i].f:=0;
     t[i].son[0]:=0;
     t[i].son[1]:=0;
     t[i].flip:=false;
   end;
  for i:=1 to m do
   begin
     read(ch);
     case ch of
     'Q':begin
           readln(ch,ch,ch,ch,u,v);
           access(u);
           j:=u;
           while t[j].son[0]<>0 do j:=t[j].son[0];
           access(v);
           k:=v;
           while t[k].son[0]<>0 do k:=t[k].son[0];
           if j=k then writeln('Yes')
                  else writeln('No');
         end;
     'C':begin
           readln(ch,ch,ch,ch,ch,ch,u,v);
           access(u);
           t[u].flip:=not t[u].flip;
           swap(t[u].son[0],t[u].son[1]);
           access(v);
           t[u].f:=v;
         end;
     'D':begin
           readln(ch,ch,ch,ch,ch,ch,u,v);
           access(u);
           t[u].flip:=not t[u].flip;
           swap(t[u].son[0],t[u].son[1]);
           access(v);
           root[u]:=true;
           t[u].f:=t[v].f;
           t[v].son[0]:=0;
         end;
     end;
   end;
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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