D1T2 逛街
题意
给定一个长度为 $n$ 的序列，有 $m$ 次操作，每次操作为如下两种形式之一：
1 l r从左到右遍历 $i \in [l,r-1]$，令 $a_i \gets \max(a_i,a_{i+1})$- 输出区间 $[l,r]$ 中所有前缀最大值的和
保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。
题解
有一档部分分是，保证操作 1 中 $l=1,r=n$。所以这启发我们去记录一个 $b_i$ 表示现在的值 $a'_i = \max_{j=i}^{b_i} a_j$。我们停下来考虑一下这个地方怎么计算区间 $[l,r]$ 的答案：设前面进行了一操作 $t$ 次，那么显然 $b_i = i+t$，所以这实际上就是在 $\max_{j=l}^{b_l}(a_j),a_{b_l+1},a_{b_l+2},\ldots,a_{b_l+r-l}$ 上询问，用楼房重建这个题的线段树技巧就可以了。
观察这个询问做法，它的想法就是每次考虑「增量」，所以我们在一般的操作上也可以遮掩个考虑。
对于整个问题，和 $l=1,r=n$ 的差别主要在于 $b_i$ 的修改换了。考虑如何维护 $b_i$：初始时显然 $b_i=i$，我们操作 $[l,r]$ 的时候发现，本质就是删除 $b_l$，然后在位置 $r$ 后面复制一份 $b_r$ 。用平衡树就可以维护了。
现在问题在于如何求答案。我们发现，首先一定有 $b_i \leq b_{i+1}$，所以我们可以考虑类似上面的做法，定义 $c_i = \sum_{i=b_{i-1}+1}^{b_i} a_i$，这样询问区间 $[l,r]$，我们先求出 $a_{l}'$，然后就是把 $a_{l}'$ 放到开头，询问 $c[l+1,r]$ 了。所以我们只需要能动态维护 $c$ 即可。发现每次修改造成的影响是：合并 $c_i$ 和 $c_{i+1}$，插入一个没影响的 $0$。其实可以理解为删除较小的那个，并让 $c_r$ 的出现次数多 $1$，所以线段树额外维护一个每个值目前出现的次数就好了。
最后说一下楼房重建那个怎么做：楼房重建这个题解决的是单点修改，多次询问某个区间 $[l,r]$ 的前缀 $\max$ 和。这个做法就是我们每个区间维护一个答案 $sm_x$ 和最大值 $mx_x$。合并区间的时候，我们左边可以直接用 $sm_{lc}$ 和 $mx_{lc}$，右边相当于有限制第一个位置需要 $> mx_{lc}$，所以我们可以定义一个函数 $gao(x,d)$，表示 $x$ 对应的区间，要求第一个位置 $>d$ 的答案是什么。这个函数转移也是分类讨论前一半区间：如果整体 $<d$，那么直接扔掉左边即可；如果第一个数字 $>d$，那么直接返回 $sm_x$ 即可，否则先 $gao(lc,d)$，然后左边当前的限制一定是 $mx_{lc}$，所以再用 $sm_{x}-sm_{lc}$ 就可以得到贡献。每次 pushup 都要掉用一次 $gao$，所以复杂度是 $O(n \log^2 n)$。
总结：
- 从部分分这个特征要多去思考如何计算答案，比如 max 可以用增量的方法计算答案
- 要多思考一些地方有没有可以简化写的方法，比如合并 $c_i$ 和 $c_{i+1}$ 要想到可以用类似权值线段树+线段树二分的方法，并且把合并看成抛弃最小值即可。
D2T2 代金券
题意
有 $n$ 个菜，第 $i$ 个菜价格是 $a_i$。你按照顺序去购买菜。每次可以选择用一些手里有的代金券去抵消价格，假设购买第 $i$ 个菜的时候花费了现金 $A$，那么会获得能在 $\geq i+1$ 的菜使用的代金券 $\lfloor \frac{A}{c}\rfloor$ 张，每张可以抵消一元。问买完所有菜最少需要多少钱。支持修改。
$n \leq 3 \times 10^5$。
题解
如果我们观察钱数，发现这个和初始有多少元现金是很相关的，不是很会处理。所以我们考虑一个和初始无关的量：代金券的使用数量！
这样问题就简化为，我们可以在某个位置占用 $c$ 元造一张代金券，或者是占用 $1$ 元消耗一张代金券，最大化代金券使用数量。
这个显然是可以二分的，考虑二分 $x$。首先我们一定会将代金券的购买放在尽量前面，这样代金券的影响区间才尽量大。那么我们定位到一个 $p$，满足 $[1,p]$ 都买满了。那么我们如何得到 $[1,p]$ 内部消化后剩下了多少代金券呢？可以用一个递推：$f_i = \lfloor \frac{a_i}{c}\rfloor + \max(0,f_{i-1}-(a_i \bmod c))$。
$f_i$ 是可以支持修改快速维护的：相当于是 $f_i = \max(\lfloor \frac{a_i}{c}\rfloor,f_{i-1}-(a_i \bmod c)+\lfloor \frac{a_i}{c}\rfloor)$，可以用 $(\max,+)$ 矩阵乘法来描述：
$$ \begin{bmatrix} -(a_i \bmod c)+\lfloor \frac{a_i}{c}\rfloor& \lfloor \frac{a_i}{c}\rfloor\\ -\infty& 0 \end{bmatrix} \otimes \begin{bmatrix} f_{i-1}\\ 0 \end{bmatrix} = \begin{bmatrix} f_{i}\\ 0 \end{bmatrix} $$
用线段树维护即可。
现在我们知道 $[1,p]$ 买满，设计算出 $p+1$ 需要买 $R$ 张，我们要判断这之后还能否够用。设 $lim = \sum_{i=p+2}^n a_i$，发现需要满足以下两个条件：
- $R \leq lim$
- $R+f_{p} \leq lim+a_p-R \times C$
第一个条件的原因是 $p+1$ 产生的代金券只能在 $[p+2,n]$ 使用；第二个就是判断剩下代金券能否被整体消化了。
这样复杂度就是 $O(n \log^2 n)$ 了。为了优化，我们可以先二分 $p$，再计算 $R$；因为 $p$ 一定满足 $R=0$ 的情况，所以我们只需要找到这样尽量往后的 $p$，然后在计算 $R$ 就好了。
找 $p$ 的时候就可以用线段树上二分做到 $O(n \log n)$ 了。
