【HNOI2010】弹飞绵羊 - LCT

题目描述

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

思路

LCT模板题，把这n个装置看作n+1个节点，

n+1为虚拟节点，到达这个点即被弹飞，初

始时对每个节点进行link(i,i+k[i])，修改时先

cut(i,i+k[i])，再link(i,i+K)，并让k[i] = K

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200000 + 10;

struct Link_Cut_Tree {

    struct Splay { int ch[2],f,mark,sum,w; }t[maxn];

    inline bool getfa(int x) { return t[t[x].f].ch[1] == x; }

    inline bool isroot(int x) { return t[t[x].f].ch[0] != x && t[t[x].f].ch[1] != x; }

    inline void pushup(int x) { t[x].sum = t[t[x].ch[0]].sum+t[t[x].ch[1]].sum+t[x].w; }

    inline void rev(int x) { t[x].mark ^= 1; swap(t[x].ch[0],t[x].ch[1]); }

    inline void pushdown(int x) {

        if (t[x].mark) {

            if (t[x].ch[0]) rev(t[x].ch[0]);

            if (t[x].ch[1]) rev(t[x].ch[1]);

            t[x].mark = 0;

        }

    }

    inline void rotate(int x) {

        int f = t[x].f,g = t[f].f,c = getfa(x);

        if (!isroot(f)) t[g].ch[getfa(f)]=x; t[x].f = g;

        t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].f = f;

        t[x].ch[c^1] = f; t[f].f = x;

        pushup(f); pushup(x);

    }

    inline void check(int x) { if (!isroot(x)) check(t[x].f); pushdown(x); }

    inline void splay(int x) {

        check(x);

        for (;!isroot(x);rotate(x))

            if (!isroot(t[x].f)) rotate(getfa(t[x].f) == getfa(x) ? t[x].f : x);

    }

    inline void access(int x) { for (int y = 0;x;y = x,x = t[x].f) splay(x),t[x].ch[1] = y,pushup(x); }

    inline void makeroot(int x) { access(x); splay(x); rev(x); }

    inline int findroot(int x) {

        access(x); splay(x);

        while (t[x].ch[0]) pushdown(x),x = t[x].ch[0];

        return x;

    }

    inline void link(int x,int y) { makeroot(x),t[x].f = y; }

    inline void cut(int x,int y) { makeroot(x); access(y); splay(y); if (t[y].ch[0] == x && t[x].ch[1] == 0) t[x].f = t[y].ch[0] = 0; }

    inline void split(int x,int y) { makeroot(x); access(y); splay(y); }

}lct;

int n,q,k[maxn];

int main() {

    scanf("%d",&n);

    for (int i = 1;i <= n+1;i++) lct.t[i].w = 1;

    for (int i = 1;i <= n;i++) {

        scanf("%d",&k[i]);

        lct.link(i,k[i]+i <= n ? k[i]+i : n+1);

    }

    scanf("%d",&q);

    while (q--) {

        int op,x,y;

        scanf("%d%d",&op,&x);

        x++;

        if (op == 1) lct.split(x,n+1),printf("%d\n",lct.t[n+1].sum-1);

        else {

            scanf("%d",&y);

            lct.cut(x,k[x]+x <= n ? k[x]+x: n+1);

            lct.link(x,y+x <= n ? y+x : n+1);

            k[x] = y;

        }

    }

    return 0;

}