BZOJ 題目2002: [Hnoi2010]Bounce 彈飛綿羊（link cut tree）

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

Sample Output

HINT

Source

Splay 啟發式合並

ac代碼

/**************************************************************
    Problem: 2002
    User: kxh1995
    Language: C++
    Result: Accepted
    Time:1912 ms
    Memory:6280 kb
****************************************************************/
 
#include   
#include   
struct LCT  
{  
    int bef[200050],pre[200050],next[200050][2],sum[200050],key[200050];  
    void init()  
    {  
        memset(pre,0,sizeof(pre));  
        memset(next,0,sizeof(next));  
    }
    void pushup(int x)
    {
        sum[x]=key[x]+sum[next[x][1]]+sum[next[x][0]];
    }
    void rotate(int x,int kind)  
    {  
        int y,z;  
        y=pre[x];  
        z=pre[y];  
        next[y][!kind]=next[x][kind];  
        pre[next[x][kind]]=y;  
        next[z][next[z][1]==y]=x;  
        pre[x]=z;  
        next[x][kind]=y;  
        pre[y]=x;  
        pushup(y);
    }  
    void splay(int x)  
    {  
        int rt;  
        for(rt=x;pre[rt];rt=pre[rt]);  
        if(x!=rt)  
        {  
            bef[x]=bef[rt];  
            bef[rt]=0;  
            while(pre[x])  
            {  
                if(next[pre[x]][0]==x)  
                {  
                    rotate(x,1);  
                }  
                else 
                    rotate(x,0);  
            } 
            pushup(x);
        }  
    }  
    void access(int x)  
    {  
        int fa;  
        for(fa=0;x;x=bef[x])  
        {  
            splay(x);  
            pre[next[x][1]]=0;  
            bef[next[x][1]]=x;  
            next[x][1]=fa;  
            pre[fa]=x;  
            bef[fa]=0;  
            fa=x;
            pushup(x);
        }  
    }  
    int query(int x)  
    {  
        access(x);  
        splay(x);  
        // while(next[x][0])  
        //   x=next[x][0];  
        return sum[next[x][0]];  
    }  
    void cut(int x)  
    {  
        access(x);  
        splay(x);  
        bef[next[x][0]]=bef[x];  
        bef[x]=0;  
        pre[next[x][0]]=0;  
        next[x][0]=0;  
    }  
    void join(int x,int y)  
    {  
        if(y==0)  
            cut(x);  
        else 
        {  
            int tmp;  
            access(y);  
            splay(y);  
            for(tmp=x;pre[tmp];tmp=pre[tmp]);  
            if(tmp!=y)  
            {  
                cut(x);  
                bef[x]=y;  
            }  
        }  
    }  
   
}lct;
int a[200020];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        lct.init();
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]+i>n)
                lct.bef[i]=0;
            else
                lct.bef[i]=a[i]+i;
            lct.key[i]=lct.sum[i]=1;
        }
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int op;
            scanf("%d",&op);
            if(op==1)
            {
                int x;
                scanf("%d",&x);
                printf("%d\n",lct.query(x+1)+1);
            }
            else
            {
                int x,y;
                scanf("%d%d",&x,&y);
                x++;
                a[x]=y;
                if(x+y>n)
                    //lct.bef[x]=0;
                    y=0;
                else
                    //lct.join(x,y+x);
                    y=y+x;
                lct.join(x,y);
            }
        }
    }
}

版權聲明：本文為博主原創文章，未經博主允許不得轉載。