模板题 ：P6242

题意 ： 写一棵线段树， 支持区间加，区间对 \(x\) 取 \(\min\)， 区间和， 区间最大值， 区间历史最大值。

直接暴力维护是 \(O(n^2)\) 的， 考虑如何优化。

考虑对于线段树的每一个节点， 维护最大值 \(mx\), 最大值个数 \(cnt\)， 严格次大值 \(sec\)。

在区间对 \(x\) 取 \(\min\) 时，

• 若 \(mx \leq x\)， 则不会修改任何值， 直接退出.
• 若 \(x < mx\)， 且 \(sec \geq x\)， 则所有的 \(mx\) 变成 \(x\)， 区间和加上 \(cnt \times (x - mx)\)， 退出.
• 否则递归左右子树.

复杂度分析 ： 摘自 灵梦 的 blog :

这样做的复杂度可以证明是 \(O(m\log n)\) 的。原论文的证明使用了势能分析，这里给出一种更好懂的 \(O((n+m)\log n)\) 下界的证明：

显然只有暴力 DFS 的过程会影响复杂度，我们考虑一次区间最值操作中哪些节点会被搜索到。发现到达的节点区间中不同的数的个数（下称「值域」）一定会减少（因为至少将最大值与次大值合并了）。线段树每层节点表示的区间的值域一共是 \(O(n)\) 的，一共 \(\log\) 层加起来就是 \(O(n\log n)\)。再加上每次操作的复杂度，可以得到复杂度的一个下界为 \(O((n+m)\log n)\)。

对于此题， 因为还有区间加操作， 但是我们对 \(x\) 取 \(\min\) 时只能修改最大值的值， 相当于把维护的元素分成了 最大值 与 非最大值， 用两个懒标记记录即可 （代码中是 \(add_a\) 与 \(add_{a1}\)）。

再加上历史最大值， 我们定义 \(add_b\) 为当前区间最大值历史上加的最多的那次的标记。
同理 \(add_{b1}\) 为当前区间非最大值历史上加的最多的那次的标记。

一个简单的例子是这个区间先 \(+3\)， 再 \(-2\)， 那么 \(add_b\) 就应该是 \(3\)。

结合代码实际讲一下 （由于 cnblogs 插入代码很鬼畜， 大家谅解一下）：

struct tre {
        int maxa, maxb, sec, sum, cnt, len; 
	int add_a, add_a1, add_b, add_b1; //最大值tag 非最大值tag 最大值历史tag 非最大值历史tag 
} tre[M << 2];

\(pushup\) 的时候， 对于最大值在左边或右边或两边都是分类讨论一下 ：

inline void push_up(int p) {
	tre[p].maxa = std :: max(tre[p << 1].maxa, tre[p << 1 | 1].maxa);
	tre[p].maxb = std :: max(tre[p << 1].maxb, tre[p << 1 | 1].maxb); 
        tre[p].sum = tre[p << 1].sum + tre[p << 1 | 1].sum; 
        if(tre[p << 1].maxa == tre[p << 1 | 1].maxa) {
    	tre[p].sec = std :: max(tre[p << 1].sec, tre[p << 1 | 1].sec); 
    	tre[p].cnt = tre[p << 1].cnt + tre[p << 1 | 1].cnt; 
	}
	else if(tre[p << 1].maxa < tre[p << 1 | 1].maxa) {
		tre[p].sec = std :: max(tre[p << 1].maxa, tre[p << 1 | 1].sec); 
		tre[p].cnt = tre[p << 1 | 1].cnt; 
	}
	else {
		tre[p].sec = std :: max(tre[p << 1].sec, tre[p << 1 | 1].maxa); 
		tre[p].cnt = tre[p << 1].cnt; 
	}
}

比较难理解的是下传标记时的对答案的更改操作 ：

inline void upd(int p, int v1, int v2, int v3, int v4) { //最大值 + tag, 最大值历史 + tag, 非最大值 + tag, 非最大值历史 + tag
        tre[p].sum += v1 * tre[p].cnt + v3 * (tre[p].len - tre[p].cnt); 
	tre[p].maxb = std :: max(tre[p].maxb, tre[p].maxa + v2); 
	tre[p].add_b = std :: max(tre[p].add_b, tre[p].add_a + v2); 
	tre[p].add_b1 = std :: max(tre[p].add_b1, tre[p].add_a1 + v4); 
	tre[p].maxa += v1, tre[p].add_a += v1, tre[p].add_a1 += v3; 
	if(tre[p].sec != -INF) tre[p].sec += v3;  
}

最后是几个操作， 相信大家打过板子都会， 代码就不给了。