BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊

题目大意

给你一个序列，每个点有一个属性$k_i$，表示如果绵羊在第$i$个点就会被弹到$i+k_i$号点。如果$i+k_i \gt n$就会视为绵羊被弹了出去。每次求把绵羊从$i$弹飞的最少步数或者修改一个点的$k$值。

分块或者LCT均可做。

对于LCT做法，直接进行Cut和Link操作，查询时查询到根的路径即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,fa[200010],c[200010][2],v[200010],a[200010];
bool rev[200010];
inline bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
void pushup(int pos)
{
	v[pos]=v[c[pos][0]]+v[c[pos][1]]+1;
}
void pushdown(int x)
{
	if(rev[x])
	{
		rev[c[x][0]]^=1,rev[c[x][1]]^=1,rev[x]^=1;
		swap(c[c[x][0]][0],c[c[x][0]][1]);
		swap(c[c[x][1]][0],c[c[x][1]][1]);
	}
}
void init(int x)
{
	if(!isroot(x)) init(fa[x]);
	pushdown(x);
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
	if(!isroot(y)) c[z][c[z][1]==y]=x;
	fa[x]=z,fa[y]=x;
	fa[c[x][r]]=y,c[y][l]=c[x][r],c[x][r]=y;
	pushup(y),pushup(x);
}
void splay(int x)
{
	init(x);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if((c[y][1]==x)^(c[z][1]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	int tmp=0;
	while(x)
	{
		splay(x);
		c[x][1]=tmp;
		pushup(x);
		tmp=x,x=fa[x];
	}
}
void chroot(int x)
{
	access(x),splay(x);
	swap(c[x][0],c[x][1]);
	rev[x]^=1;
}
void cut(int x,int y)
{
	chroot(x),access(y),splay(y);
	c[y][0]=fa[x]=0;
}
void link(int x,int y)
{
	chroot(x),fa[x]=y;
}
void modify()
{
	int x,y;
	scanf("%d%d",&x,&y),x++,y=min(n+1,x+y);
	cut(x,a[x]),link(x,y);
	a[x]=y;
}
int query()
{
	int x;
	scanf("%d",&x),x++,chroot(x),access(n+1),splay(n+1);
	return v[n+1];
}
int main()
{
	int md,tmp;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",a+i),a[i]=min(n+1,i+a[i]),link(i,a[i]);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&md);
		switch(md)
		{
			case 1:printf("%d\n",query()-1);break;
			case 2:modify();break;
		}
	}
	return 0;
}