题目链接
把每个点和能跳到的点连边，于是就构成了一个森林。
查询操作就是该点到根的路径长度，修改操作就相当于删边再重新连边。
显然是\(LCT\)的强项。
查询时\(access(x),splay(x)\)，然后输出\(size[x]\)就行了。
修改时\(access(x),splay(x)\)，然后双向断掉\(x\)与左儿子的边，然后直接和\(x+y\)连边即可。
简化版的\(LCT\)
#include <cstdio>
#define R register int
#define I inline void
#define lc c[x][0]
#define rc c[x][1]
const int MAXN = 300010;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
int f[MAXN], c[MAXN][2], v[MAXN], s[MAXN], sz[MAXN], st[MAXN], tag[MAXN];
inline int nroot(R x){
return c[f[x]][0] == x || c[f[x]][1] == x;
}
I pushup(R x){
s[x] = s[lc] ^ s[rc] ^ v[x];
sz[x] = sz[lc] + sz[rc] + 1;
}
I swap(R x){
lc ^= rc; rc = lc ^ rc; lc ^= rc; tag[x] ^= 1;
}
I pushdown(R x){
if(tag[x]){
swap(lc); swap(rc);
tag[x] = 0;
}
}
I rotate(R x){
R y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k];
if(nroot(y)) c[z][c[z][1] == y] = x;
c[x][!k] = y; c[y][k] = w; f[y] = x; f[x] = z;
if(w) f[w] = y;
pushup(y);
}
I splay(R x){
R y = x, z = 0;
st[++z] = y;
while(nroot(y)) st[++z] = y = f[y];
while(z) pushdown(st[z--]);
while(nroot(x)){
y = f[x]; z = f[y];
if(nroot(y)) (c[z][1] == y) ^ (c[y][1] == x) ? rotate(x) : rotate(y);
rotate(x);
}
pushup(x);
}
I access(R x){
for(R y = 0; x; x = f[y = x]){
splay(x); rc = y; pushup(x);
}
}
int n, m, opt, a, b;
int main(){
n = read();
for(R i = 1; i <= n; ++i){
a = read();
if(i + a <= n) f[i] = i + a;
}
m = read();
while(m--){
opt = read(); a = read() + 1;
switch(opt){
case 1 : access(a); splay(a); printf("%d\n", sz[a]); break;
case 2 : b = read(); access(a); splay(a); c[a][0] = f[c[a][0]] = 0; if(a + b <= n) f[a] = a + b; break;
}
}
return 0;
}