- 首先可以想到一个性质：覆盖 \(\min\) 的区间加上一定不优。因此考虑以每个点为 \(\max\)，判断包含这个位置的所有线段中和的最小值
- 然后就不会了 \(QwQ\)
- 原来这里还有一个性质：最小值一定是 \(\min(a_1,a_m)\)，因为假设作为 \(\max\) 的点为 \(x\)，\(1\) 被覆盖到的点 \((1,x]\) 肯定都被覆盖到，而 \(m\) 同理。
- 因此可以把线段按照左端点排序，右端点加入堆中维护包含 \(x\) 的线段，同时维护 \(a_1,a_m\) 的值，每次和 \(ans\) 取 \(\max\) 即可
- 复杂度 \(O(n \log n)\)
CF1884C Medium Design
发布时间 2023-12-28 21:25:06作者: FOX_konata