审题

OK进入正题，首先，线段树3有五个操作，单独拿出来1、3、4来看，就是一个很简单的区间修改加上区间查询最大值和求和，记录一下懒标记、最大值和总和就好。

但是，题目的难点就在于2和5，一个一个来看。

分析

2操作中是将区间中的数全都取与一个数取最小值，那么如果是暴力思路，应该是单点修改，因为我们所记录的数不足以支撑我们去进行区间修改。 但是如果我们选择让这个数在这个区间范围内比严格次大值大比最大值小，是不是就是说我们可以对这个区间内的最大值修改从而不用对其他值修改，而修改的值就是这个数减去区间最大值。

这样我们的区间最大值就都变成了这个数，而其他值由于比这个数小所以不用变，这种方法最坏情况下才会和单点一致，所以复杂度肯定够。（具体分析见吉司机）

于是根据这个，我们的结构体里面需要再记录一个懒标记，这个懒标记是这个区间内除了最大值之外的数要加的值。

因为有些地方需要加的是一个数（操作1），有些地方加的是0（操作2）。然后还需要记录一个严格次大值，这个数的初始化应该是一个很小的数，然后在进行向上更新时需要变成左右儿子中第二小的那个，也就是需要判断一下。

最后需要一个cnt来记录区间有多少个最大值，这样方便进行修改。

5操作是求历史最大值，初始化的时候就是和现在最大值一致，然后在每次下放或者更新时，将其和最大值加上一个最大值要加的数里的最大值，因为比这个值要小的值加了也不会是历史最大值。

也不用怕越界，因为我们如果不是下放是修改的操作，那么此时这个最大值要加的数的最大值和现在的最大值要加的数是一致的 （比较乱嗷），然后如果是下放，由于我们下放的儿子还没有进行过操作，所以它们此时的最大值就是它们现在的状态，那么中间我们进行的操作都是在它们现在状态的基础上操作的，所以需要将历史最大值与现在最大值加上最大值加的数的最大值之前求较大的数并且赋值给历史最大值。 （这一段比较乱啊，慢慢来理解，当然如果有人思路更好的话可以告诉我qwq）

于是根据这个，我们结构体又要再记录俩懒标记，分别为最大值要加的数里面最大的，然后是除了最大值之外加的数里面最大的，作用和上面那俩差不多。然后还要记录一个历史最大值。

最后

最后，本题完结，丑陋的代码便不放了，如果有想看的可以QQ私传一下，代码过于丑陋，而且看别人代码写出来的题总归不是自己的，所以建议自己写一写。

愿诸位可以AK IOI！