ACM►数据结构►LCT

LCT(模板-待填坑)

题目链接：

bzoj2002

题目大意：

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

题目分析：

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 212345;
 
struct Node {
    int fa, son[2];
    int siz;
 
    inline int &l() { return son[0]; }
    inline int &r() { return son[1]; }
 
    void init() {
        fa = son[0] = son[1] = 0;
        siz = 1;
    }
    void maintain();
} node[MAX];
 
void Node::maintain() {
    siz = 1 + node[l()].siz + node[r()].siz;
}
 
int ori(int st) {
    if (node[st].fa < 0) return 0;
    return st == node[node[st].fa].r();
}
 
int f(int x) {
    return node[x].fa;
}
 
void setc(int st, int sn, int d) {
    if (st > 0) {
        node[st].son[d] = sn;
        node[st].maintain();
    }
    if (sn > 0) node[sn].fa = st;
}
 
void zg(int x) {
    int st = f(x);
    int p = f(st);
    int d = ori(x), dst = ori(st);
    setc(st, node[x].son[d^1], d);
    setc(x, st, d^1);
    setc(p, x, dst);
}
 
void splay(int x) {
    while (f(x) > 0) {
        if (f(f(x)) <= 0) zg(x);
        else {
            if (ori(x) == ori(f(x))) zg(f(x));
            else zg(x);
            zg(x);
        }
    }
}
 
void access(int x) {
    splay(x);
    while (node[x].fa < 0) {
        int fa = -node[x].fa;
        splay(fa);
        node[node[fa].r()].fa *= -1;
        setc(fa, x, 1);
        splay(x);
    }
}
 
int findroot(int x) {
    access(x);
    while (node[x].l()) x = node[x].l();
    splay(x);
    return x;
}
 
void link(int st, int x) {
    access(x);
    node[x].fa = -st;
    access(x);
}
 
void cut(int x) {
    access(x);
    node[node[x].l()].fa = 0;
    node[x].son[0] = 0;
}
 
int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) node[i].init();
    node[0].siz = 0;
 
    int x;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        if (i + x <= n) link(i + x, i);
    }
    scanf("%d", &m);
    int ord, v;
    while (m--) {
        scanf("%d %d", &ord, &x);
        x++;
        if (ord == 1) {
            access(x);
            printf("%d\n", node[node[x].l()].siz + 1);
        } else {
            scanf("%d", &v);
            cut(x);
            if (x + v <= n) link(x + v, x);
        }
    }
}

解题过程：