BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊 分块

#include<cstdio>
#include<iostream>
#include<cmath>
#define R register int
using namespace std;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==‘-‘?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int T,n,m;
int k[200010],pos[200010],cnt[200010],nxt[200010];
inline void change(int p,int inc) {
    k[p]=inc;
    for(R i=p;i>=T*(pos[p]-1);--i) {
        if(i+k[i]>min(T*pos[i],n)) cnt[i]=1,nxt[i]=i+k[i];
        else cnt[i]=cnt[i+k[i]]+1,nxt[i]=nxt[i+k[i]];
    }
}
inline int query(int p) { R ret=0;
    while(p<=n) ret+=cnt[p],p=nxt[p];
    return ret;
}
signed main() {
    n=g(); T=sqrt(n)+1;
    for(R i=1;i<=n;++i) k[i]=g();
    for(R i=1;i<=n;++i) pos[i]=(i-1)/T+1;
    for(R i=n;i>=1;--i) 
        if(i+k[i]>min(T*pos[i],n)) cnt[i]=1,nxt[i]=i+k[i];
        else cnt[i]=cnt[i+k[i]]+1,nxt[i]=nxt[i+k[i]]; 
    m=g(); for(R i=1;i<=m;++i) {
        R k=g(),p=g(),d;
        if(k&1) printf("%d\n",query(p+1));
        else d=g(),change(p+1,d);
    }
}