Luogu5044 [IOI2018] meetings 会议

题意：有 座山排成一行，第 座的高度为 。

设 为 之间 的最大值。

每次询问给出区间 ，要求合理地选定 以最小化

允许离线，，时限 。

---

发现无法找到简明的性质，先考虑大力 。

设 为询问 的答案。

转移时，先取出 内的最大值 。

若集合地点选在 左侧，则右侧的 都为 ，反之类似。

可以写出转移： 这样就得到一个 的做法。考虑优化这个 。

---

我们发现，转移和区间内的最大值（位置）有关，考虑建立笛卡尔树。

对于笛卡尔树节点 ，设：

• （前缀 DP 值）
• （后缀 DP 值）

如何求 ？根据转移方程，我们只需：

• 找出 中的最大值
• 对应到笛卡尔树节点
• 找出 的左右儿子
• 查询 。

为了避免讨论，可以翻转数组做两次，这样就只需要考虑 相关的东西。

---

在笛卡尔树上 dfs，同时求解 。设左右儿子分别为 ，当前区间最大值为 。

• ：

  可以直接继承 。

• 单点修改。

• ：

  • ：继承自 ，再区间加。

  • 区间对一次函数取 。

    区间一次函数 min 较为复杂，不容易找到一个 的解法。

  考虑转移中 取左边的条件,寻找性质。 不等式左侧是常数。对于右侧， 每增加 ，容易发现 的增量不会超过 ，所以 是单调减的。

  所以，被 所影响的恰是一个前缀。

  这样，我们就只需要实现线段树二分和线段树区间覆盖一次函数了。

看起来我们需要对每个节点维护一个线段树，并考虑继承。好消息是，由于笛卡尔树两个子节点区间不交，只需用一棵线段树维护。

二分时，需要查看一个区间内的 的最大值，由于单调性，直接取最左侧的值就好了。

复杂度 。