一个 LCT

Description

游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$个装置，若不存在这个装置，则绵羊被弹飞。

绵羊想知道当它从第 $i$​ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数。任何时候弹力系数均为正整数。

Solution1

我们让每个装置向弹射到的地方连一个边，那么答案就是这个点到根的路径的长度。

因为要加边、删边且一直是一棵树，我们使用 LCT 维护。

具体怎么维护呢？

我们发现，我们不需要把一段路径单独拎出来处理，只需要查询一个点到这个辅助树对应的原树上的根的距离即可。

并且不能随便换原树的根。

那好办了，回想一下我们为什么要换根：因为 $access$ 只能打通一个点到根的路径，所以当我们想查询一条路径的时候需要换根，但这个题根是固定的，不需要这么做。

当查询点 $x$ 的时候，我们直接 $access(x),splay(x)$，然后答案就是 $siz(x)$。

加边怎么办呢？我们直接 $access(x),splay(x)$，然后连一条虚边即可（实链剖分的灵活性体现出来了，这个虚边就有一点有向边的意思在里面）。

删边怎么办呢？也是一样的。

发现我们实际上少写了很多函数，代码又简洁常数又小。

Code1

#include <algorithm>
#include <cstdio>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

struct LCT
{
    int ch[maxn][2], rev[maxn], father[maxn], ans[maxn], val[maxn], siz[maxn];
    inline int &ls(int x) { return ch[x][0]; }
    inline int &rs(int x) { return ch[x][1]; }
    inline bool get(int x) { return x == rs(father[x]); }
    inline bool isroot(int x) { return x != ch[father[x]][0] && x != ch[father[x]][1]; }
    inline void push_up(int x) { siz[x] = siz[ls(x)] + siz[rs(x)] + 1; }
    inline void push_down(int x)
    {
        if (!rev[x])
            return;
        if (ls(x))
            std::swap(ls(ls(x)), rs(ls(x))), rev[ls(x)] ^= 1;
        if (rs(x))
            std::swap(ls(rs(x)), rs(rs(x))), rev[rs(x)] ^= 1;
        rev[x] = 0;
    }
    inline void update(int x)
    {
        if (!isroot(x))
            update(father[x]);
        push_down(x);
    }
    inline void rotate(int x)
    {
        int y = father[x], z = father[y], d = get(x);
        if (!isroot(y))
            ch[z][y == ch[z][1]] = x;
        ch[y][d] = ch[x][d ^ 1];
        if (ch[x][d ^ 1])
            father[ch[x][d ^ 1]] = y;
        ch[x][d ^ 1] = y, father[y] = x, father[x] = z;
        push_up(y), push_up(x);
    }
    inline void splay(int x)
    {
        update(x);
        for (int f; f = father[x], !isroot(x); rotate(x))
            if (!isroot(f))
                rotate(get(x) == get(f) ? f : x);
    }
    inline int access(int x)
    {
        int p = 0;
        for (; x; p = x, x = father[x])
            splay(x), rs(x) = p, push_up(x);
        return p;
    }
} lct;

int p[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (i + x > n)
            continue;
        else
            lct.father[i] = i + x;
    }
    cin >> m;
    while (m--)
    {
        int pos, x;
        cin >> pos >> x;
        x++;
        if (pos == 1)
        {
            lct.access(x), lct.splay(x);
            cout << lct.siz[x] << endl;
        }
        else
        {
            int k;
            cin >> k;
            lct.access(x), lct.splay(x);
            lct.ls(x) = lct.father[lct.ls(x)] = 0;
            if (x + k <= n)
                lct.father[x] = x + k;
            lct.push_up(x);
        }
    }
}

Solution2

很无脑的一个做法，我不喜欢，但有必要学。

建一个超级源点 $n+1$，弹射出去的时候在这个点和超级源点之间建边，查询的时候用 $link(x,n+1)$​ ，然后答案是 $siz(n+1)-1$。

优点：高度模块化，比较无脑。

缺点：我不喜欢，且代码长，常数大。

Code2

我的实现很丑，看个乐。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define mem(x) memset(x, 0, sizeof(x))
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

inline int read()
{
    char ch = getchar();
    int x = 0;
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}

struct LCT
{
    int ch[maxn][2], rev[maxn], father[maxn], siz[maxn], val[maxn];
    inline int &ls(int x) { return ch[x][0]; }
    inline int &rs(int x) { return ch[x][1]; }
    inline bool get(int x) { return x == rs(father[x]); }
    inline bool isroot(int x) { return x != ch[father[x]][0] && x != ch[father[x]][1]; }
    inline void push_up(int x) { siz[x] = siz[ls(x)] + siz[rs(x)] + 1; }
    inline void push_down(int x)
    {
        if (!rev[x])
            return;
        if (ls(x))
            std::swap(ls(ls(x)), rs(ls(x))), rev[ls(x)] ^= 1;
        if (rs(x))
            std::swap(ls(rs(x)), rs(rs(x))), rev[rs(x)] ^= 1;
        rev[x] = 0;
    }
    inline void update(int x)
    {
        if (!isroot(x))
            update(father[x]);
        push_down(x);
    }
    inline void rotate(int x)
    {
        int y = father[x], z = father[y], d = get(x);
        if (!isroot(y))
            ch[z][y == ch[z][1]] = x;
        ch[y][d] = ch[x][d ^ 1];
        if (ch[x][d ^ 1])
            father[ch[x][d ^ 1]] = y;
        ch[x][d ^ 1] = y, father[y] = x, father[x] = z;
        push_up(y), push_up(x);
    }
    inline void splay(int x)
    {
        update(x);
        for (int f; f = father[x], !isroot(x); rotate(x))
            if (!isroot(f))
                rotate(get(x) == get(f) ? f : x);
    }
    int access(int x)
    {
        int p = 0;
        for (; x; p = x, x = father[x])
            splay(x), rs(x) = p, push_up(x);
        return p;
    }
    void makeroot(int x) { x = access(x), std::swap(ls(x), rs(x)), rev[x] ^= 1; }
    int find(int x)
    {
        access(x), splay(x), push_down(x);
        while (ls(x))
            x = ls(x), push_down(x);
        splay(x);
        return x;
    }
    void split(int x, int y) { makeroot(x), access(y), splay(y); }
    void link(int x, int y)
    {
        makeroot(x), splay(x);
        if (find(y) == x)
            return;
        father[x] = y;
    }
    void cut(int x, int y)
    {
        makeroot(x);
        if (find(y) == x && father[y] == x && !ls(y))
            ls(x) = father[y] = 0, push_up(x);
    }
} lct;

int p[maxn];

int main()
{
    int n = read();
    for (int i = 1; i <= n; i++)
    {
        int x = read();
        lct.link(i, i + x > n ? n + 1 : i + x);
        p[i] = i + x > n ? n + 1 - i : x;
    }
    int m = read();
    while (m--)
    {
        int pos = read(), x = read();
        x++;
        if (pos == 1)
        {
            lct.split(x, n + 1);
            cout << lct.siz[n + 1] - 1 << endl;
        }
        else
        {
            int k = read();
            lct.cut(x, x + p[x]);
            lct.link(x, x + k > n ? n + 1 : x + k);
            p[x] = x + k > n ? n + 1 - x : k;
        }
    }
}

总结

注意题目的性质，可以考虑挖掘题目的一些性质，魔改数据结构入手，也可以考虑对数据结构进行一些扩展。