写在前面的话
\(80+80+100+30=290 , \text{rank3}\) ,发现自己还是太菜了。
这次比赛挂大分，算下来掉了 \(40\) 分。本质上还是我自己对于问题的考虑不够全面，思维不够严谨。不好评价。
T1
题目描述：现在有 \(n\) 个区间，你需要选出一些区间，然后设这些区间的交集为 \(V\) ,并集为 \(U\) 。最大化 \(AV+BU\) , \(A,B\) 为题目给出的常数。
思路点拨：我们分两类讨论：
- 选两个区间（这两个区间有交）
为什么是两个区间，因为选择更多的区间一定是更劣的啊（交集不变，并集变小）。
我们先排除区间包含的情况（并集不会变大，但是你交集变小了）。这一部分可以先对全部的区间按照左端点为第一关键字，右端点为第二关键字（右端点大的考前），进行排序。如果一个区间满足这个区间之前的区间有右端点比他自己的右端点要大，那么这个区间就是被包含的。记录一个前缀最大值就是可以的了。
之后我们枚举一个区间，使用数据结构去找另一个区间。
如果存在两个区间 \(i,j\) 满足 \(l_i \leqslant l_j \leqslant r_i \leqslant r_j\) ，贡献就是 \((r_i-l_j+1)\times A+(r_j-l_i+1)\times B\) ，对于区间 \(j\) 而言，他的贡献就是 \(-Al_j+Br_j\) 。我们将这个值插入到权值线段树的 \(l_j\) 处，每一次对区间 \(i\) 在权值线段树上做 \([l_i,r_i]\) ,最大值查询,最后加上 \((r_i+1)\times A+(-l_i+1)\times B\) 。这是一个常量，对于一个区间 \(i\) 而言是恒定的，与 \(j\) 无关。
时间复杂度 \(O(n \log n)\)
- 选了一堆区间，没有交
就这样。