HYSBZ2002

【分析】用分块水过了，每个块记录当前点到下一块的第一个位置需要消耗的步数以及下一个位置，那么查询只要跟着这个走花费的总和就是答案，然后对于预处理，只要按每一块从后往前扫描一遍就可以，对于修改只要把修改的块整个重新 计算即可。复杂度m*sqrt(n).

【AC CODE】1856ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 200000+10, SIZE = 500, BLOCK = MAXN/SIZE+10,MAXIN = 100000, MAXOUT = 10000;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write(){ fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}/*必须在程序结束时加 write()*/
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s){ *(pout++) = *(s++); if(pout == pend) write(); }
}
template <class T>
inline void out_int(T x) {
	if(!x){ out_char('0');return;}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x){ outtmp[len++] = x%10+48; x /= 10;}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
int a[MAXN],n;
int cost[BLOCK][SIZE],nxt[BLOCK][SIZE],sn;

int query(int x)
{
	int ans = 0,i = x/SIZE, j = x%SIZE;
	while(1)
	{
		ans += cost[i][j];
		int tmp = nxt[i][j];
		if(tmp >= n) break;
		i = tmp/SIZE;
		j = tmp%SIZE;
	}
	return ans;
}
void update(int x, int v)
{
	int i = x/SIZE, st = i*SIZE,ed = min(n-1,(i+1)*SIZE-1);
	a[x] = v;
	per(j,ed,st)
	{
		if(a[j]+j > ed) cost[i][j%SIZE] = 1,nxt[i][j%SIZE] = a[j]+j;
		else cost[i][j%SIZE] = cost[i][j%SIZE+a[j]]+1, nxt[i][j%SIZE] = nxt[i][j%SIZE+a[j]];
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	while(in(n))
	{
		rep(i,0,n) in(a[i]);
		sn = n/SIZE+(bool)(n%SIZE);
		rep(i,0,sn)
		{
			int ed = min(n-1,(i+1)*SIZE-1), st = i*SIZE;
			per(j,ed,st)
			{
				if(a[j]+j > ed) cost[i][j%SIZE] = 1,nxt[i][j%SIZE] = a[j]+j;
				else cost[i][j%SIZE] = cost[i][j%SIZE+a[j]]+1, nxt[i][j%SIZE] = nxt[i][j%SIZE+a[j]];
			}
		}
		int q;
		in(q);
		while(q--)
		{
			int op,x;
			in(op),in(x);
			if(1 == op) out_int(query(x)),out_char('\n');
			else
			{
				int v;
				in(v);
				update(x,v);
			}
		}
	}
	write();
	return 0;
}