Bounce 弹飞绵羊

Bounce 弹飞绵羊

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2002

分块

将整个大区间分成若干块，每个点维护到下一个块需要跳的次数以及会跳到哪个点（分块要注意细节，区间开闭容易弄乱）。

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<cmath>
 5 #define B (int(sqrt(n)))
 6 #define N 200000
 7 using namespace std;
 8 struct nod{
 9     int num;
10     int next,cost;
11 }a[N+5];
12 int n,m;
13 int main(void){
14     scanf("%d",&n);
15     for(int i=0;i<n;++i)
16         scanf("%d",&a[i].num);
17     for(int i=n-1;i>=0;--i){
18         int index=i+a[i].num;
19         int R=min(n,((i/B)+1)*B);
20         if(index>=R){/**直接if(index/B>i/B)会出现始终不成立的情况导致后面陷入死循环**/
21             a[i].cost=1;
22             a[i].next=index;
23         }else{
24             a[i].cost=a[index].cost+1;
25             a[i].next=a[index].next;
26         }
27     }
28     scanf("%d",&m);
29     while(m--){
30         int type;
31         scanf("%d",&type);
32         if(type==1){
33             int index,sum=0;
34             scanf("%d",&index);
35             while(index<n){
36                 sum+=a[index].cost;
37                 index=a[index].next;
38             }
39             printf("%d
",sum);
40         }else if(type==2){
41             int index,num;
42             scanf("%d%d",&index,&num);
43             int block=index/B;
44             a[index].num=num;
45             for(int i=index;i>=block*B;--i){
46                 int t=a[i].num+i;
47                 int R=min(n,(block+1)*B);
48                 if(t>=R){
49                     a[i].cost=1;
50                     a[i].next=t;
51                 }else{
52                     a[i].cost=a[t].cost+1;
53                     a[i].next=a[t].next;
54                 }
55             }
56         }
57     }
58 }