更好的阅读体验：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;
}