[洛谷P3203][HNOI2010]弹飞绵羊

题目大意：有$n$个节点，第$i$个节点有一个弹力系数$k_i$，当到达第$i$个点时，会弹到第$i+k_i$个节点，若没有这个节点（$i+k_i>n$）就会被弹飞。有两个操作：

1. $x：$询问从第$x$个节点开始要多少次会被弹飞
2. $x,y：$把第$x$个点的弹力系数修改为$y$。

题解：建一个节点标号$n+1$，所有大于$n$的位置都连向这，表示会被弹飞。其他每个节点向会被弹到的节点连边（$i->k_i+i$），发现这样会构成一棵树。

询问就是问该点的深度（到$n+1$的距离）。修改就是把原来的边切断，再连上一条新边。可以想到$LCT$，只需要维护每个点到链顶的距离即可。

卡点：1.$get$函数写错

2.在$link$和$cut$操作中换了根，但是在询问中是按照根为$n+1$来做的

C++ Code：

#include <cstdio>

#define maxn 200010

#define lc(rt) son[rt][0]

#define rc(rt) son[rt][1]

using namespace std;

int sz[maxn], son[maxn][2], fa[maxn], tg[maxn];

inline int min(int a, int b) {return a < b ? a : b;}

inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}

inline int get(int rt, int flag = 1) {return son[fa[rt]][flag] == rt;}

inline bool is_root(int rt) {return !(get(rt, 0) || get(rt));}

inline void update(int rt) {sz[rt] = sz[lc(rt)] + sz[rc(rt)] + 1;}

inline void pushdown(int rt) {

    tg[rt] ^= 1; tg[lc(rt)] ^= 1; tg[rc(rt)] ^= 1;

    swap(lc(rt), rc(rt));

}

inline void rotate(int x) {

    int y = fa[x], z = fa[y], b = get(x);

    if (!is_root(y)) son[z][get(y)] = x;

    fa[son[y][b] = son[x][!b]] = y; son[x][!b] = y;

    fa[y] = x, fa[x] = z;

    update(y), update(x);

}

int stack[maxn], top;

inline void splay(int x) {

    stack[top = 1] = x;

    for (int y = x; !is_root(y); stack[++top] = y = fa[y]);

    for (; top; top--) if (tg[stack[top]]) pushdown(stack[top]);

    for (; !is_root(x); rotate(x)) if (!is_root(fa[x]))

        get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);

    update(x);

}

inline void access(int rt) {for (int t = 0; rt; rc(rt) = t, t = rt, rt = fa[rt]) splay(rt);}

inline void make_root(int rt) {access(rt), splay(rt), tg[rt] ^= 1;}

inline void link(int x, int y) {make_root(x), fa[x] = y;}

inline void split(int x, int y) {make_root(x), access(y), splay(y);}

inline void cut(int x, int y) {split(x, y), lc(y) = fa[x] = 0;}

int n, m;

inline int ask(int rt) {

	make_root(n + 1);

    access(rt);

    splay(rt);

    return sz[rt] - 1;

}

int s[maxn];

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d", &s[i]);

        link(i, min(n + 1, i + s[i]));

    }

    scanf("%d", &m);

    for (int i = 0; i < m; i++) {

        int op, x, y;

        scanf("%d%d", &op, &x); x++;

        if (op == 1) printf("%d\n", ask(x));

        else {

            scanf("%d", &y);

            cut(x, min(n + 1, x + s[x]));

            s[x] = y;

            link(x, min(n + 1, x + y));

        }

    }

    return 0;

}