记录编号	142859	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.986 s
提交时间	2014-12-11 11:48:58	内存使用	3.53 MiB

/* 动态树 LinkCutTree 14.12.10 */

#include <cstdio>
#include <algorithm>
using namespace std;

int n;

struct linkcuttree
{
    int ch[200010][2],f[200010],c[200010];
    bool r[200010];
    void init()
    {
        int i;
        scanf("%d",&n);
        for (i=1;i<=n;++i)
        {
            scanf("%d",f+i); f[i]+=i;
            if (f[i]>n) f[i]=n+1;
        }
        for (i=1;i<=n+1;++i) c[i]=1;
        for (i=0;i<=n+1;++i) r[i]=1;
    }
    void update(int p) {c[p]=c[ch[p][0]]+c[ch[p][1]]+1;}
    void rotate(int p,int k)
    {
        int q=ch[p][k];
        ch[p][k]=ch[q][k^1];
        f[ch[p][k]]=p;
        ch[q][k^1]=p;
        if (!r[p]) ch[f[p]][p==ch[f[p]][1]]=q;
        f[q]=f[p]; f[p]=q;
        r[q]=r[p]^r[q]; r[p]=r[p]^r[q];
        update(p); update(q);
    }
    void splay(int p)
    {while (!r[p]) rotate(f[p],p==ch[f[p]][1]);}
    void access(int p)
    {
        int q; splay(p);
        if (ch[p][1])
        {r[ch[p][1]]=1; ch[p][1]=0;}
        while (f[p])
        {
            q=f[p]; splay(q);
            r[ch[q][1]]=1; r[p]=0;
            ch[q][1]=p; update(q);
            splay(p);
        }
    }
    void cut(int p)
    {
        splay(p);
        f[ch[p][0]]=f[p]; r[ch[p][0]]=1;
        ch[p][0]=0; update(p);
    }
}T;

int main()
{
    freopen("bzoj_2002.in","r",stdin);
    freopen("bzoj_2002.out","w",stdout);
    T.init();
    int m; scanf("%d",&m);
    while (m--)
    {
        int x,y,z; scanf("%d",&x);
        if (x==1)
        {
            scanf("%d",&y); ++y; T.access(y);
            printf("%d\n",T.c[T.ch[y][0]]);
        }
        else
        {
            scanf("%d%d",&y,&z); ++y;
            T.cut(y); T.f[y]=y+z;
            if (T.f[y]>n) T.f[y]=n+1;
        }
    }
    fclose(stdin); fclose(stdout);
    return 0;
}