BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 9071  Solved: 4652
[Submit][Status][Discuss]

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

HINT

Source

[Submit][Status][Discuss]

将跳转看成边的关系，易知这些转移边形成一棵树。如果以“弹出去”这个状态为根节点，从一个点出发的步数可以转换为深度，或者说是从根节点到这个点的距离。改变一个点的系数，可以视为改变一个点的父节点，但是其子树不会受到影响。显然是个LCT模板题，第一次写还有些许不懂，大体是从这位前辈的blog里学的。

 VAR
     n : longint;
     m : longint;
     siz : array[-..] of longint;
     fat : array[-..] of longint;
     rot : array[-..] of boolean;
     son : array[-..,..] of longint;

 PROCEDURE update(t : longint);
 begin
     siz[t]:=siz[son[t,]]+siz[son[t,]]+;
 end;

 PROCEDURE ltrotate(x : longint);
 var
     y : longint;
 begin
     y:=son[x,];
     son[x,]:=son[y,];
     fat[son[x,]]:=x;
     son[y,]:=x;
     if x=son[fat[x],] then
         son[fat[x],]:=y
     else if x=son[fat[x],] then
         son[fat[x],]:=y;
     fat[y]:=fat[x];
     fat[x]:=y;
     rot[y]:=rot[x] xor rot[y];
     rot[x]:=rot[x] xor rot[y];
     update(x);
     update(y);
 end;

 PROCEDURE rtrotate(x : longint);
 var
     y : longint;
 begin
     y:=son[x,];
     son[x,]:=son[y,];
     fat[son[x,]]:=x;
     son[y,]:=x;
     if x=son[fat[x],] then
         son[fat[x],]:=y
     else if x=son[fat[x],] then
         son[fat[x],]:=y;
     fat[y]:=fat[x];
     fat[x]:=y;
     rot[y]:=rot[x] xor rot[y];
     rot[x]:=rot[x] xor rot[y];
     update(x);
     update(y);
 end;

 PROCEDURE splay(x : longint);
 begin
     while not rot[x] do
         if x=son[fat[x],] then
             ltrotate(fat[x])
         else
             rtrotate(fat[x]);
 end;

 PROCEDURE access(x : longint);
 var
     y : longint;
 begin
     splay(x);
     while fat[x]<> do
     begin
         y:=fat[x];
         splay(y);
         rot[son[y,]]:=true;
         rot[x]:=false;
         son[y,]:=x;
         update(y);
         splay(x);
     end;
 end;

 PROCEDURE main;
 var
     i, x, y, z : longint;
 begin
     read(n);

     for i:= to n do
     begin
         read(fat[i]);
         fat[i]:=fat[i]+i;
         if fat[i]>n then
             fat[i]:=n+;
     end;

     for i:= to n+ do
     begin
         siz[i]:=;
         rot[i]:=true;
     end;

     read(m);

     for i:= to m do
     begin
         read(x);
         if x= then
         begin
             read(y);
             inc(y);
             access(y);
             writeln(siz[son[y,]]);
         end
         else
         begin
             read(y,z);
             inc(y);
             splay(y);
             fat[son[y,]]:=fat[y];
             rot[son[y,]]:=true;
             son[y,]:=;
             siz[y]:=siz[son[y,]]+;
             fat[y]:=y+z;
             if fat[y]>n then
                 fat[y]:=n+;
         end;
     end;
 end;

 BEGIN
     main;
 END.

 #include <bits/stdc++.h>

 #define fread_siz 1024

 inline int get_c(void)
 {
     static char buf[fread_siz];
     static char *head = buf + fread_siz;
     static char *tail = buf + fread_siz;

     if (head == tail)
         fread(head = buf, , fread_siz, stdin);

     return *head++;
 }

 inline int get_i(void)
 {
     register int ret = ;
     register int neg = false;
     register int bit = get_c();

     for (; bit < ; bit = get_c())
         if (bit == '-')neg ^= true;

     for (; bit > ; bit = get_c())
         ret = ret *  + bit - ;

     return neg ? -ret : ret;
 }

 template <class T>
 inline T min(T a, T b)
 {
     return a < b ? a : b;
 }

 const int N = ;

 int n, m;
 int root[N];
 int lson[N];
 int rson[N];
 int size[N];
 int father[N];

 inline void update(int t)
 {
     size[t] = size[lson[t]] + size[rson[t]] + ;
 }

 inline void rotateLeft(int t)
 {
     int r = rson[t];
     rson[t] = lson[r];
     father[rson[t]] = t;
     lson[r] = t;
     if (t == lson[father[t]])
         lson[father[t]] = r;
     else if (t == rson[father[t]])
         rson[father[t]] = r;
     father[r] = father[t];
     father[t] = r;
     update(t);
     update(r);
     root[r] ^= root[t];
     root[t] ^= root[r];
 }

 inline void rotateRight(int t)
 {
     int l = lson[t];
     lson[t] = rson[l];
     father[lson[t]] = t;
     rson[l] = t;
     if (t == lson[father[t]])
         lson[father[t]] = l;
     else if (t == rson[father[t]])
         rson[father[t]] = l;
     father[l] = father[t];
     father[t] = l;
     update(t);
     update(l);
     root[l] ^= root[t];
     root[t] ^= root[l];
 }

 inline void splay(int t)
 {
     while (!root[t])
     {
         if (t == lson[father[t]])
             rotateRight(father[t]);
         else
             rotateLeft(father[t]);
     }
 }

 inline void access(int t)
 {
     splay(t);

     while (father[t])
     {
         int f = father[t];
         splay(f);
         root[rson[f]] = ;
         root[t] = ;
         rson[f] = t;
         update(f);
         splay(t);
     }
 }

 inline void cut(int t)
 {
     splay(t);
     root[lson[t]] = ;
     father[lson[t]] = father[t];
     lson[t] = ;
     update(t);
 }

 signed main(void)
 {
     n = get_i();

     for (int i = ; i <= n; ++i)
         father[i] = min(get_i() + i, n + );

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

     m = get_i();

     for (int i = ; i <= m; ++i)
     {
         int x = get_i(), y, z;
         if (x == )
         {
             y = get_i() + ; access(y);
             printf("%d\n", size[lson[y]]);
         }
         else
         {
             y = get_i() + ; z = get_i();
             cut(y); father[y] = min(n + , y + z);
         }
     }
 }

@Author: YouSiki