bzoj2002: [Hnoi2010]Bounce 弹飞绵羊

Description

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

Input

第一行包含一个整数 \(n\), 表示地上有 \(n\) 个装置, 装置的编号从 \(0\) 到 \(n-1\), 接下来一行有 \(n\) 个正整数, 依次为那 \(n\) 个装置的初始弹力系数. 第三行有一个正整数 \(m\), 接下来 \(m\) 行每行至少有两个数 \(i, j\), 若 \(i=1\), 你要输出从 \(j\) 出发被弹几次后被弹飞, 若 \(i=2\) 则还会再输入一个正整数 \(k\), 表示第 \(j\) 个弹力装置的系数被修改成 \(k\).

Output

对于每个 \(i=1\) 的情况, 你都要输出一个需要的步数, 占一行.

Sample Input

Sample Output

2
3

Data RAnge

对于 20% 的数据, 满足:\(n, m \leq 10000\);

对于 100% 的数据, 满足:\(n \leq 200000, m \leq 100000\).

Explanation

大家一定要把这个 bzoj2002 写一遍, 叫弹飞绵羊...... Link-Cut Tree 的模板题一定要写得很熟练...... ---Tsienyi Lawyer

好吧, 叶老师的这番话我终于听从了, 然后写了一遍动态树 (然而 QTREE 还没有写 QwQ).

关于这道题我调了半天, 然后就是死活 TLE (明显是死循环好不好) 停不下来. 然后我就把自己的代码和标程对着改了很久很久 (差不多两三个小时, 到一点多), 为了这个动用了几乎一切设备: IntelliCLI, PyJudge, MinGW GDB, GDB on Bash on Windows, Diff......, 导致桌面乱糟糟, 最后发现一个很细微的差异:

par(p) = g; if (g) ch(g, y) = p;
if (isroot(q)) {
    isroot(p) = true;
    isroot(q) = false;
}

其中这一块的写法和 Splay 的写法是无异的, 但是就是这样写, 导致了本人无限死循环, 因为其实这段代码应该是这样写的:

par(p) = g;
if (isroot(q)) {
    isroot(p) = true;
    isroot(q) = false;
} else {
    ch(g, y) = p;
}

原因就在于一个节点到底是不是树根并不取决于其父亲是不是空节点, 而是取决于该节点的根标记. 如果根标记为真, 该节点才是根. 这里就把 Splay 树里默认的整个数据结构只有一个根的假设代入到了 Link-Cut Tree 里面了, 然而这个数据结构里有很多个根, 所以导致了万恶的无限死循环......

然而令人很开心的是三行 Splay 魔改一下就可以兼容了=w=

现在回来说题, 题目的大意就是给一棵树, 动态修改节点的父亲, 求节点到根一共遍历了多少个节点 (就是某节点的深度是多少).

谈到修改边的连接, 基本就是动态树无疑了.

然而如果要是一开始以为这只是个有向无环图 (虽然它是), 那么你就错了. 因为虽然每一个点可能从多个点到达, 但是反过来每一个点却只可能去一个点, 这就是一棵树无疑了. 那还有什么可以犹豫的......

有关动态树的操作, 请参见这个论文:QTREE解法的一些研究.pdf

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 200100;

class LinkCutTree
{
public:
    int arr_i[maxn][5];
    #define lc(_x) arr_i[_x][0]
    #define rc(_x) arr_i[_x][1]
    #define ch(_x,_y) arr_i[_x][_y]
    #define par(_x) arr_i[_x][2]
    #define size(_x) arr_i[_x][3]
    #define isroot(_x) arr_i[_x][4]
    int n;
    void update_lazy(int p)
    {
        size(p) = size(lc(p)) + 1 + size(rc(p));
        return ;
    }
    void rotate(int p)
    {
        int q = par(p), g = par(q);
        int x = rc(q) == p, y = q == rc(g);
        ch(q, x) = ch(p, !x); if (ch(q, x)) par(ch(q, x)) = q;
        ch(p, !x) = q; par(q) = p;
        par(p) = g; // if (g) ch(g, y) = p;
        if (isroot(q)) {
            isroot(p) = true;
            isroot(q) = false;
        } else {
            ch(g, y) = p;
        }
        update_lazy(q);
        update_lazy(p);
        return ;
    }
    void splay(int p)
    {
        for (int q = 0; (q = par(p)) && !isroot(p); rotate(p))
            if (par(q) && !isroot(q))
                rotate((p == rc(q)) == (q == rc(par(q))) ? q : p);
        return ;
    }
    void access(int p)
    {
        int q = 0;
        while (p) {
            splay(p);
            isroot(rc(p)) = true;
            isroot(q) = false;
            rc(p) = q;
            update_lazy(p);
            q = p, p = par(p);
        }
        return ;
    }
    void makeroot(int p)
    {
        access(p);
        splay(p);
        return ;
    }
    void link(int p, int q)
    {
        makeroot(p);
        par(lc(p)) = 0;
        isroot(lc(p)) = true;
        lc(p) = 0;
        par(p) = q;
        update_lazy(p);
        return ;
    }
    void init(int n_)
    {
        this->n = n_;
        for (int i = 1; i <= n; i++) {
            isroot(i) = true;
            size(i) = 1;
        }
        return ;
    }
    int query(int p)
    {
        makeroot(p);
        return size(lc(p)) + 1;
    }
} lct;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    lct.init(n);
    for (int i = 1, a; i <= n; i++) {
        scanf("%d", &a);
        if (i + a <= n)
            lct.link(i, i + a);
    }
    scanf("%d", &m);
    for (int idx = 1; idx <= m; idx++) {
        int a, b, c;
        scanf("%d", &a);
        if (a == 1) { // To query
            scanf("%d", &b);
            b += 1; // Due to the strange marker descripted in the problem
            printf("%d\n", lct.query(b));
        } else if (a == 2) { // To modify
            scanf("%d%d", &b, &c);
            b += 1; // Due to the strange marker descripted in the problem
            lct.link(b, b+c <= n ? b+c : 0);
        }
    }
    return 0;
}