更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19626422

大意

维护一个包含 $n$ 个弹力装置的数组，每个装置 $i$ 有弹力系数 $k_i$，绵羊从 $i$ 出发会弹到 $i + k_i$ 的位置，超出范围则弹飞。需要处理两种操作：查询从指定装置出发被弹飞的次数，以及修改指定装置的弹力系数

思路

如果说，从当前节点 $i$ 向节点 $i + k_i$ 连一条边，那么最终我们把跳出去的部分，设为 $n + 1$ 节点，那么我们就得到了一颗以 $n + 1$ 为根的树，每次我们要统计的就是 $i$ 到根的路径上的所有点之和。

但是由于这个东西需要动态的修改和查询，我们就可以用 $\text{LCT}$ 解决这个问题。

由于根节点是固定的，所以我们就不需要很多其他的奇妙操作了，只需要 splay 和 access 即可。

在查询的时候，只需要把 $x$ access 后 splay 到根即可，答案就是左子树大小，修改同理。

代码

#include<iostream>
#include<vector>
using namespace std;

#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa

const int MAXN = 2 * 1e5 + 5;
vector<int> G[MAXN];
struct node{
	int ch[2], sz, fa;
}t[MAXN];

bool isroot(int x){
	return lc(fa(x)) != x && rc(fa(x)) != x;
}

void pushup(int x){
	t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
}

void rotate(int x){
	int y = fa(x), z = fa(y);
	int k = (rc(y) == x);
	if(!isroot(y)){
		t[z].ch[rc(z) == y] = x;
	}
	fa(x) = z;
	t[y].ch[k] = t[x].ch[k ^ 1];
	if(t[x].ch[k ^ 1]){
		fa(t[x].ch[k ^ 1]) = y;
	}
	t[x].ch[k ^ 1] = y;
	fa(y) = x;
	pushup(y);
	pushup(x);
}

void splay(int x){
	while(!isroot(x)){
		int y = fa(x), z = fa(y);
		if(!isroot(y)){
			(rc(y) == x) ^ (rc(z) == y) ? rotate(x) : rotate(y);
		}
		rotate(x);
	}
}

void access(int x){
	for(int y = 0;x;y = x, x = fa(x)){
		splay(x);
		rc(x) = y;
		pushup(x);
	}
}

int n, m, k[MAXN];

int main(){
	
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> k[i];
		t[i].sz = 1;
		fa(i) = (i + k[i]) > n ? n + 1 : (i + k[i]);
	}
	cin >> m;
	while(m --){
		int op, x, v; cin >> op >> x;
		x ++;
		if(op == 1){
			access(x);
			splay(x);
			cout << t[lc(x)].sz << '\n';
		}
		else{
			cin >> v;
			access(x);
			splay(x);
			lc(x) = fa(lc(x)) = 0;
			pushup(x);
			k[x] = v;
			fa(x) = x + v > n ? n + 1 : x + v;
		}
	}
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19434487

大意

在 $i$ 的地方会向后跳 $a[i]$ 次，然后带修询问你最少需要跳几次能跳出这个长度为 $n$ 的地方

思路

首先我们发现每个点的弹出，会影响下一个点 $i + a[i]$，也就是说我们如果暴力的考虑的话，就只需修改的时候向后一直跳。

但是这样很劣啊，我们可以考虑用分块处理这个问题，我们可以考虑倒序处理，当后面的点处理过后，你就可以把前面的点从后面转移。

于是我们只需要记录 $cnt[i]$ 次才能跳出第 $i$ 块，以及 $nxt[i]$ 弹出块后落到的第一个位置。

那么我们就可以分块直接处理这个玩意，当一个点被修改的时候，只会影响这个点所在的块，直接重新对这个块建一遍即可。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 2 * 1e5 + 5;
int n, m, B, sz = 0;
int a[MAXN], cnt[MAXN], nxt[MAXN];

inline void build(int x){
    int l = x * B + 1;
    int r = min(n, (x + 1) * B);
    for(int i = r; i >= l; i--){
        int nx = i + a[i];
        if(nx > n){
            cnt[i] = 1;
            nxt[i] = -1;
        }
        else if(nx > r){
            cnt[i] = 1;
            nxt[i] = nx;
        }
        else{
            cnt[i] = 1 + cnt[nx];
            nxt[i] = nxt[nx];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

	cin >> n;

    B = sqrt(n);
    sz = (n - 1) / B + 1;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < sz; i++){
        build(i);
    }

    cin >> m;
    while(m --){
        int op; cin >> op;
        if(op == 1){
            int x; cin >> x;
            x ++;
            int res = 0;
            while(x != -1){
                res += cnt[x];
                x = nxt[x];
            }
            cout << res << '\n';
        }
        else{
            int x, y; cin >> x >> y;
            x ++;
            a[x] = y;
            int p = (x - 1) / B;
            build(p);
        }
    }

    return 0;
}