不辛苦，命苦。

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)

条轻边。

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

CPP

// 望んだ その星 塔の頂上で
// あなたの目を焼くのはひかり
#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 话了。

文章操作

相关推荐

评论

不辛苦，命苦。