[雅礼1706 Day 4] QYH

n 个开区间, 从中选 m (m > 1) 个, 它们的权值为 |交| * |并|. 求最大权值. (1 ≤ n ≤ 10^6, 1 ≤ l < r ≤ 10^6) [bzoj 2687] 交与并 题面没写 "数据有一定梯度", 我还以为不是10分, 就是100分......

首先, 如果A包含于B, 那么用B替换A, 答案不会变差. 但是有一种情况, A是不能被替换为B的: 只选择A和B. 那么, 对于所有区间, 找出包含它的最长区间. 如果存在, 更新答案 (即 ), 扔掉它.

按左端点排序; 左端点相同, 长度大的放前面. 用区间长度更新右端点位置的权值, 那么待查询的是后缀最大值, 用树状数组维护.

处理完之后, 区间左右端点均非严格递增. 发现, 选择 和只选 , 权值是相等的. 所以, 问题简化为, 寻找两个区间 , 使得 最大.

对于一个 , 考察决策 优于 的条件 :

由于左右端点均非严格递增, 一旦对于某个 , 有 , 那么对于 , 同样有 . (反之不然)

称使 最大的 为 的决策点 (若有多个, 取最靠左的), 则 . 以前 优于左边的点, 现在仍然如此.

有了决策单调性, 我们知道决策表长这样: 111 222 33333 4 555

接下来有两种方案: - 单调栈 决策表每一段是单调栈中的一个节点. 每计算出一个新的值, 用它更新决策表. 如果可以整段替换, 就弹栈. 否则, 在这一段内二分, 分裂这个节点. - 分治 定义 求解 的答案, 已知这一段的决策点在 中. 令 . 把 扫一遍, 求 . 然后递归下去: .

时间复杂度都是 , 个人喜欢分治~

听了三位神犇讲这题, 每人讲了至少两遍, 终于产生了一点明白的感觉......非常感谢 ＞﹏＜