BZOJ2002 洛谷3203 HNOI2010 彈飛綿羊LCT

題目描述

某天，Lostmonkey發明了一種超級彈力裝置，為了在他的綿羊朋友面前顯擺，他邀請小綿羊一起玩個遊戲。遊戲一開始，Lostmonkey在地上沿着一條直線擺上n個裝置，每個裝置設定初始彈力系數ki，當綿羊達到第i個裝置時，它會往後彈ki步，達到第i+ki個裝置，若不存在第i+ki個裝置，則綿羊被彈飛。綿羊想知道當它從第i個裝置起步時，被彈幾次後會被彈飛。為了使得遊戲更有趣，Lostmonkey可以修改某個彈力裝置的彈力系數，任何時候彈力系數均為正整數。

題解： LCT。我們把每個點向它跳到的點連邊，如果超過了n，就不連了，修改的話可以寫link和cut，但是我寫了一種許多原本LCT需要的函數都沒寫的寫法，這個的link和cut可以直接改。 講解一下核心代碼吧。 核心代碼是access(x);splay(x); 這個東西就是你把x到根的路徑連通，之後再把x旋轉到根，這樣原來x與兒子連的邊變成了輕邊，不會被統計，所有原來比x深度小的點都到了x的左子樹中，而此時x所在的子樹大小就是步數。 代碼如下：

#include <bits/stdc++.h>
using namespace std;

int n,m,a,s[200001],f[200001],c[200001][2],rev[200001];
int nroot(int x)
{
    return c[f[x]][0]==x||c[f[x]][1]==x;
}
void pushup(int x)
{
    s[x]=s[c[x][1]]+s[c[x][0]]+1;
}
void rotate(int x)
{
    int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
    if(nroot(y))
    c[z][c[z][1]==y]=x;
    c[x][!k]=y;
    c[y][k]=w;
    if(w)
    f[w]=y;
    f[x]=z;
    f[y]=x;
    pushup(y);
}
void splay(int x)
{
    int y,z;
    while(nroot(x))
    {
        y=f[x];
        z=f[y];
        if(nroot(y))
        {
            if(c[y][0]==x ^ c[z][0]==y)
            rotate(y);
            else
            rotate(x);
        }
        rotate(x);
    }
    pushup(x);
}
void access(int x)
{
    int y=0;
    while(x!=0)
    {
        splay(x);
        c[x][1]=y;
        pushup(x);
        if(y!=0)
        f[y]=x;
        y=x;
        x=f[x];
    }
} 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        s[i]=1;
        if(a+i<=n)
        f[i]=a+i;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d",&y);
            ++y;
            access(y);
            splay(y);
            printf("%d\n",s[y]);
        }
        if(x==2)
        {
            scanf("%d%d",&y,&z);
            ++y;
            access(y);
            splay(y);
            c[y][0]=f[c[y][0]]=0;
            if(y+z<=n)
            f[y]=y+z;
        }
    }
    return 0;
}