checkmin 线段树

题意：

给你一个长为 \(n\) 的序列 \(a\)，支持：

• 1 l r x：\(\forall a_i \in [l,r],a_i \gets \min(a_i,x)\)。
• 2 l r：求 \(\sum_{i\in [l,r]} a_i\)。
• 3 l r：求 \(\max_{i \in [l,r]} a_i\)。

数据范围：\(n,m \le 10^5\)。

思路：

考虑线段树，显然一个结点需要维护的基本信息为 \(sum\) 和 \(max\)。

考虑 \(\operatorname{checkmin}\) 操作对于一个被其完全覆盖的区间 \([L,R]\) 的影响。

（因为使用了线段树，所以不被完全覆盖的区间直接使用 \(\operatorname{pushup}\) 进行更新，并且这些区间只有 \(\Theta(\log n)\) 个）

发现这个操作会使得 \([L,R]\) 中的数趋于相同。

具体来说，令 \(max\) 为最大值，\(sec\) 为严格次大值。

考虑如下情况：

1. 如果 \(x \ge max\)，对区间不会有影响。
2. 如果 \(max > x > sec\)，只需要修改最大值，区间信息可以容易地更新，然后打上一个修改最大值的标记即可。
3. 如果 \(sec \ge x\)，发现修改后这个区间中的不同数的个数至少减少一个，考虑暴力递归到下一层。

令一个区间的势能为其中的不同数的个数。

显然每次操作只有被部分修改的区间势能可能加 \(1\)，因此势能总增量为 \(\Theta(m \log n)\)，因此势能总减量为 \(\Theta((n+m)\log n)\)。

显然每次递归必然以为着该区间势能减少，因此递归总次数不会超过势能总减量。

因此总时间复杂度：\(\Theta(n \log n)\)。