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

先考虑单次询问整个序列。

将答案放在每座塔中编号最小的积木处，那么如果 $i$ 记入答案，则需要找到一个 $f_i<i$ 满足 $s_{f_i}\neq s_i$，且所有 $f_i$ 互不相同。

显然 $s_i=\texttt{P}$ 和 $s_i=\texttt{C}$ 的 $i$ 独立且对称，所以不妨认为 $s_i=\texttt{P}$。则所求转化为从序列中最多选出多少互相不交个 $\texttt{CP}$ 子序列。这是一个经典问题，可以贪心地把 $\texttt{C}$ 看作左括号，$\texttt{P}$ 看作右括号，匹配上的括号对数即为所求。类似地处理 $\texttt{PC}$ 子序列，可以做到 $O(qn)$。

事实上，将问题转化为括号匹配还有更好的性质。如果将右括号 $i$ 匹配的左括号作为 $f_i$（失配则为 $0$），那么由括号匹配的性质，当查询 $[l,r]$（即考虑对子串 $s[l:r]$ 进行括号匹配）时：如果 $f_i<l$，则 $i$ 会失配；如果 $f_i\geq l$，则 $i$ 也会匹配上 $f_i$。

先分别考虑 $\texttt{CP}$ 和 $\texttt{PC}$ 进行括号匹配，那么查询 $[l,r]$ 的答案即为有多少 $l\leq i\leq r$ 满足 $f_i<l$。这是一个二维数点问题，容易离线树状数组/在线主席树做到 $O((n+q)\log n)$。