题意
给定 (n) 个区间，我们定义区间集合 (S(|S|>1)) 的权值为 区间交 ( imes) 区间并，找出权值最大的区间集合。
(nle 10^6)
分析
-
首先排除区间包含的情况，但是注意存在特殊情况：答案是两个区间，其中一个区间被另一个包含。
-
排除之后的区间左右端点都递增，我们的答案一定是一段连续的区间，记最左最右的区间为 (i,j) ，容易得到
[ans=(R_j-L_i) imes(R_i-L_j) ]将式子拆开：
[ans=R_iR_j+L_iL_j-L_iR_i-L_jR_j ]将 (L_iR_i) 看做转移函数 (g) ，(R_iR_j) 是关于 (i,j) 的二元函数 (s) ( (L_iL_j) 同理)。容易证明 (s) 满足四边形不等式：
假设四个区间 (a<b<c<d) (因为左右端点都单增所以可以如此判断)，首先假设不满足决策单调，那么有
[egin{cases}g(a)+s(a,c)<g(b)+s(b,c) \ g(a)+s(a,d)>g(b)+s(b,d)end{cases} ]移项之后容易得到：
[s(b,c)-s(a,c)>s(b,d)-s(a,d) ][R_c(R_b-R_a)>R_d(R_b-R_a) ]由于 (R) 递增，上式显然不成立。
所以决策单调。
- 然后套个单调队列的板子就没了。
- 总时间复杂度 (O(nlogn))