题解：P5044 [IOI 2018] meetings 会议

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

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

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

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

看起来第二个不是很好维护，但是我们只需要求 $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。