题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2002
题意：中文题面
思路：考虑分块，每个位置维护一个跳出该块需要的步数cnt[],和跳出该块后到达下一块的哪个位置to[]。
关于修改操作：直接修改所在块的左端点到修改的位置。 然后需要逆序修改。因为后面的位置的值会影响到前面位置的值。
关于询问操作：直接暴力计算即可。
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
int belong[MAXN], block, num, L[MAXN], R[MAXN];
int n, q;
int a[MAXN], cnt[MAXN], to[MAXN];
void build(){
block = (int)sqrt(n + 0.5);
num = n / block; if (n%block){ num++; }
for (int i = ; i <= num; i++){
L[i] = (i - )*block + ; R[i] = i*block;
}
R[num] = n;
for (int i = ; i <= n; i++){
belong[i] = ((i - ) / block) + ;
}
for (int i = num; i>; i--){
for (int j = R[i]; j >= L[i]; j--){
if (j + a[j]>R[i]){
cnt[j] = ; to[j] = min(n+,j + a[j]);
}
else{
cnt[j] = cnt[j + a[j]] + ; to[j] = min(n+,to[j + a[j]]);
}
}
}
}
void modify(int pos, int val){
a[pos] = val;
for (int i = pos; i >= L[belong[pos]]; i--){
if (i + a[i]>R[belong[pos]]){
cnt[i] = ; to[i] = min(i + a[i], n + );
}
else{
cnt[i] = cnt[i + a[i]] + ; to[i] = min(to[i + a[i]], n + );
}
}
}
int query(int pos){
int ans = ;
for (int i = pos; i <= n; i = to[i]){
ans += cnt[i];
}
return ans;
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
while (~scanf("%d", &n)){
for (int i = ; i <= n; i++){ scanf("%d", &a[i]); }
build(); scanf("%d", &q);
int type, pos, v;
for (int i = ; i <= q; i++){
scanf("%d", &type);
if (type == ){
scanf("%d", &pos); pos++; printf("%d\n", query(pos));
}
else{
scanf("%d%d", &pos, &v); pos++; modify(pos, v);
}
}
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}