Discussion #925 - Problem #9516

关于区间 chmax 区间历史和线段树的研究

QOJ9516 需要使用此数据结构。

它需要支持区间 chmax，求区间历史和。

一般来说区间 chmin 使用吉司机线段树维护，区间历史和使用矩阵维护标记，但是放在一起却会出现问题，对于最小值的标记和对于次小值的标记都需要对增加一个历史版本的操作进行复合。然而下放的时候，会出现要修改的元素个数不同，从而导致了区间和的增量不同的问题。

找到最小值比目前 chmax 的值小的区间，如果最大值比当前 chmax 的值小，就进行 cover 操作，否则递归。

这样就可以维护了。

然而可以构造一个数组 1000 0 1000 0 1000 ... 0 1000

然后全局 chmax $1,2,3\cdots$ 就每次都要递归满叶子，TLE。

如果当前这个区间的值全都相同，就进行 cover，否则递归，解决问题的方式和上面类似。

卡TLE的方法相同。

笔者对于这个问题深思熟虑，认为应该直接对算法本身进行考虑，抛弃传统的矩阵维护思想。（借鉴算法三的代码）

$tag,stag$ 表示最小值整体加的标记，最小值整体加的历史和。

$sm,ans$ 表示区间和以及区间历史和。

$upd$ 表示版本更新的次数。

$mn,mn2,mncnt$ 表示最小值，次小值，最小值的出现次数。

对于一次 chmax，会对最小值值进行整体加的操作。

对于一次版本更新，会让区间的和累加到历史和，并且将标记累加到标记历史和。

对于 pushup 是容易的。

对于 pushdown 需要找到对应的值，然后根据对应的 mncnt 来进行更新，而不是整个区间。

复杂度容易分析到和吉司机线段树相同 $O(q\log^2 n)$。

在排列的部分分之后，要解决一个子树反复被填满的问题。

这里需要注意到，如果目前的子树最小值发生变化才会更新，假设从 $v\rightarrow v^\prime$。那么如果一个决策不包含当前的子树，也不会更新。如果包含了当前的子树，剩下的值设为 $x$。

这里每个子树的指针最多动子树大小次，插入元素可能会增加动的次数，但是都是 $O(2^nn^2)$ 级别。