前言

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

思路

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