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

complexor · 2025-11-27 20:53:36 · 题解

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

将答案放在每座塔中编号最小的积木处，那么如果 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)。