题解：P5044 [IOI 2018] meetings 会议

min_inf · 2025-06-20 16:35:13 · 题解

模拟赛场上想出来的神秘做法。

对于单组询问，我们考虑在笛卡尔树上 DP，显然有转移：

考虑怎么刻画区间笛卡尔树：找到区间最大值，把从左端点开始的前缀 \max 及其右儿子和从右端点开始的后缀 \max 及其左儿子合并起来。接下来我们只考虑右侧的做法。

从左往右扫，维护一个递减的单调栈并维护当前每个点的 DP 值 g_i。考虑加入一个点 i 产生的影响：

• 前面的某个点 j 有 g_j\gets\min(g_j+a_j,g_{nxt_j}+a_j(sz_{ls_j}+1))（从右往左依次转移），nxt_j 是单调栈上右边的元素。

看起来第二个不是很好维护，但是我们只需要求 Q 个 g，考虑不直接维护每个 DP 值。假如我们要询问的是 g_x，可以发现肯定是从询问时存在的某个 f_{ls_y}+a_y 转移过来的，被加上的一定是 y-x 个 a_y（显然吃最右边的最优）和他们之间的节点的 a_i(sz_{ls_i}+1) 的和，可以在单调栈上做一个前缀和，就是插入和询问的时候各加一个常数。

这样问题就变成了每个点有 a_i 和 b_i，要支持单点修改，全局 b_i\gets b_i+a_i，求区间 \min b_i。显然可以 KTT 维护，时间复杂度 O(n\log^2n)，常数很小。

code。