CPU 监控
Aftglw
·
·
题解
打标记，推标记，好麻烦。
历史最值问题、历史版本和问题，直接考虑用不动脑子的线代解法。
由于要维护两个数组 a, b，然后每次操作让 b_i \leftarrow \max(a_i, b_i)，于是直接把 a_i, b_i 放入一个向量里面，记作 \begin{bmatrix} a_i\\b_i \end{bmatrix}。
重定义矩阵乘法，将 \times, + 分别换成 + ,\max，则每次更新 b_i \leftarrow \max(a_i, b_i) 可以看作：
\begin{bmatrix} a_i\\b_i \end{bmatrix}
\leftarrow
\begin{bmatrix} 0 & -\infty \\ 0 & 0 \end{bmatrix}
\begin{bmatrix} a_i\\b_i \end{bmatrix}
用线段树维护向量，那么每次操作完让全局乘上一个固定的矩阵即可，直接打区间乘法 标记。
然后考虑区间加法。
如果区间加上 k：
\begin{bmatrix} a_i\\b_i \end{bmatrix}
\leftarrow
\begin{bmatrix} k & -\infty \\ -\infty & 0 \end{bmatrix}
\begin{bmatrix} a_i\\b_i \end{bmatrix}
然后考虑区间覆盖。
发现不对了，需要一个常数项，于是将向量改为 \begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
那么如果区间赋为 k：
\begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
\leftarrow
\begin{bmatrix} -\infty & -\infty & k \\ -\infty & 0 & -\infty \\ -\infty & -\infty & 0 \end{bmatrix}
\begin{bmatrix} a_i\\b_i \\ 0 \end{bmatrix}
同理每次区间加变为：
\begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
\leftarrow
\begin{bmatrix} k & -\infty & -\infty \\ -\infty & 0 & -\infty \\ -\infty & -\infty & 0 \end{bmatrix}
\begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
更新 b_i 变为：
\begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
\leftarrow
\begin{bmatrix} 0 & -\infty & -\infty \\ 0 & 0 & -\infty \\ -\infty & -\infty & 0 \end{bmatrix}
\begin{bmatrix} a_i\\b_i\\0 \end{bmatrix}
发现任何操作都可以转化为了区间乘法，于是只用维护一个乘法标记就行了。
时间复杂度 \mathcal O(n \log n) ，但是由于是矩阵乘法，所以常数较大，但是足以通过，code。
但是有些情况就过不了，比如这题 ，所以有必要学会一定的卡常技巧（如果你非要把矩阵乘法完全循环展开还是可以通过那道题的）。
发现任何时刻任何矩阵中，除了这四个位置（* 标记处），其他位置的值都是不变的。
\begin{bmatrix} * & -\infty & * \\ * & 0 & * \\ -\infty & -\infty & 0 \end{bmatrix}
于是可以只用维护这四个位置的值，然后根据矩阵乘法写出这四个值的转移式即可。
这样写常数约为直接矩阵乘法的 \frac 1 4，code。
当然还可以优化常数，比如标记永久化，只不过我就没写了。
注意 -\infty 不要设得太小，会爆 long long。