bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊

LCT练习

Description

Input

Output

Sample Input

4

1 2 1 1

3

1 1

2 1 1

1 1

Sample Output

2

3

1操作，先把n+1放到根的位置，然后access、splay那个点，因为能跳到这个点的点深度都比它低，所以splay到根以后直接输出左子树的siz

#include <cstdio>
#define N 200010
using namespace std;
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
int n,m,x,y,com,f[N],ch[N][2],siz[N],res[N],k[N],to[N];
void swap(int &a,int &b){int t=a;a=b;b=t;}
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
void pushdown(int x)
{
if (res[x] && x)
{
if (ch[x][0]) res[ch[x][0]]^=1;
if (ch[x][1]) res[ch[x][1]]^=1;
swap(ch[x][1],ch[x][0]);
res[x]=0;
}
}
int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
int get_son(int x){return ch[f[x]][1]==x;}
void rot(int x)
{
int fa=f[x],fafa=f[fa],k=get_son(x);
if (!is_root(fa))
ch[fafa][ch[fafa][1]==fa]=x;
ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
ch[x][k^1]=fa,f[fa]=x;
f[x]=fafa;
update(fa);update(x);
}
void push(int x)
{
if(!is_root(x)) push(f[x]);
pushdown(x);
}
void splay(int x)
{
push(x);
for (int fa;!is_root(x);rot(x))
if (!is_root(fa=f[x]))
rot(get_son(x)==get_son(fa)?fa:x);
}
void access(int x)
{
for (int y=0;x;y=x,x=f[x])
splay(x),ch[x][1]=y;
}
int find_root(int x)
{
access(x),splay(x);
while(ch[x][0])
x=ch[x][0];
return x;
}
void make_root(int x){access(x),splay(x),res[x]^=1;}
void link(int x,int y){make_root(x),f[x]=y,splay(x);}
void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;}
main()
{
for (int i=1;i<=n;i++)
for (int i=1;i<=n;i++)
{
if (i+k[i]<=n)
to[i]=i+k[i];
else
to[i]=n+1;
f[i]=to[i];
siz[i]=1;
}
siz[n+1]=1;
for (int i=1;i<=m;++i)
{
if (com==1)
{
make_root(n+1);
access(x);
splay(x);
printf("%d\n",siz[ch[x][0]]);
}
if (com==2)
{
}