题目链接：[HNOI2010]弹飞绵羊

国内第一道LCT，所以基本上是裸题。

如果我们可以把这个结构想成一棵树，然后如果一个点飞出去，我们可以想成到达另一个节点。所以我们建立一个虚拟节点。

然后用LCT维护子树大小，每次从一个点开始，我们对当前点和虚拟节点拉一条链即可。然后输出子树size。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k[N],ed;
int cnt,st[N];
struct node{int ch[2],fa,sz,re;}t[N];
inline int ls(int x){return t[x].ch[0];}
inline int rs(int x){return t[x].ch[1];}
inline void push_up(int p){
	t[p].sz=t[ls(p)].sz+t[rs(p)].sz+1;
}
inline void push_re(int p){swap(t[p].ch[0],t[p].ch[1]); t[p].re^=1;}
inline void push_down(int p){
	if(!t[p].re)	return;
	if(ls(p))	push_re(ls(p));	if(rs(p))	push_re(rs(p)); t[p].re^=1;
}
inline bool isroot(int x){return ls(t[x].fa)!=x&&rs(t[x].fa)!=x;}
inline void rotate(int x){
	int y=t[x].fa,z=t[y].fa,k=rs(y)==x,w=t[x].ch[!k];
	if(!isroot(y))	t[z].ch[rs(z)==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
	if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z;	push_up(y);
}
inline void splay(int x){
	cnt=1;	st[cnt]=x; int y=x;
	while(!isroot(y))	st[++cnt]=y=t[y].fa;
	while(cnt)	push_down(st[cnt--]);
	while(!isroot(x)){
		int y=t[x].fa,z=t[y].fa;
		if(!isroot(y))	rotate((ls(y)==x)^(ls(z)==y)?x:y); rotate(x);
	}push_up(x);
}
inline void access(int x){
	for(int y=0;x;x=t[y=x].fa) splay(x),t[x].ch[1]=y,push_up(x); 
}
inline void makeroot(int x){
	access(x); splay(x); push_re(x);
}
inline int find(int x){
	access(x); splay(x); while(ls(x)) push_down(x),x=ls(x); 
	splay(x);	return x;
}
inline void split(int x,int y){
	makeroot(x); access(y); splay(y);
}
inline void link(int x,int y){
	makeroot(x); 	t[x].fa=y;
}
inline void cut(int x,int y){
	makeroot(x); 
	if(find(y)==x&&t[y].fa==x&&!ls(y)) t[y].fa=t[x].ch[1]=0,push_up(x);
}
signed main(){
	cin>>n; ed=n+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&k[i]);	link(i,min(i+k[i],ed));
	}
	cin>>m;
	while(m--){
		int op,x,y;	scanf("%d %d",&op,&x); x++;
		if(op==1)	split(ed,x),printf("%d\n",t[x].sz-1);
		else{
			scanf("%d",&y);	cut(x,min(x+k[x],ed));
			k[x]=y;	link(x,min(x+k[x],ed));
		}	
	}
	return 0;
}