括号序列

Miraik · 2022-11-26 19:23:38 · 题解

首先考虑给定一个长度为 n 的括号序列，我们将它变成一个合法括号序列的最优策略是什么样的。

首先有两个性质：

1. 我们只会做最多一次变换操作。

证明：显然，多次变换操作可以合为一次。

2. 设这个序列有 A 个左括号，B 个右括号，那么必然存在一种变换方案，使得变换后有 \min(A,B) 组括号被匹配。换句话说，就是左括号和右括号中个数较少的全部被匹配到。

证明：不妨设 A \ge B，把左括号看作 1，右括号看作 -1，然后再得到一个前缀和数组 c。然后选择数组中最小值所在位置 x，通过变换使得 x 这个位置移到新序列的末尾。

如果有右括号没匹配上左括号，就说明存在一个位置 i 使得 c_i<0。

对于 x 之后的任意位置 y 都有 c_x<c_y，那么把 [x+1,n] 变换到序列开头，这部分必然使得整体的 c 数组增加。

而变换前 [1,x] 这部分在变换后的 c 值增加量是完全一致的（也就是变换前的 c_n-c_x）。因此 c_x（相当于变换后的 c_n）依然是这部分的最小值。又因为 A \ge B，我们可以知道 c_x 此时就是 A-B \ge 0。

因此结论得证。A < B 的情况是类似的，不再赘述。有了这两个性质，这题就可做了。因为我们发现如果一个序列的匹配数没有达到上界 \min(A,B) 的话，我们把它循环移位一下必然不劣。因此最后的答案就是 \sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} \lvert A[l, r] - B[l, r]\rvert+g(l,r)，其中 A,B 意义同上，g(l,r) 表示序列的匹配数是否达到上界（是为 0，不是为 1）。

• n \leq 400$，$\sum n \leq 800

暴力枚举 l,r，再暴力计算，时间复杂度 O(n^3)。

• n \leq 2\times 10^3$，$\sum n \leq 4\times 10^3

暴力枚举 l，r 从 l 开始向后拓展，在拓展的过程中维护括号匹配情况以及 A,B，计算 [l,r] 的贡献。时间复杂度 O(n^2)。

• 特殊性质：所有括号都是左括号

此时容易发现就是求 \sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} r-l+1。这就是 \sum\limits_{i=1}^n (n-i+1) \times i 啊。如果您是数学带师的话还可以直接看出这个东西就是 n+2 \choose 3（考虑组合意义）。

• 特殊性质：对于所有整数 1\le i < n，有 s_i \neq s_{i+1}

所有可能的子串只有四种形态：\texttt{()()} \cdots \texttt{()}，\texttt{)()} \cdots \texttt{()}，\texttt{)()} \cdots \texttt{()(} 和 \texttt{()()} \cdots \texttt{()(}。其中只有第三种 g(l,r)=1，容易做到线性计算。

• n \leq 2\times 10^5$，$\sum n \leq 5\times 10^5

此时我们再整理整理式子，让它变成 \sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} |c_r-c_{l-1}| + \sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} g(l,r)。

前面那个部分可以直接把 c 排序后快速计算 \sum\limits_{r=0}^{n} \sum\limits_{l=0}^{r} c_r-c_l 即可。对于后面那个，我们考虑把 g(l,r) 转化成更优秀的条件。

关键性质：g(l,r)=1 等价于：\min\{c_l,c_{l+1},\cdots,c_{r-1}\} < \min(c_{l-1},c_r)。

证明：