BZOJ2002弹飞绵羊

动态树LCT模板题

#include<cstdio>

#include<cctype>

#include<algorithm>

using namespace std;

inline int read()

{

    int x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

inline void println(int x)

{

    if(x < 0)

        putchar('-');

    if(x == 0)

        putchar('0');

    int top = 0, ans[10 + (1 << 4)];

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const int MAXN = (int)2e5 + (1 << 5);

struct node

{

    int isroot, ch[2], fa, size;

}T[MAXN];

void update(int u)

{

    T[u].size = ((T[u].ch[0] == - 1) ? 0 : T[T[u].ch[0]].size)

        + ((T[u].ch[1] == - 1) ? 0 : T[T[u].ch[1]].size) + 1;

}

inline int get_rela(int u)

{

    return u == T[T[u].fa].ch[1];

}

void rotate(int u)

{

    int fa = T[u].fa, fafa = T[T[u].fa].fa, rela = get_rela(u);

    T[T[u].ch[rela ^ 1]].fa = fa;

    T[fa].ch[rela] = T[u].ch[rela ^ 1];

    T[u].ch[rela ^ 1] = fa;

    T[fa].fa = u;

    T[u].fa = fafa;

    if(T[fa].isroot)

        T[fa].isroot = 0, T[u].isroot = 1;

    else

        T[fafa].ch[T[fafa].ch[1] == fa] = u;

    update(fa), update(u);

}

void splay(int u)

{

    while(1)

    {

        if(T[u].isroot)

            break;

        if(! T[T[u].fa].isroot)

            rotate((get_rela(u) == get_rela(T[u].fa)) ? T[u].fa : u);

        rotate(u);

    }

}

void access(int u)

{

    splay(u);

    while(T[u].fa != - 1)

    {

        int fa = T[u].fa;

        splay(fa);

        if(T[fa].ch[1] != - 1)

            T[T[fa].ch[1]].isroot = 1;

        T[u].isroot = 0;

        T[fa].ch[1] = u;

        update(fa);

        splay(u);

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("BZOJ2002.in", "r", stdin);

    freopen("BZOJ2002.out", "w", stdout);

    #endif

    int n = read();

    T[n].fa = - 1;

    for(int i = 0; i < n; i ++)

        T[i].fa = min(read() + i, n);

    for(int i = 0; i <= n; i ++)

        T[i].size = 1, T[i].isroot = 1, T[i].ch[0] = T[i].ch[1] = - 1;

    int m = read();

    for(int i = 0; i < m; i ++)

    {

        int opt = read();

        if(opt == 1)

        {

            int u = read();

            access(u);

            println(T[T[u].ch[0]].size);    //这里要稍微注意一下

            continue;

        }

        int u = read();

        splay(u);

        T[T[u].ch[0]].fa = T[u].fa;

        T[T[u].ch[0]].isroot = 1;

        T[u].ch[0] = - 1;

        T[u].size = ((T[u].ch[1] == - 1) ? 0 : T[T[u].ch[1]].size) + 1;

        T[u].fa = min(n, read() + u);

    }

}