【LGJOI】上古遗迹
WeLikeStudying · · 个人记录
- 我深感孤独,因为我菜得离谱,QwQ。
你能比我还菜吗!
题意
- 比赛链接。
- 题目
\text{ID}:8806 。 - 给定长度为
n 的数列,一个区间的权值是它的最小值乘上它的长度,询问某个区间的子区间的最大权值。
分析
- 全局查询怎么做?我们计算出从每个点向左向右最长延伸出的端点,这个复杂度用单调栈做到
O(n) 。 - 静态区间查询怎么做?相当于每次查询的左端点对
l 取较大值,对r 取较小值,然后重新计算长度乘权值。 - 难道只能暴力扫?我们发现我们有很多个区间,考虑将它们分类讨论。
- 有两种情况很容易确定:被
[l,r] 包含的,和包含[l,r] 的,可以利用二维数点轻松地统计贡献。 - 接下来问题在于只有左端点和右端点被覆盖的区间。
- 然后我们可以用
\text{CDQ} 分治套李超树来实现这一切,当然如果你懒的话也可以用线段树套李超树。 - 代码实现,并不是很确定正确性,虽然能过。
- 更新:现在已经确定正确性并找到错误的原因。