Bounce 弹飞绵羊
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2002
分块
将整个大区间分成若干块，每个点维护到下一个块需要跳的次数以及会跳到哪个点（分块要注意细节，区间开闭容易弄乱）。
代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define B (int(sqrt(n)))
#define N 200000
using namespace std;
struct nod{
int num;
int next,cost;
}a[N+];
int n,m;
int main(void){
scanf("%d",&n);
for(int i=;i<n;++i)
scanf("%d",&a[i].num);
for(int i=n-;i>=;--i){
int index=i+a[i].num;
int R=min(n,((i/B)+)*B);
if(index>=R){/**直接if(index/B>i/B)会出现始终不成立的情况导致后面陷入死循环**/
a[i].cost=;
a[i].next=index;
}else{
a[i].cost=a[index].cost+;
a[i].next=a[index].next;
}
}
scanf("%d",&m);
while(m--){
int type;
scanf("%d",&type);
if(type==){
int index,sum=;
scanf("%d",&index);
while(index<n){
sum+=a[index].cost;
index=a[index].next;
}
printf("%d\n",sum);
}else if(type==){
int index,num;
scanf("%d%d",&index,&num);
int block=index/B;
a[index].num=num;
for(int i=index;i>=block*B;--i){
int t=a[i].num+i;
int R=min(n,(block+)*B);
if(t>=R){
a[i].cost=;
a[i].next=t;
}else{
a[i].cost=a[t].cost+;
a[i].next=a[t].next;
}
}
}
}
}