【bzoj】3745: [Coci2015]Norma

题意：

n <= 5e5

题解：

** 首先，想到确定最大值，最小值的区间一起统计。因为是统计所有区间，第一想法是枚举右端点，维护所有左端点的答案
用单调栈分别维护最小值，最大值，把贡献拆开讨论一下，需要用线段树维护mx(i) * mn(i), mx(i) * mn(i) * i,mx(i) * i,mn(i) * i,mx(i),mn(i) 6个和。因为更新的时候要么更新最大值，要么更新最小值。讨论一下该怎么修改。
**
**
正解是CDQ分治：
思路是一样的，但是CDQ分治写起来更加简便：
当前分治层只需要考虑的就是跨越当前中间节点的所有区间如何计算答案了。
从mid开始向左枚举左端点，考虑右端点的贡献。那么我们在右侧记录两个指针p,q，分别表示左侧的最大值和最小值第一次改变的位置。这两个指针会把整个序列分成三段。
第一段最大值和最小值都是左侧最大最小值，直接计算区间长度和就好了。
第二段是最大值和最小值中一个被改变了，分情况讨论一下，维护右侧的区间最大最小值就可以直接算了。第三部分是最大值和最小值都被改变了，那么把式子写出来，维护一个前缀就好了。
CDQ的思想也是固定mx和mn该怎么贡献，因为分治，所以可以方便的从mid把区间划分开
**

这题的细节一定要推清楚：区间是左闭右开的。推清楚细节后非常好写，然而我因为区间端点没有写对，还对拍了！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！