如果没有 \(1\) 操作，只有 \(2\) 操作，怎么办。
需要求解每种前缀最大值的和，使用单侧递归线段树（无论是相同还是不同都可以处理），处理出一个区间的信息二元组 \((mx, sum)\)，\(mx\) 表示最大值，\(sum\) 表示以当前区间开头的区间答案，那么不妨考虑处理合并函数 \(merge (ls, rs)\)，过程如下：
- 处理出 \(ls, rs\) 的信息。
- 此时 \(node(sum) = ls(sum) + calc(rs, ls(mx))\)。
其中 \(calc(rs, ls(mx))\) 表示单侧递归在前面的最大值是 \(ls(mx)\) 的情况下，其每种前缀最大值的和是多少，考虑分类讨论：
- \(ls(mx) \ge rs(mx)\)，此时右儿子贡献为 \(0\)。
- \(ls(mx) < rs(mx)\)，此时继续分类讨论：
- \(ls(mx) \ge lls(mx)\)，此时右儿子的左儿子不会产生贡献，那么往 \(rs\) 递归。
- \(ls(mx) < lls(mx)\)，此时形式 \(lls\) 有一段贡献被 \(ls\) 干预，后面 \(rs\) 都是以 \(ls\) 的最大值为历史最大值进行统计贡献，可以用差分的方式直接求出这一部分的贡献，往 \(ls\) 递归。
单侧递归线段树可以做到 \(O(\log^2 n)\) 单次查询，虽然本题有更优美的性质，但这也够了。
考察进行 \(1\) 操作很多次后 \(a_i\) 长成什么样子：
- \(a_i\) 一定是原本 \(a[i, i + ?]\) 的 \(\max\)。
这个很容易理解，但是 \(?\) 的维护看起来不是很简单，对于每个元素也没有很好的颜色段均摊做法，考虑贡献反演，从贡献的角度看 \(a_i\) 到底让前面多少个元素 \(chkmax\) 了。初始给每个地方放一个等于其下标的牌子，那么每次对 \([l, r]\) 进行 \(1\) 操作相当于对着 \([l + 1, r]\) 这段区间的牌子向前移动一格，对于一个牌子 \(p\)，那么其移动的路径上的所有位置都跟 \(a_p\) 要 \(chkmax\) 一次。
牌子的维护是简单的，可以弄个线段树上二分解决，考察此时如何求得 \(b_i\) 也就是目前的 \(i\) 位置上的值，你需要对于牌子发现几个性质：
- 对于编号为 \(1 \sim n\) 的牌子，其处于的位置单调不降。
那么对于一个位置的 \(b_i\)，其 \(i + ?\) 的值就是 \(\le i\) 的下标中放的编号最大的那个牌子的编号，比这个牌子编号大的牌子都没有经过 \(i\)，比其小的都在所计算的区间内，这确实是一个比较重要的观察。
但是这仍然没有将问题变得更加简单，\(2\) 操作的区间不同前缀最大值和的计算仍然是困难的，思考如何将这个 \(2\) 操作转化为与上面有关的东西，记录 \(c_i\) 为 \(i\) 位置上牌子对应的值的最大值，发现 \(b_l \sim b_r\) 的不同前缀最大值和等价于 \(b_l, c_{l + 1}, c_{l + 2}, ..., c_{r}\) 的每种前缀最大值和（使用单调栈刻画更容易推导得到），由于移动，所以实际上关于 \(c\) 的维护是一个单点更改，需要映射一下才能方便维护，使用单侧递归线段树 / 平衡树可以简单维护。
其实：思考问题简化过后能否简单解决，同时思考序列操作后的具体形式，将贡献倒过来看成贡献到哪个位置，基于之前的推导过程结合得到有关于单个位置的简单刻画方式，将问题转化为我们尝试过的问题，使用数据结构解决。