记录编号	480293	评测结果	AAAAAAAAAA
题目名称	[HNOI 2010] 弹飞绵羊	最终得分	100
用户昵称	xzz_233	是否通过	通过
代码语言	C++	运行时间	2.855 s
提交时间	2017-12-26 07:57:05	内存使用	6.73 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
typedef long long ll;
il int gi(){
	int a;scanf("%d",&a);return a;
}
const int maxn=200001;
int t[maxn],n,jiafdjf;
namespace LCT{
    int ch[maxn][2],fa[maxn],siz[maxn];bool rev[maxn];
    il vd upd(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
    il bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    il vd down(int x){if(rev[x])rev[x]=0,rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,std::swap(ch[x][0],ch[x][1]);}
    il vd rotate(int x){
        sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1];
        if(!isrt(y))ch[z][y==ch[z][1]]=x;fa[x]=z;
        ch[y][o]=ch[x][!o],fa[ch[x][!o]]=y;
        ch[x][!o]=y,fa[y]=x;
        upd(y);
    }
    il vd splay(int x){
        sta int stk[maxn],top;stk[top=1]=x;
        for(rg int i=x;!isrt(i);i=fa[i])stk[++top]=fa[i];
        while(top)down(stk[top--]);
        for(rg int y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y])
            if(!isrt(y))rotate(((x==ch[y][0])^(y==ch[z][0]))?y:x);
        upd(x);
    }
    il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);}
    il vd makert(int x){access(x),splay(x),rev[x]^=1;}
    il vd link(int x,int y){makert(x),fa[x]=y;}
    il vd cut(int x,int y){makert(x),access(y),splay(y);fa[x]=ch[y][0]=0;}
    il int query(int x){makert(jiafdjf),access(x),splay(x);return siz[x]-1;}
}
int main(){
	freopen("bzoj_2002.in","r",stdin);
	freopen("bzoj_2002.out","w",stdout);
    n=gi(),jiafdjf=n+1;
    using namespace LCT;
    for(rg int i=1;i<=n;++i)link(i,t[i]=std::min(i+gi(),jiafdjf));
    int m=gi(),u;
    makert(jiafdjf);
    while(m--)
        if(gi()==1)printf("%d\n",query(gi()+1));
        else u=gi()+1,cut(t[u],u),t[u]=std::min(u+gi(),jiafdjf),link(u,t[u]);
    return 0;
}