P14598 [COCI 2025/2026 #2] 搭塔 / Tornjevi 题解

简单的做法，不需要动脑子。

$\mathcal{O}(nq)$ 的暴力算法是从左往右顺序枚举，如果有塔顶与当前积木异色的塔就放上去，否则单开一座。设当前有 $a$ 座塔顶颜色为红色，$b$ 座为蓝色，当前遇到的是红色的积木，那么这个过程等价于 $a\leftarrow a+1,b\leftarrow \max(b-1,0)$。这可以表示成一个 $(\max,+)$ 矩乘的形式（相当于给 $\begin{bmatrix} a\\ b\\ 0 \end{bmatrix}$ 左乘一个东西），线段树或猫树维护静态区间矩乘即可优化至 $\mathcal{O}(\omega\cdot n\log n)$。