【LGJOI】上古遗迹

WeLikeStudying · 2022-03-27 22:47:54 · 个人记录

• 我深感孤独，因为我菜得离谱，QwQ。
• 你能比我还菜吗！

题意

• 比赛链接。
• 题目 \text{ID}:8806。
• 给定长度为 n 的数列，一个区间的权值是它的最小值乘上它的长度，询问某个区间的子区间的最大权值。

分析

• 全局查询怎么做？我们计算出从每个点向左向右最长延伸出的端点，这个复杂度用单调栈做到 O(n)。
• 静态区间查询怎么做？相当于每次查询的左端点对 l 取较大值，对 r 取较小值，然后重新计算长度乘权值。
• 难道只能暴力扫？我们发现我们有很多个区间，考虑将它们分类讨论。
• 有两种情况很容易确定：被 [l,r] 包含的，和包含 [l,r] 的，可以利用二维数点轻松地统计贡献。
• 接下来问题在于只有左端点和右端点被覆盖的区间。
• 然后我们可以用 \text{CDQ} 分治套李超树来实现这一切，当然如果你懒的话也可以用线段树套李超树。
• 代码实现，并不是很确定正确性，虽然能过。
• 更新：现在已经确定正确性并找到错误的原因。