Description：

有一排 $n$ 个装置，第 $i$ 个装置可以向后弹 $a[i]$ 格， $a[i]$ 可以为负数和零，问落到某个位置后弹几次会被弹出序列。

$1\le n \le 200000$

Solution：

如果把弹看作一条有向边，那么整个图就是一个基环内向树森林加内向树森林，每次查询就是查询这个点到根节点的距离，像弹飞绵羊一样，可以用 $LCT$ 维护有根树，但基环树不好维护，于是可以再有根树的根节点开一个变量 $pos$ 记录根节点连出去的那个点，由于是有根树，所以不能 $makeroot$ ，还要注意 $link$ 和 $cut$ 都是有方向的，在 $link$ 时，如果他们已经被连了起来，那么其中一个一定是根，不然不会有出边，于是把 $pos$ 设成对应的点即可，否则像普通的一样连一个虚父亲，注意不能 $makeroot$ 。 $cut$ 要复杂一些，首先如果当前节点是根，那么就应该把 $pos$ 删掉，如果不是根，那么如果这条边不是环中的边，那么直接删，否则把这条边断掉后原来记在 $pos$ 里的那一条边就应该连上，注意连上后要清空 $pos$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

int a[MAXN];

struct node

{

	int c[2],fa,siz;

}t[MAXN];

int pos[MAXN];

inline void maintain(int rt){t[rt].siz = t[t[rt].c[0]].siz + t[t[rt].c[1]].siz + 1;return;}

inline void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

inline bool isroot(int x){return (t[t[x].fa].c[0] != x && t[t[x].fa].c[1] != x);}

inline int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

inline void rotate(int x)

{

	register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

inline void splay(int x)

{

	while(!isroot(x))

	{

		register int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

inline void access(int k)

{

	for(register int i = 0;k;i = k,k = t[k].fa)

	{

		splay(k);t[k].c[1] = i;maintain(k);

	}

	return;

}

inline int find(int k)

{

	access(k);splay(k);

	while(t[k].c[0])k = t[k].c[0];

	return k;

}

void link(int x,int f)

{

	if(find(f) == x)pos[x] = f;

	else{access(x);splay(x);t[x].fa = f;}

	return;

}

void cut(int x,int f)

{

	if(pos[x] == f)pos[x] = 0;

	else

	{

		int rt = find(x);

		access(x);splay(x);t[x].c[0] = t[t[x].c[0]].fa = 0;

		if(pos[rt] != 0 && find(pos[rt]) == x)

		{

			link(rt,pos[rt]);

			pos[rt] = 0;

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)t[i].siz = 1;

	for(int i = 1;i <= n;++i)if(i + a[i] >= 1 && i + a[i] <= n)link(i,i + a[i]);

	int opt,x,y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d",&x);

			access(x);int rt = find(x);

			if(pos[rt] != 0)puts("-1");

			else{splay(x);printf("%d\n",t[x].siz);}

		}

		else

		{

			scanf("%d%d",&x,&y);

			if(x + a[x] >= 1 && x + a[x] <= n)cut(x,x + a[x]);

			if(x + y >= 1 && x + y <= n)link(x,x + y);

			a[x] = y;

		}

	}

	return 0;

}