[HNOI 2010]Bounce 弹飞绵羊

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

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

Sample Input

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

Sample Output

2
3

题解

首先，建立一个虚拟节点$n+1$，绵羊到达这个节点即被弹飞。

对于每个装置，

如果$i+K_i<=n$，则执行$Link(i,i+K_i)$，否则$Link(i,n+1)$。

对于修改操作，先执行$Cut(j,j+K_j)$（如果$j+K_j>n$则为$n+1$），再执行$Link(j,j+k)$（如果$j+k>n$则为$n+1$），

并把$K_j$赋为$k$。

对于询问操作，分别执行$MakeRoot(n+1)$，$MakeRoot(x)$，最终答案即为$size[x]-1$。

其中$size[i]$表示平衡树中节点$i$的子树的大小。

 //It is made by Awson on 2017.12.24

 #include <map>

 #include <set>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <cstdio>

 #include <string>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 using namespace std;

 const int N = ;

 int n, m, k[N+], opt, a, b;

 struct Link_Cut_Tree {

     int ch[N+][], pre[N+], size[N+], isrt[N+], rev[N+];

     Link_Cut_Tree () {

     memset(isrt, , sizeof(isrt));

     }

     void pushup(int o) {

     if (!o) return;

     size[o] = size[ch[o][]]+size[ch[o][]]+;

     }

     void pushdown(int o) {

     if (!o || !rev[o]) return;

     int ls = ch[o][], rs = ch[o][];

     swap(ch[ls][], ch[ls][]), swap(ch[rs][], ch[rs][]);

     rev[ls] ^= , rev[rs] ^= , rev[o] = ;

     }

     void push(int o) {

     if (!isrt[o]) push(pre[o]);

     pushdown(o);

     }

     void rotate(int o, int kind) {

     int p = pre[o];

     ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;

     if (isrt[p]) isrt[o] = , isrt[p] = ;

     else ch[pre[p]][ch[pre[p]][] == p] = o;

     pre[o] = pre[p];

     ch[o][kind] = p, pre[p] = o;

     pushup(ch[o][kind]), pushup(o);

     }

     void splay(int o) {

     push(o);

     while (!isrt[o]) {

         if (isrt[pre[o]]) rotate(o, ch[pre[o]][] == o);

         else {

         int p = pre[o], kind = ch[pre[p]][] == p;

         if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);

         else rotate(p, kind), rotate(o, kind);

         }

     }

     }

     void access(int o) {

     int y = ;

     while (o) {

         splay(o); size[o] -= size[ch[o][]];

         isrt[ch[o][]] = , isrt[ch[o][] = y] = ;

         o = pre[y = o];

         pushup(o);

     }

     }

     void makeroot(int o) {

     access(o), splay(o);

     rev[o] ^= , swap(ch[o][], ch[o][]);

     }

     void link(int x, int y) {

     makeroot(x); pre[x] = y;

     }

     void cut(int x, int y) {

     makeroot(x), access(y), splay(y);

     size[y] -= size[x];

     ch[y][] = pre[x] = , isrt[x] = ;

     }

     int query(int x) {

     makeroot(n+), makeroot(x);

     return size[x]-;

     }

 }T;

 void work() {

     scanf("%d", &n);

     for (int i = ; i <= n; i++) T.size[i] = ;

     for (int i = ; i <= n; i++) {

     scanf("%d", &k[i]);

     T.link(i, Min(k[i]+i, n+));

     }

     scanf("%d", &m);

     while (m--) {

     scanf("%d", &opt);

     if (opt == ) {

         scanf("%d", &a); a++;

         printf("%d\n", T.query(a));

     }else {

         scanf("%d%d", &a, &b); a++;

         T.cut(a, Min(k[a]+a, n+));

         k[a] = b;

         T.link(a, Min(k[a]+a, n+));

     }

     }

 }

 int main() {

     work();

     return ;

 }

巴特西