不辛苦，命苦。

Nelofus · 2025-08-02 23:40:59 · 题解

ABC417G 的题解。DAG 链剖分做法，可持久化平衡树不会。

首先考虑树的情况怎么做。

也就是说，每个点只作为至多一个点的 L,R，这当然不可能，但是你不妨假设初始不是只有 S_0 和 S_1，而是有很多个长度为 1 的字符串。

你发现这个东西肯定是个二叉树森林。每次就是问你一个点 u 子树里的第 x 个叶子是啥。

你一个自然的想法当然是从上往下二分，假设当前节点是 u，如果 x>\mathrm{Left}(u) 就 x\leftarrow x-\mathrm{Left}(u)，然后 u\leftarrow \mathrm{Rson}(u)，否则 u\leftarrow \mathrm{Lson}(u)。这里 \mathrm{Left}(u) 表示 u 左儿子子树中的叶子数。

答案肯定是对的，但是你发现树不平衡，所以复杂度爆了。那一个自然的想法当然是想办法一次往下跳很多步。

这要求我们每个节点有一个后继，不构造出链状结构这个想法就没法成立。我们先起手一个 HLD 试试看，当然这里看重儿子的依据不是子树大小，而是叶子个数，复杂度也就差常数倍所以没关系。

HLD 完了那肯定就是二分 / 倍增。倍增好写一点，考虑倍增。对每个点 u 维护 \mathrm{jump}(u,k) 表示从 u 出发，在重链上往下走 2^k 步到的节点，再维护一个 \mathrm{skip}(u,k)，表示这 2^k 步之中，所有下一步向右的节点 u 的左子树叶子个数之和。

然后倍增跳就行了，注意能跳的 k 必须满足

x>\mathrm{skip}(u,k)\land x\le \mathrm{skip}(u,k)+\mathrm{f}(\mathrm{jump}(u,k))

其中 \mathrm{f}(u) 的意思是 u 子树的叶子个数。这很容易理解，x-\mathrm{skip}(u,k) 这个叶子肯定要在跳完的 \mathrm{jump}(u,k) 这个子树内。在每轮结束之后在手动把 u 往左子树 / 右子树移一位。

然后就是分析复杂度。我们肯定是分析手动移位的个数，因为每轮倍增的代价是 \mathcal O(\log q) 的。分析 x 的变化，我们分成四类讨论：

手动向左，左侧为轻边。
手动向右，右侧为轻边。

这两类加起来肯定是 \mathcal O(\log n)。

手动向左，左侧为重边。
手动向右，右侧为重边。

显然，这两类根本不可能。因为如果我们还能在重链上往下走，刚才在倍增的时候这条边肯定就走过了。

综上，复杂度 \mathcal O(q\log^2 q)。

然后考虑原问题，这实际上是一模一样的。

接下来说的所有路径，指的都是当前点出发，到达 \texttt{0} 和 \texttt{1} 这两个初始字符串的路径。

终点指的也是这两个初始字符串。

我们要找到从 u 出发，从第 x 条小的到 \texttt{0} 或到 \texttt{1} 的路径。

这里小的意思就是说，我们维护一个空的字符串 s，每次往左走就在 s 后增加一个 \texttt{a}，往右走就在 s 后增加一个 \texttt{b}。然后路径 \mathcal P_1 比路径 \mathcal P_2 小就是 \mathcal P_1 对应的字符串，字典序小于 \mathcal P_2 的字符串。

就是，左侧的所有路径小于右侧的所有路径。

那 \mathrm{f}(u),\mathrm{Left}(u) 之类的都类似改成路径数就行了。

欸，问题是这个重链剖分咋办来着？注意到询问的 X_i\le 10^{18}，所以只要点 u 的左后继 \mathrm{Lson}(u) 的 \mathrm{f} 比 10^{18} 大，我们就可以删掉 u 的右后继了，它根本没用。

从而，每个点出发的路径总数就是 10^{18} 的量级，而不是指数级。那当然就是把 DAG 链剖分拿出来了！我们把点 u 的后继中 \mathrm{f} 较大的那个称为重后继，从而不难发现每次走向一个轻后继，\mathrm{f} 至少减半。所有从每个点 u 出发到达终点也至多会经过 \mathcal O(\log W_i) 条轻边。

那我们直接把上面树上的做法搬下来即可。附代码：

// 望んだ その星 塔の頂上で
// あなたの目を焼くのはひかり
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;

//{{{
template<typename Ta, typename Tb>
inline void chkmax(Ta &a, const Tb &b) {if (a < b)  a = b;}
template<typename Ta, typename Tb>
inline void chkmin(Ta &a, const Tb &b) {if (a > b)  a = b;}
constexpr int MEMORY_POOL = 1 << 20;
char BUFFER[MEMORY_POOL], *PS, *PT;
inline char gc() {
    if (PS == PT)   PT = (PS = BUFFER) + fread(BUFFER, 1, MEMORY_POOL, stdin);
    return PS == PT ? EOF : *PS++;
}
template<typename T>
inline void read(T &ans) {
    ans = 0;
    T w = 1;
    char c = gc();
    while (!isdigit(c)) {
        if (c == '-')   w = -1;
        c = gc();
    }
    while (isdigit(c)) {
        ans = (ans << 3) + (ans << 1) + (c ^ 48);
        c = gc();
    }
    ans *= w;
}
template<typename T, typename ...Ts>
void read(T &a, Ts&... other) {
    read(a);
    read(other...);
}
//}}}

constexpr int N = 5e5 + 10;
constexpr int K = 20;
constexpr u64 MAXV = 1e18 + 200;
std::array<int, 2> ch[N];
bool vis[N];
int jump[N][K];
u64 skip[N][K];
u64 f[N];
int n, q;

int main() {
#ifdef HeratinoNelofus
    freopen("input.txt", "r", stdin);
#endif
    f[1] = f[2] = 1;
    read(q);
    n = q + 2;
    for (int i = 3; i <= n; i++) {
        int l, r;
        i64 x;
        read(l, r, x);
        l += 1, r += 1;
        int u = i;
        if (f[l] >= MAXV)
            r = 0;
        ch[u][0] = l, ch[u][1] = r;
        f[u] = std::min(f[l] + f[r], MAXV);
        if (f[l] < f[r])
            jump[u][0] = r, skip[u][0] = f[l];
        else
            jump[u][0] = l;
        for (int k = 1; k < K; k++) {
            jump[u][k] = jump[jump[u][k - 1]][k - 1];
            skip[u][k] = skip[u][k - 1] + skip[jump[u][k - 1]][k - 1];
            chkmin(skip[u][k], MAXV);
        }

        while (u != 1 && u != 2) {
            for (int k = K - 1; k >= 0; k--)
                if (jump[u][k] && skip[u][k] < x)
                    if (f[jump[u][k]] + skip[u][k] >= x)
                        x -= skip[u][k], u = jump[u][k];
            if (u == 1 || u == 2)
                break;
            if (x <= f[ch[u][0]])
                u = ch[u][0];
            else
                x -= f[ch[u][0]], u = ch[u][1];
        }
        assert(x == 1);
        std::cout << u - 1 << '\n';
    }
}

其实真实情况是先条件反射 DAG 链剖，然后条件反射倍增，再想的树上的情况，就做完了。为啥写得这么长我也不懂，可能是退役若干个月完全忘记怎么说 OI 话了。