LCT複習之 bzoj 2002: [Hnoi2010]Bounce 彈飛綿羊

題意

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

題解

以前用分塊做過一次，當時還是自己想出來分塊的做法呢！

但是，今天，我學會了LCT

于是我把這題又做了一次

做法也很簡單

如果我們把終點看成一個節點，假設是n+1吧

然後每個點和他能到達的點相連

不難發現，這是一顆以n+1為根的有根樹

答案就是這個點到根的路徑有多少個節點

LCT維護即可

注意查詢答案的時候，人為地把n+1變回根就可以了

稍微地比分塊快一點點啊

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
int n,m;
int a[N];
struct qq
{
    int c,fa,son[2];
    bool rev;
}tr[N];
bool is_root (int x)
{
    int fa=tr[x].fa;
    if (tr[fa].son[]==x) return false;
    if (tr[fa].son[]==x) return false;
    return true;
}
void push_down (int x)
{
    if (!tr[x].rev) return ;
    int s1=tr[x].son[],s2=tr[x].son[];
    swap(tr[x].son[],tr[x].son[]);
    tr[s1].rev^=;tr[s2].rev^=;tr[x].rev^=;
}
void pre (int x)
{
    if (!is_root(x)) pre(tr[x].fa);
    push_down(x);
}
void update (int now)
{
    int s1=tr[now].son[],s2=tr[now].son[];
    tr[now].c=+tr[s1].c+tr[s2].c;
}
void rotate (int x)
{
    int y=tr[x].fa,z=tr[y].fa,r,R;
    int w=(tr[y].son[]==x);

    r=tr[x].son[w];R=y;
    tr[R].son[-w]=r;
    if (r!=) tr[r].fa=R;

    r=x;R=z;
    if (!is_root(y))
    {
        if (tr[R].son[]==y) tr[R].son[]=r;
        else tr[R].son[]=r;
    }
    tr[r].fa=R;

    r=y;R=x;
    tr[R].son[w]=r;
    tr[r].fa=R;

    update(y);update(x);
}
void splay (int x)//使得x成為所在splay的根 
{
    pre(x);
    while (!is_root(x))
    {
        int y=tr[x].fa,z=tr[y].fa;
        if (!is_root(y))
        {
            if ((tr[z].son[]==y)==(tr[y].son[]==x)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
void access (int x)//使得x成為偏愛路徑 
{
    int last=;
    while (x!=)
    {
        splay(x);
        tr[x].son[]=last;
        update(x);
        last=x;
        x=tr[x].fa;
    }
}
void make_root (int x)//使得x成為所在樹的跟 
{
    access(x);splay(x);tr[x].rev^=;
}
void link (int x,int y)//連接配接這兩個點 注意，原來是x跳到y的，是以，y的深度比x小 
{
    if (y>n) y=n+;
    make_root(x);tr[x].fa=y;
}
void split (int x,int y)//分離這兩個點的路徑，y當根 
{
    make_root(x);
    access(y);
    splay(y);
}
void cut (int x,int y) 
{
    if (y>n) y=n+;
    split(x,y);
    tr[y].son[]=tr[x].fa=;
    update(y);
}
int solve (int x)
{
    make_root(n+);
    access(x);splay(x);
    return tr[x].c;
}
int main()
{
    scanf("%d",&n);
    tr[n+].c=;tr[n+].rev=false;
    for (int u=;u<=n;u++)  
    {
        scanf("%d",&a[u]);
        tr[u].c=;tr[u].rev=false;
    }
    for (int u=n;u>=;u--)
        link(u,u+a[u]);
    scanf("%d",&m);
    for (int u=;u<=m;u++)
    {
        int op;
        scanf("%d",&op);
        if (op==)
        {
            int x;
            scanf("%d",&x);x++;
            printf("%d\n",solve(x)-);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);x++;
            cut(x,x+a[x]);
            a[x]=y;
            link(x,x+a[x]);
        }
    }
    return ;
}