题目传送门(BZOJ)
>原文链接<

题解 :

我们建立一个虚拟点n+1, 设弹到它就算弹出去.

修改 :

对于一个点x, 其弹力为k, 那么相当于xx+k有一条边,

对于修改, 相当于断掉这条边, 再链接一条(x, x+k’)(k’是新的弹力)

对于x+k > n的, 这个就会弹出去, 我们向n+1连边.

就这样, 初始化和修改已经有了方法, 考虑如何查询;

查询 :

我们令x指向的边是x的父亲(连边操作都在LCT中完成),

那么查询一个点弹几次会弹出去就是查询它跳fa能跳多少次跳到n+1

所以我们$makeRoot(n+1) 我们再Access(x), 这样这条路径(n+1, x)就被我们拿出来当成一棵Splay了, 由于Splay的关键字是深度, 所以我们可以直接把xSplay上去, 这样, x的左子树大小, 就是这条链上深度比它浅的点的数量, 也就是要弹多少次才能弹出去, 所以siz[ls]$就是答案啦.

代码 :

#include <bits/stdc++.h>using namespace std;#define ls ch[p][0]#define rs ch[p][1]const int N = 210000;int ch[N][2], f[N], siz[N], tag[N], nxt[N];class Input_Output { char buf[100000], *p1, *p2; char Nc() { return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin)), p1==p2?EOF:*p1++; }public: int Read() { int x = 0;char c = Nc(); while(!isdigit(c)) c = Nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+c-48, c=Nc(); return x; }}I_O;class Link_Cut_Tree {private: int Get(int p) { return ch[f[p]][1] == p; } bool IsRoot(int p) { return ch[f[p]][1] != p&&ch[f[p]][0]!=p; } void PushUp(int p) { siz[p] = siz[ls]+siz[rs]+1; } void PushDown(int p) { if(tag[p]) { tag[p] = 0; swap(ch[ls][0], ch[ls][1]); swap(ch[rs][0], ch[rs][1]); tag[ls] ^= 1, tag[rs] ^= 1; } return; } void Update(int p) { if(!IsRoot(p)) Update(f[p]); PushDown(p); } void Rotate(int x) { int y = f[x], z = f[y], k = Get(x); if(!IsRoot(y)) ch[z][ch[z][1] == y] = x; ch[y][k] = ch[x][!k]; f[ch[y][k]] = y; ch[x][!k] = y; f[y] = x, f[x] = z; PushUp(y), PushUp(x); }public: void Splay(int x) { Update(x); for(int fa;fa = f[x], !IsRoot(x);Rotate(x)) if(!IsRoot(fa)) Rotate(Get(x) == Get(fa)?fa:x); } void Access(int x) { for(int fa = 0; x; fa = x, x = f[x]) Splay(x), ch[x][1] = fa, PushUp(x); } void MakeRoot(int p) { Access(p);Splay(p); swap(ls, rs); tag[p] ^= 1; } void Split(int x, int y) { MakeRoot(x); Access(y); Splay(y); } int Find(int p) { Access(p); Splay(p); while(ls) PushDown(p), p = ls; Splay(p); return p; } void Link(int x, int p) { MakeRoot(x); f[x] = p; Splay(x); } void Cut(int x, int p) { Split(x, p); ls = f[x] = 0; }}LCT;class Init_And_Solve { int n, m;public: void Init() { n = I_O.Read(); for(int i = 1; i <= n; i ++ ) { int x = I_O.Read(); f[i] = x+i; siz[i] = 1; if(f[i]>n+1) f[i] = n+1; nxt[i] = f[i]; } siz[n+1]=1; } void Solve() { m = I_O.Read(); for(int i = 1; i <= m; i ++ ) { int opt = I_O.Read(); if(opt == 1) { int x = I_O.Read(); LCT.MakeRoot(n+1); x++; LCT.Access(x); LCT.Splay(x); printf("%d\n", siz[ch[x][0]]); } else { int x = I_O.Read(), y = I_O.Read(); x ++ ; int to = min(n+1, x+y); LCT.Cut(x, nxt[x]); LCT.Link(x, to); nxt[x] = to; } } }}init;int main() { init.Init(); init.Solve();}