题解 洛谷P3203/BZOJ2002【[HNOI2010]弹飞绵羊】

裸的LCT，关键是要怎么连边，怎么将这种弹飞关系转化成连边就行了。

那么我们可以这样连边：

• 一个节点i的爸爸就是i+ki。

• 没有i+ki那么就被弹飞了，即\(i\)的爸爸是虚拟节点n+1。

那么怎么求次数呢？

• i的深度就是次数

对于求深度，我们可以先将x弄成root，然后通过Access(n+1)将n+1号节点和x节点丢到一个Splay里面，维护一个size，每次询问的answer就是已经Splay到根的n+1号节点的size了。

Code:

#include<bits/stdc++.h>

#define ll long long

#define inf 0x3f3f3f3f

#define RI register int

using namespace std;

const int N=2e5+2;

template <typename Tp> inline void IN(Tp &x){

    int f=1;x=0;char ch=getchar();

    while(ch<'0'||ch>'9')if(ch=='-')f=-1,ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();x*=f;

}int f[N],s[N],r[N],val[N],hep[N],ch[N][2];

inline int get(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}

inline void pushup(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+1;}

inline void pushdown(int x){

	if(!r[x])return;r[x]=0;

	swap(ch[x][0],ch[x][1]);

	if(ch[x][0])r[ch[x][0]]^=1;

	if(ch[x][1])r[ch[x][1]]^=1;

}

inline void rotate(int x){

	int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k];

	if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;

	if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);

}

inline void Splay(int x){

	int y=x,top=0;hep[++top]=y;

	while(get(y))hep[++top]=y=f[y];

	while(top)pushdown(hep[top--]);

	while(get(x)){

		y=f[x],top=f[y];

		if(get(y))

		  rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);

		rotate(x);

	}pushup(x);return;

}

inline void Access(int x){

	for(register int y=0;x;x=f[y=x])

	   Splay(x),ch[x][1]=y,pushup(x);

}

inline int findroot(int x){

	Access(x);Splay(x);

	while(ch[x][0])pushdown(x),x=ch[x][0];

	return x;

}

inline void makeroot(int x){Access(x);Splay(x);r[x]^=1;}

inline void split(int x,int y){makeroot(x);Access(y);Splay(y);}

inline void link(int x,int y){makeroot(x);if(findroot(y)!=x)f[x]=y;}

inline void cut(int x,int y){

	split(x,y);if(findroot(y)==x&&f[x]==y&&!ch[x][1])

	{f[x]=ch[y][0]=0;pushup(y);}return;

}int n,m;

int main(){

	scanf("%d",&n);

	for(register int i=1;i<=n+1;++i)s[i]=1;

	for(register int x,i=1;i<=n;++i){

	    scanf("%d",&x);val[i]=x;

	    link(i,(i+x<=n)?i+x:n+1);

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

    for(register int op,x,y,i=1;i<=m;++i){

    	scanf("%d%d",&op,&x);++x;

    	if(op==1){

    		makeroot(x);Access(n+1);Splay(n+1);

			printf("%d\n",s[n+1]-1);

    	}else if(op==2){

    		scanf("%d\n",&y);

    		cut(x,(x+val[x]<=n)?x+val[x]:n+1);

    		link(x,(x+y<=n)?x+y:n+1);val[x]=y;

    	}

    }return 0;

}

所以就没了。