bzoj-2002 Bounce 彈飛綿羊

題意：

直線上有一排n個彈力裝置，每個彈力裝置會将綿羊彈到下ki個彈力裝置處；

如果沒有了則綿羊被彈飛。。

問每個綿羊被彈了幾次彈飛；

可能會修改彈力裝置的k值；

n<=200000，m<=100000；

題解：

裸的LCT吧；

是以下面的啟發式合并Splay是啥鬼；

有人說這題邊有向，和無向邊不一樣；

然而有個卵差別，把終點作為根不就有向了嗎！

反正切了上一題這一題也不難吧；

維護個size之後，把終點作為根再access(x)；

這時的Splay就是x彈飛的路線啦，Splay(x)之後x的左子樹大小就是答案咯；

其實也是整棵Splay的大小-1，因為x的重兒子在access時砍掉了嘛；

LCT是啥啥的還是戳上一篇。。

代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 210000
#define which(x) (ch[fa[x]][1]==x)
using namespace std;
int fa[N],ch[N][2],size[N],to[N],root;
bool rt[N],cov[N];
void Pushup(int x)
{
	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void reverse(int x)
{
	swap(ch[x][0],ch[x][1]);
	cov[x]^=1;
}
void Pushdown(int x)
{
	if(cov[x])
	{
		reverse(ch[x][0]);
		reverse(ch[x][1]);
		cov[x]=0;
	}
}
void down(int x)
{
	if(!rt[x])	down(fa[x]);
	Pushdown(x);
}
void Rotate(int x)
{
	int f=fa[x];
	bool k=which(x);
	if(rt[f])	rt[f]^=rt[x]^=1;
	else		ch[fa[f]][which(f)]=x;
	ch[f][k]=ch[x][!k];
	ch[x][!k]=f;
	fa[ch[f][k]]=f;
	fa[x]=fa[f];
	fa[f]=x;
	size[x]=size[f];
	Pushup(f);
}
void Splay(int x)
{
	down(x);
	while(!rt[x])
	{
		int f=fa[x];
		if(rt[f])
		{
			Rotate(x);
			return ;
		}
		if(which(x)^which(f))
			Rotate(x);
		else
			Rotate(f);
		Rotate(x);
	}
}
void access(int x)
{
	int y=0;
	while(x)
	{
		Splay(x);
		rt[ch[x][1]]=1;
		rt[y]=0;
		ch[x][1]=y;
		Pushup(x);
		y=x,x=fa[x];
	}
}
void Mtr(int x)
{
	access(x);
	Splay(x);
	reverse(x);
}
void Link(int x,int y)
{
	Mtr(x);
	fa[x]=y;
}
void Cut(int x,int y)
{
	Mtr(x);
	access(y);
	Splay(x);
	ch[x][1]=0,fa[y]=0;
	rt[y]=1;
	Pushup(x);
}
int Query(int x)
{
	Mtr(root);
	access(x);
	Splay(x);
	return size[ch[x][0]];
}
int main()
{
	int n,m,i,j,k,x,y,op;
	scanf("%d",&n);
	root=n+1;
	for(i=1;i<=n+1;i++)
		rt[i]=1,size[i]=1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);
		to[i]=min(i+k,root);
		Link(i,to[i]);
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d",&x),x++;
			printf("%d\n",Query(x));
		}
		else
		{
			scanf("%d%d",&x,&k),x++;
			Cut(x,to[x]);
			to[x]=min(x+k,root);
			Link(x,to[x]);
		}
	}
	return 0;
}