终于会写动态树了

Posted on 2012-02-26 13:03 Mato_No1 阅读(1971) 评论(2)  编辑 收藏 引用 所属分类: 专题:数据结构动态模拟问题
【背景】
2012年1月19日,本沙茶开始看动态树论文,搞懂了一些;
2012年1月20日,开始写动态树,使用的题是QTREE,花了整整一天时间总算写完,交上去,TLE……
2012年1月21日,又调了一天,对拍了100+组随机数据都瞬间出解,交上去,还是TLE……
2012年2月8日,WC2012,fanhq666讲动态树,又搞懂了一点,于是当天晚上回房间以后就开始继续调,交上去,TLE……
2012年2月9日,晚上继续调QTREE,TLE……
在挑战动态树N次失败之后,本沙茶昨天再次去挑战动态树……这次换了一个题:BZOJ2002(传说中的动态树模板题)
一开始还是TLE了,不过后来把数据搞到手以后,发现TLE的原因并不是常数大,而是死循环了,最后,经过2h+的调试,总算找到了错误(有好几处),终于AC了……

【关于BZOJ2002】
从每个点i往(i+Ki)连一条边,如果(i+Ki)不存在则往一个附加的结点(本沙茶的代码中为1号点,因为0号点是不能使用的)连一条边,这样就是一棵树(除1号点外,每个点有且只有一个后继……),然后,问题中的两种操作就是“改接”和“询问到根的距离”,可以用动态树搞;

【代码】
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 200004, INF = ~0U >> 2;
struct node {
    
int c[2], p, sz;
    
bool rf, d;
} T[MAXN];
int n;
void sc(int _p, int _c, bool _d)
{
    T[_p].c[_d] 
= _c; T[_c].p = _p; T[_c].d = _d;
}
void upd(int No)
{
    T[No].sz 
= T[T[No].c[0]].sz + T[T[No].c[1]].sz + 1;
}
void rot(int No)
{
    
int p = T[No].p; bool d = T[No].d;
    
if (T[p].rf) {T[p].rf = 0; T[No].rf = 1; T[No].p = T[p].p;} else sc(T[p].p, No, T[p].d);
    sc(p, T[No].c[
!d], d); sc(No, p, !d); upd(p);
}
void splay(int No)
{
    
int p; while (!T[No].rf) if (T[p = T[No].p].rf) rot(No); else if (T[No].d == T[p].d) {rot(p); rot(No);} else {rot(No); rot(No);} upd(No);
}
int access(int x)
{
    
int tmp = 0;
    
do {
        splay(x); T[T[x].c[
1]].rf = 1; T[tmp].rf = 0; sc(x, tmp, 1); upd(x); tmp = x; x = T[x].p;
    } 
while (x);
}
void cut(int x)
{
    access(x); splay(x); T[T[x].c[
0]].rf = 1; T[T[x].c[0]].p = 0; sc(x, 00); upd(x);
}
void join(int x, int p)
{
    access(x); T[x].p 
= p;
}
int main()
{
    
int m, x, y, z;
    scanf(
"%d"&n); n++;
    re3(i, 
2, n) {scanf("%d"&x); T[i].sz = 1; T[i].rf = 1if (i + x <= n) T[i].p = i + x; else T[i].p = 1;}
    T[
1].sz = 1; T[1].rf = 1; T[0].sz = 0;
    scanf(
"%d"&m);
    re(i, m) {
        scanf(
"%d"&x);
        
if (x == 1) {
            scanf(
"%d"&y); y += 2;
            access(y); splay(y); printf(
"%d\n", T[T[y].c[0]].sz);
        } 
else {
            scanf(
"%d%d"&y, &z); y += 2;
            cut(y); 
if (y + z <= n) join(y, y + z); else join(y, 1);
        }
    }
    
return 0;
}

【易疵点】
(1)注意一个点的父结点p有两种可能:如果该结点是某棵伸展树的根结点则p为它通过轻边连向的另一棵伸展树中的某一个点的编号(在原树中,就是该结点所在伸展树代表的链的最上层的那个节点的父结点),否则为该结点在伸展树中的父结点编号(通过重边相连);
(2)在改接时删除边的时候,如果删除的是轻边则直接把父结点设为0即可,如果是重边则要sc一下再将父结点设为0;
(3)rot里面有一个地方很关键,极易疵!就是如果p是伸展树的根结点,则除了No的rf改为1,p的rf改为0之外,还要把No的父结点设为p的父结点;
(4)本题中不涉及整棵大树的根(就是root),如果需要root,则rot中还要加一句:if (root == p) root = No;
(5)cut里面有一种简便写法(不需要找到x的父结点的):先access(x),将x伸展到根之后,x及其右子树就是原树中以x为根的子树,左子树就是其它部分,所以直接将x与其左子结点断开即可(注意断开的是重边所以要sc一下,再将x的左子结点的父结点设为0、rf设为1,再upd一下);
(6)一定要搞清楚rf的变化(该改时一定要改!)

最后,放上fanhq666超级大神的总结:
01

Feedback

# re: 终于会写动态树了  回复  更多评论   

2012-05-14 15:34 by yimao
受到了一定的启发,thx!

# re: 终于会写动态树了  回复  更多评论   

2012-06-28 23:53 by 蒟蒻
请问大牛...codeforces 121 div1 3fools ans roads...可以用LCT做吗?
题目大概意思是:有一棵树,每条边权值为0,m个操作,给a到b路径上每条边权值都+1,最后问每条边的权值....
只会树链剖分...不知是否LCT...求大牛给个思路...万分感激...

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理