bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊

LCT练习

Description

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

Sample Input

1 2 1 1

1 1

2 1 1

1 1

Sample Output

板子题

对于所有的点，向它能跳到的点连边，假如弹飞就连到n+1，最后就形成一个动态树。

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

2操作，把原来的边cut，link一下新边。

#include <cstdio>
#define N 200010
using namespace std;
#define read(a) a=getnum()
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()
{
    read(n);
    for (int i=1;i<=n;i++)
        read(k[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;
    read(m);
    for (int i=1;i<=m;++i)
    {
        read(com);
    read(x),x++;
        if (com==1)
        {
            make_root(n+1);
            access(x);
            splay(x);
            printf("%d\n",siz[ch[x][0]]);
    }
    if (com==2)
    {
        read(y);
        cut(x,to[x]);
        if (x+y<=n)
            to[x]=x+y;
        else
            to[x]=n+1;
        link(x,to[x]);
    }
    }
}