BZOJ2002 [HNOI2010] 弹飞绵羊

LCT access完了一定splay再用！！！

悲伤= =

LCT裸题 把调出去设虚点n+1即可

//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200010
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define fa(x) t[x].fa
#define nroot(x) (ls(fa(x))==x||rs(fa(x))==x)
using namespace std;

struct node
{
	int sz,fa,son[2]; bool rev;
}t[N];

void pushup(int x)
{
	t[x].sz = t[ls(x)].sz + t[rs(x)].sz + 1;
}

void rotate(int x)
{
	if(!x||!nroot(x))	return;
	int f = fa(x),gf = fa(f);
	int k = (rs(f) == x), p = k^1;
	if(nroot(f))	t[gf].son[rs(gf)==f] = x;
	t[x].fa = gf; t[f].fa = x;
	if(t[x].son[p])	t[t[x].son[p]].fa = f;
	t[f].son[k] = t[x].son[p];
	t[x].son[p] = f;
	pushup(f); pushup(x);
}

void pushdown(int x)
{
	if(!x || !t[x].rev)	return;
	swap(ls(x),rs(x));
	if(ls(x))	t[ls(x)].rev^=1;
	if(rs(x))	t[rs(x)].rev^=1;
	t[x].rev^=1;
}

void push(int x)
{
	if(nroot(x))	push(fa(x));
	pushdown(x);
}

void splay(int x)
{
	push(x);
	while(nroot(x))
	{
		int f = fa(x), gf = fa(f);
		if(nroot(gf))
			(rs(f)==x)^(rs(gf)==f)?rotate(x):rotate(f);
		rotate(x);
	}
	pushup(x);
}

void access(int x)
{
	int y = 0;
	do
	{
		//printf("%d
",x);
		splay(x);
		t[x].son[1] = y;
		pushup(x);
		y = x; x = t[x].fa;
	}while(x);
}

void makeroot(int x)
{
	access(x); splay(x); t[x].rev=1;// pushdown(x);
}

void link(int x,int y)
{
	makeroot(x); t[x].fa = y;
}

void cut(int x,int y)
{
	makeroot(y); access(x); splay(x);
	//printf("%d %d
",t[y].sz,rs(y));
	if(t[x].sz == 2 && ls(x) == y)
		t[x].son[0] = 0, t[y].fa = 0,pushup(x);
}
int k[N];
int main()
{
	int n,x,y,opt,m;
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)	t[i].sz=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&k[i]);
		if(i+k[i]>n)	link(i,n+1);
		else	link(i,i+k[i]);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&opt,&x);
		//for(int j=1;j<=n+1;j++)
		//	printf("%d ",t[j].fa);
		//printf("
");
		x++;
		if(opt==1)
		{
			makeroot(n+1);
			//printf("MMP
");
			//for(int j=1;j<=n+1;j++)
			//	printf("%d ",t[j].fa);
			access(x); splay(x);
			//printf("%d %d
",ls(5),rs(5));
			printf("%d
",t[x].sz-1);
		}
		else
		{
			scanf("%d",&y);
			cut(x,x+k[x]>n?n+1:x+k[x]);
			k[x] = y;
			link(x,x+k[x]>n?n+1:x+k[x]);
		}
	}
	return 0;
}