弹飞河鼠

今天写这一篇题解完全是因为愤怒。。。

好的，先来看题。

题目描述

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

输入输出格式

输入格式：

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1。

接下来一行有n个正整数，依次为那n个装置的初始弹力系数。

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

2
3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

关于这道题，如果不是因为lbg大佬帮我dbug，我可能就真的惨死在这道题上了。。。（十分感谢）

好了，不废话了，进入正题。

这道题的正解LCT我并没有学过，所以我也只能用万恶的分块（骗分利器）了。。。

思路其实很简单，我们将整个序列分成若干个块（块的大小取决于数据，但是我们一般都会默认为√n），对于每一块的每一个点我们只要维护他弹出这个块还需几步和弹出之后会到达哪一个点即可。

关于修改，由于每一个块之间都是相互独立的，所以单点修改只需要维护每一个块就可以了，并且由于每一个点的数据都建立在他后面块的基础上，所以我们对于每一个块都需要倒着来进行维护。

而对于查询我们只要循着每一个点的指向，累加每一个点的sum值，大于n的时候跳出即可。

PS：由于装置是从零开始计数的所以读入数据时不要忘了加一！！！

最后，附上本题代码：（码风较丑，勿喷、、、）

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 struct pot
 6 {
 7     int to,k,conti,sum;
 8 }p[200005];
 9 int size,cnt=1,n;
10 void change(int ct)
11 {
12     //printf("%d
",size);
13     for(int j=min(ct*size,n);j>(ct-1)*size;j--)
14     {
15         if(j + p[j].k > ct * size || j + p[j].k > n) p[j].sum = 1,p[j].to = j + p[j].k;
16         else
17         {
18             p[j].to=p[j+p[j].k].to;
19             p[j].sum=p[j+p[j].k].sum + 1;
20         }
21         //printf("%d
",p[j].to);
22     }
23 }
24 int query(int y)
25 {
26     int ans=0;
27     while(y<=n)
28     {
29         ans+=p[y].sum;
30         //printf("%d
",ans);
31         y=p[y].to;
32     }
33     return ans;
34 }
35 int main()
36 {
37     int temp = 0;
38     scanf("%d",&n);
39     size=sqrt(n);
40     for(int i=1;i<=n;i++)
41     {
42         temp++;
43         if(temp>size)
44         {
45             cnt++;
46             temp=1;
47         }
48         scanf("%d",&p[i].k);
49         p[i].conti=cnt;
50     }
51     //if(temp != 0) cnt++;
52     //printf("%d
",cnt);
53     for(int i=cnt;i >= 1;i--)
54         change(i);
55     int m;
56     scanf("%d",&m);
57     for(int i=1;i<=m;i++)
58     {
59         int x,y,z;
60         scanf("%d%d",&x,&y);
61         if(x==1)
62             printf("%d
",query(y+1));
63         else
64         {
65             scanf("%d",&z);
66             p[y+1].k=z;
67             //printf("%d
",p[y].k); 
68             change(p[y+1].conti);
69         }
70     }
71     return 0;
72 }