题解：P14761 [Opoi 2025] CCD 的序列

SuyctidohanQ · 2025-12-17 20:56:52 · 题解

先把括号转成数字：( 是 1，) 是 -1。合法括号序列就是前缀和一直 \ge 0 且最后总和为 0。

每次操作是往位置 l 和 r 各塞一个括号。可以把原序列看成 L+M+R，其中 M 是 [l+1, r] 这段。操作后变成 L+(+M+)+R。

只有跨过插入位置的匹配会变。具体来说，就是 M 里面那些和 L 匹配的右括号，以及 M 里面那些和 R 匹配的左括号。

设 M 里没配对的右括号有 x 个，没配对的左括号有 y 个，答案就是 2(x+y)。

怎么算 x 和 y？用前缀和最小值 mn。如果 mn<0，说明多出来 |mn| 个右括号，所以 x = \max(0, -mn)。y 就是区间和 sum 加上 x。