题目地址：洛谷：【P3203】[HNOI2010]弹飞绵羊 – 洛谷、BZOJ：Problem 2002. — [Hnoi2010]Bounce 弹飞绵羊

题目描述

某天，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。

输出格式：
对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

输入样例#1：

4
1 2 1 1
3
1 1
2 1 1
1 1

输出样例#1：

2
3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

题解

我们可以考虑把第i个弹力装置和第i+ki个连边，这样我们会建出来一棵树。如果跳超过了就直接连到n+1号点上。如果不改ki的值，答案即为以n+1为根的有根树中i号点的深度。现在要改ki的值，就得动态维护树上信息，就得用LCT。改的时候，切掉i和i+ki的边，然后再加i和新i+ki的边即可。统计信息就统计子树大小。把i到n+1的链split出来以后，Splay里就只有这条链，因此子树大小就是答案。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

// link/cut tree

struct Node {
    int ch[2], fa, sum;
    bool rev;
} tr[MAXN];

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    int fa = tr[p].fa;
    return tr[fa].ch[0] != p && tr[fa].ch[1] != p;
}

inline void update(int p) {
    int ls = tr[p].ch[0], rs = tr[p].ch[1];
    tr[p].sum = tr[ls].sum + tr[rs].sum + 1;
}

inline void reverse(int p) {
    std::swap(tr[p].ch[0], tr[p].ch[1]);
    tr[p].rev ^= 1;
}

inline void pushdown(int p) {
    int ls = tr[p].ch[0], rs = tr[p].ch[1];
    if(tr[p].rev) {
        if(ls) reverse(ls);
        if(rs) reverse(rs);
        tr[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = tr[p].fa;
    } 
    pushdown(p);
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[tr[v].ch[0]].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0;
}

int n, m, k[MAXN], op, ut, wt;

int main() {
    n = readint();
    tr[n + 1].sum = 1;
    for(int i = 1; i <= n; i++) {
        k[i] = readint();
        tr[i].sum = 1;
    }
    for(int i = 1; i <= n; i++) {
        int x = i, y = i + k[i];
        y = std::min(y, n + 1);
        link(x, y);
    }
    m = readint();
    while(m--) {
        op = readint(); ut = readint() + 1;
        if(op == 1) {
            split(ut, n + 1);
            printf("%d\n", tr[n + 1].sum - 1);
        } else {
            wt = readint();
            cut(ut, std::min(ut + k[ut], n + 1));
            k[ut] = wt;
            link(ut, std::min(ut + k[ut], n + 1));
        }
    }
    return 0;
}