题意简述

维护长度为$n$的序列$a$，有$m$组操作。

1.0 x y t：对于$x \le i \le y$，令$a_i = \min(a_i,t)$。

2.1 x y：对于$x \le i \le y$，求$a_i$的最大值。

3.2 x y：对于$x \le i \le y$，求$a_i$的总和。

$1 \le n,m \le 10 ^ 6, 1 \le x \le y \le n, 0 \le a_i,t \lt 2 ^ {31}$

题目解析

小清新数据结构啊……

XYZ大爷和吉利爷太神啦！看了论文终于会做了，太神奇。

考虑线段树，我们发现这道题无法用经典的懒标记维护，怎么办呢？

我们对于线段树的每个结点，维护最大值$max$，最大值出现次数$cnt$，严格次大值$sec$和区间和$sum$。

修改时，对于可修改结点$x$，若

1.$t \ge max(x)$：修改对于该区间无效，返回。

2.$sec(x) \lt t \lt max(x)$：$t$只对$max(x)$发生影响，令$max(x) = t$并更新区间和，返回。

3.$sec(x) \le t$：无法简单地更新区间和了……

怎么办呢？遇到第三种情况，继续向下DFS直到有结点满足条件$1,2$。

这个复杂度靠谱吗？一开始是我是怀疑的，看完论文后我真心膜膜膜~~（证明待填...）

另外我想知道，这题现场有人做出来吗……