BZOJ2438: [Hnoi2010]Bounce 弹飞绵羊

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2002

Solution

LCT模板题
每个点和弹出去的点连边（弹飞的连向同一个点T，显然它是根），建一棵LCT。
如果询问为x，那么答案为x的深度
改变弹力则切断原来的边，连上新的边
这些都可以用LCT维护。

Solution

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 200005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
inline void writeln(ll x){
    write(x); putchar('\n');
}
ll fa[N],left[N],right[N],rev[N],size[N],q[N],now[N];
ll n,m,top,opt,x,y;
bool isroot(ll x){
    return (left[fa[x]]!=x)&&(right[fa[x]]!=x);
}
void pushdown(ll x){
    if (rev[x]){
        rev[x]^=1; rev[left[x]]^=1; rev[right[x]]^=1;
        swap(left[x],right[x]);
    }
}
void updata(ll x){
    size[x]=size[left[x]]+size[right[x]]+1;
}
void rotate(ll x){
    ll y=fa[x],z=fa[y],flag=left[y]==x;
    if (!isroot(y)) if (left[z]==y) left[z]=x; else right[z]=x;
    fa[y]=x; fa[x]=z;
    if (flag) fa[left[y]=right[x]]=right[x]=y;
    else fa[right[y]=left[x]]=left[x]=y;
    updata(y); updata(x);
}
void splay(ll x){
    q[++top]=x;
    for (ll i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
    while (top) pushdown(q[top--]);
    while (!isroot(x)){
        ll y=fa[x],z=fa[y];
        if (!isroot(y)) if (left[z]==y^left[y]==x) rotate(x);
                        else rotate(y);
        rotate(x);
    }
}
void access(ll x){
    for (ll y=0;x;y=x,x=fa[x])
        splay(x),right[x]=y,updata(x);
}
void makeroot(ll x){
    access(x); splay(x); rev[x]^=1;
}
void link(ll x,ll y){
    makeroot(x); fa[x]=y; splay(x);
}
void cut(ll x,ll y){
    makeroot(x); access(y); splay(y); left[y]=fa[x]=0;
}
ll query(ll x){
    makeroot(n+1); access(x); splay(x);
    return size[left[x]];
}
int main(){
    n=read();
    for (ll i=1;i<=n;i++){
        size[i]=1;
        now[i]=fa[i]=min(i+read(),n+1);
    }
    m=read(); size[n+1]=1;
    for (ll i=1;i<=m;i++){
        opt=read();
        if (opt==1) writeln(query(read()+1));
        else {
            x=read(); x++; y=read();
            cut(x,now[x]);
            link(x,now[x]=min(n+1,x+y));
        }
    }
}