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

　　强行用分块做，算是另一种分块的用法，分块真奇妙啊。

　　受到了来自abclzr的细心教导，首先思考最普通的模拟，发现可以O(n)路径压缩，O(1)的查询，但是需要修改就变成了O（n^2）的修改，于是考虑分块，记录一下每个点跳出该点所在的块的步数，也就是在每块内进行路径压缩，还有记录每个点跳出块后到达的点，同样可以块内路径压缩完成，这样就变成了O(sqrt(n))的修改和查询，但是预处理是O(n*sqrt(n))的，虽然可以过，但是LCT更快啦啦，我偏要写分块啦啦,读入优化背了一晚上WA的锅啦啦啦MD。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #define N 200010 7 using namespace std; 8 int pos[N],st[N],nx[N],k[N]; 9 int n,m,q,block;10 inline int read ()11 {12     char c;13     int ans=0;14     while ((c=getchar())=='\n' || c==' ' || c=='\r');15     ans=c-'0';16     while (isdigit(c=getchar())) ans=ans*10+c-'0';17     return ans;18 } 19 int solve(int x)20 {21     int ans=0;22     while (1)23     {24         ans+=st[x];25         if (!nx[x])    return ans;26         x=nx[x];27     }28 }29 int main()30 {31     n=read();32     block=(int)(sqrt(n));33     for (int i=1;i<=n;i++)34     {35         pos[i]=(i-1)/block+1;36         k[i]=read();37     }38     for (int i=n;i>=1;i--)39     {40         if (i+k[i]>n)    st[i]=1;41         else if (pos[i]==pos[i+k[i]])42              {43                  st[i]=st[i+k[i]]+1;44                  nx[i]=nx[i+k[i]];45              }46         else47             {48                 st[i]=1;49                 nx[i]=i+k[i];50             }51     }52     q=read();53     for (int i=1;i<=q;i++)54     {55         int x,y,z;56         x=read();y=read();57         y++;58         if (x==1) printf("%d\n",solve(y));59         else60         {61         z=read();62             k[y]=z;63             for (int j=y;j>=(pos[y]-1)*block+1;j--)64             {65                 if (j+k[j]>n)    st[j]=1,nx[j]=0;66                 else if (pos[j]==pos[j+k[j]])67                      {68                          st[j]=st[j+k[j]]+1;69                          nx[j]=nx[j+k[j]];70                      }71                      else    72                      {73                          st[j]=1;74                          nx[j]=j+k[j];75                      }    76             }77         }78     }79     return 0;80 }
           
          
         
        
       

 

---

2016.3.24 学LCT，这果然是模板题。。。

 

1 #include 
       
         2 #include 
        
          3 #define N 200020 4 using namespace std; 5 int n,m; 6 struct SplayNode  7 { 8     SplayNode *fa,*ch[2]; 9     int step;10     bool chr() {
     return this==fa->ch[1];}11     bool check() {
     return this!=fa->ch[1] && this !=fa->ch[0];}12     void updata() {step=ch[0]->step+ch[1]->step+1;}13 }*lct[N],*null;14 inline int read() {
     int ans=0; char c; while ((c=getchar())>'9' || c<'0'); ans=c-'0'; while (isdigit(c=getchar())) ans=ans*10+c-'0'; return ans;}15 inline void MakeTree(SplayNode *x) {x->fa=x->ch[1]=x->ch[0]=null; x->step=1;}16 void init() {
     null=new SplayNode; null->fa=null->ch[1]=null->ch[0]=null; null->step=0;}17 inline void rotate(SplayNode *x)18 {19     SplayNode *r=x->fa;20     int t=x->chr();21     if (!r->check()) r->fa->ch[r->chr()]=x;22     x->fa=r->fa;23     r->ch[t]=x->ch[t^1];24     r->ch[t]->fa=r;25     r->fa=x;26     x->ch[t^1]=r;27     r->updata();28 }29 inline void splay(SplayNode *x)30 {31     for (;!x->check();rotate(x))32         if (!x->fa->check())33             if (x->chr()==x->fa->chr())    rotate(x->fa);34             else rotate(x);35     x->updata();36 }37 inline SplayNode *access(SplayNode *x)38 {39     SplayNode *y=null;40     for (;x!=null;y=x,x=x->fa)41     {42         splay(x);43         x->ch[1]=y;44     }45     return y;46 }47 inline void link(SplayNode *x,SplayNode *y)48 {49     access(x); splay(x);50     x->ch[0]->fa=null; x->ch[0]=null; x->fa=y; x->updata();51 }52 int main()53 {54     init();55     n=read(); 56     for (int i=0;i
         
          fa=lct[i+x];66     }67     m=read();68     for (int i=1;i<=m;i++)69     {70         int temp,x,y;71         temp=read(); x=read();72         if (temp==1)73         {74             access(lct[x]); 75             splay(lct[x]);76             printf("%d\n",lct[x]->step);77         }78         else79         {80             y=read();81             if (x+y