原题呈现

P9356 Bracket#

题目描述#

Mirika 有一个长度为 $n$ 的括号序列 $s$ ．

对于一个括号序列 $S$ ，Mirika 可以执行两种操作：

变换：选择一个位置 $i$ 满足 $1 \leq i \leq \lvert S \rvert$ ，使得 $S$ 变为 $S_iS_{i+1}\cdots S_{\lvert S\rvert}S_1S_2\cdots S_{i-2}S_{i-1}$ ．
插入：在这个序列的 任意位置 插入一个括号（左右括号均可）．

Mirika 定义括号序列 $S$ 的权值 $f(S)$ 为能将这个括号序列变成一个合法括号序列所需的最小操作数．

其中，合法括号序列的定义为：

空串为合法括号序列．
若 $\texttt A$ 为合法括号序列，则 $\texttt{(A)}$ 为合法括号序列．
若 $\texttt A, \texttt B$ 均为合法括号序列，则 $\texttt{AB}$ 也为合法括号序列．

现在 Mirika 想要求出：

$\sum_{l=1}^n \sum_{r=l}^n f(s[l,r])$

其中 $s[l,r]$ 表示由 $s_l,s_{l+1},\cdots,s_r$ 形成的连续子序列．

但是 Mirika 太菜了不会算，于是只好求助于你．

输入格式#

本题每个测试点内有多组数据．

第一行一个正整数 $T$ 表示测试数据组数．

对于每组数据，第一行一个正整数 $n$ ．

第二行一个长度为 $n$ 的括号序列 $s$ ．

输出格式#

输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案．

输入输出样例 #1#

输入 #1#

1
5
2
2
3
((
4
4
5
())(
6
5
7
()(()
8
5
9
()()(
10
15
11
()())(())))()()

输出 #1#

说明/提示#

样例解释#

对于 $s = \texttt{())(}$ ：

考虑 $s[1,4]=\texttt{())(}$ ．执行变换操作 $i=4$ ，有 $\texttt{())(} \Rightarrow \texttt{(())}$ ，其中 $\texttt{(())}$ 是合法括号序列，故 $f(s[1, 4]) = 1$ ．可以证明不存在更优的策略．
考虑 $s[2,4]=\texttt{))(}$ ．执行变换操作 $i=2$ ，再在序列开头插入一个左括号，有 $\texttt{))(} \Rightarrow \texttt{)()} \Rightarrow \texttt{()()}$ ，其中 $\texttt{()()}$ 是合法括号序列，故 $f(s[2, 4]) = 2$ ．可以证明不存在更优的策略．

数据规模与约定#

本题采用捆绑测试．

Subtask 0（15 pts）： $n \leq 400$ ， $\sum n \leq 800$ ．
Subtask 1（20 pts）： $n \leq 2\times 10^3$ ， $\sum n \leq 4\times 10^3$ ．
Subtask 2（5 pts）： $s$ 内不含有右括号．
Subtask 3（10 pts）：对于所有整数 $1\le i < n$ ，有 $s_i \neq s_{i+1}$ ．
Subtask 4（30 pts）： $n \leq 2\times 10^5$ ， $\sum n \leq 5\times 10^5$ ．
Subtask 5（20 pts）：无特殊限制．

对于所有数据， $1 \leq T \leq 10000$ ， $1 \leq n \leq 2 \times 10^6$ ， $1 \leq \sum n \leq 2 \times 10^7$ ．

小技巧：快速判断括号序列的合法性

对于一个括号序列 $T$ ，长度为 $m$ ，若将其左括号视作 1，右括号视作 -1，将这个序列做一次前缀和，得到 $s$ 数组：

$s_0 = 0$ ，是一个空串
$s_i$ 表示括号序列遍历到第 $i$ 个括号时，栈中的左括号个数

因此，对于括号序列 $T$ ， $T$ 是合法的当且仅当：

$s_m = 0$
$\forall i, s_i \geq 0$

对于括号序列 $T$ ，一个 $T$ 的子串 $[l,r]$ 是合法的，当且仅当以下条件全部满足：

$s_r=s_{l-1}$
$s_r$ 是 $s_{l..r}$ 中的最小值

对于一个括号序列 $T$ ，长度为 $m$ ，若将其左括号视作 1，右括号视作 -1，将这个序列做一次前缀和，得到 $s$ 数组：

s[0] = 0，是一个空串
s[i] 表示括号序列遍历到第 $i$ 个括号时，栈中的左括号个数则一个 $T$ 的子串 $[l,r]$ 是合法的，当且仅当以下条件全部满足：
$s_r=s_{l-1}$
$s_r$ 是 $s_{l..r}$ 中的最小值

由于 $f(T)$ 为通过循环移位和插入括号变成合法括号序列的最少操作数，则有：

若 $s_1$ 是前缀和数组中最小的，则所需操作数为 $|s_m|$ ，即在末尾补充 $|s_m|$ 个右括号．
若 $s_m$ 是前缀和数组中最小的，则所需操作数为 $|s_m|$ ，即在开头补充 $|s_m|$ 个左括号．
否则，需要先循环移位一次，转换为上面两种情况，再补充括号，所需操作数 $|s_m| + 1$

因此，可以将子串的贡献拆分为所有子串的 $|s_m|$ 的部分和部分子串所需 1 的部分．

$|s_m|$ 的部分#

$|s_m|$ 的部分的贡献为：

\sum_{l=1}^{m}\sum_{r=l}^{m} |s[r]-s[l-1]|

将两个和式化简，得：

\sum_{0\leq i<j\leq m} |s[j]-s[i]|

注意，这里 $i=l-1$ ．

将 $s$ 数组排序，就可以消去绝对值，变成下面的形式（注意：这里需要桶排）：

\sum_{0\leq i<j\leq m} s[j]-s[i]

接着，遍历每一个元素，将这一个元素和前面每一个元素进行配对，具体来说，若遍历到的当前元素前面还有 $i$ 个元素，则当前元素会配成 $i$ 对，贡献为 $(s[i + 1] - s[i]) + (s[i+1]-s[i-1]) + (s[i+1]-s[i-2]) + \cdots + (s[i+1]-s[1])$

可以化简为： $s[i-1] \times i + s[1] + s[2] + \cdots + s[i]$

可以维护当前前缀和来 $O(n)$ 解决．

1 的部分#

正难则反，只需要算出不需要 +1 的子串，剩下的就是需要 +1 的子串．

通过上面规律分析我们可以知道，一个子串不需要 +1，当且仅当以下条件满足其一：

该子串左端点在该字串范围前缀和数组中取到最小值
该子串右端点在该字串范围前缀和数组中取到最小值

观察可知，这两个条件对称，只需要反转序列，并将左右括号对调，就可以将第二个问题条件转化为第一个条件．

定义 $p[i]$ 为左端点 $l=i-1$ 右边第一个位置 $r$ ，满足 $s[r+1]$ 小于 $s[i]$ （注意，位置和 p 数组下标是 0-based，而 s 数组下标是 1-based）．可以使用从小到大的单调栈进行维护．

求出 $p[i]$ 之后，左端点 $l$ 的右端点就可以取 $i+1,i+2,\cdots,p[i]-1$ ，一共是 $p[i]-i-1$ 种情况，将其作为负贡献计入总和．

容斥掉合法子串#

不难发现，合法子串同时满足上面两个条件，因此合法子串会被算两次，要扣除重复的部分，就要知道有多少合法子串．

回顾上面的规律，我们知道，一个子串 $[l,r]$ 是合法序列，当且仅当以下两个条件全部满足：

首尾相等： $s[l-1] = s[r]$
$s[l-1]$ 是当前区间最小值

我们将所有的 $s$ 放到一个桶 $bucket$ 中，桶里存放每个元素的下标， $s$ 的值域为 $[-n, n]$ ，可以偏移为 $[0, 2n]$ ．

枚举每一个值 $x$ ，遍历下标数组 $pos=bucked[x]$ ，对于每一个下标 $u$ （即为左端点 -1），找到所有的 $v$ （即为右端点）满足 $u<v$ 且 $v < p_u$ （使得 $s[u]$ 是当前区间最小值），其中， $u,v\in pos$ ．

在程序中，我们使用双指针，使用一个指针 $ptr$ 指向 $pos$ 中的元素，初始为 0，用于记录当前第一个不满足条件的 $v$ ．遍历元素 $pos[i]$ 时：

移动双指针，直到移动到 $pos$ 边界，或 $pos[ptr] > p_{pos[i]}$ ．
此时，所有可能的右边界为： $i+1,i+2,\cdots,ptr$ ，共有 $ptr-i-i$ 个，将其作为贡献计入总和．

最终答案为：

S_{|s_m|} +T-S_{1} +S_g

其中：

$S_{|s_m|}$ 为 $|s_m|$ 的部分的贡献．
$T$ 为子串数， $T=\frac{(m+1)m}{2}$ ．
$S_1$ 为上述不需要 +1 的子串数量．
$S_g$ 为 $S_1$ 计算中被重复计数的合法子串数量．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N = 2e6 + 100;
5
int n, s[N], p[N], rs[N], rp[N];
6
ll ans;
7
string str;
8

9
// s[i] := sum{ str[0] ~ str[i-1] }
10

11
ll solve_1(int *s, int *p) {
12
    ll ans = 0;
13
    stack<pair<int, int>> sta;
14
    for (int i = 0; i <= n; i++)
15
        p[i] = n + 1;
16
    for (int i = 0; i <= n; i++) {
17
        while (!sta.empty() && sta.top().first > s[i]) {
18
            int ele = sta.top().second;
19
            sta.pop();
20
            p[ele] = i;
21
        }
22
        sta.push({s[i], i});
23
    }
24
    for (int i = 0; i < n; i++) { // i 表示左端点的前一个位置
25
        ans += p[i] - 1 - i;
26
    }
27
    return ans;
28
}
29

30
void solve() {
31
    ans = 0;
32
    cin >> n >> str;
33
    vector<int> cnt((n << 1) + 1, 0);
34
    cnt[s[0] + n] = 1;
35
    for (int i = 1; i <= str.size(); i++) {
36
        s[i] = s[i - 1] + (str[i - 1] == '(' ? 1 : -1);
37
        cnt[s[i] + n]++;
38
    }
39
    // 计算 |Sn| 的部分
40
    vector<int> vec;
41
    for (int i = 0; i <= n << 1; i++) {
42
        for (int j = 1; j <= cnt[i]; j++)
43
            vec.push_back(i - n);
44
    }
45

46
    ll pref = 0;
47
    for (int i = 0; i < vec.size(); i++) {
48
        ans += 1ll * vec[i] * i - pref;
49
        pref += vec[i];
50
    }
51

52
    // 计算 1 的部分
53
    ll tot = (1ll * n * (n + 1)) >> 1;
54
    // 左边取到最小，p[i] := 下标为i后边第一个小于s[i]的值的下标
55
    tot -= solve_1(s, p);
56
    // 右边取到最小
57
    string rstr = str;
58
    reverse(rstr.begin(), rstr.end());
59
    for (int i = 1; i <= rstr.size(); i++) {
60
        rs[i] = rs[i - 1] + (rstr[i - 1] == '(' ? -1 : 1);
61
    }
62
    tot -= solve_1(rs, rp);
63

64
    // 去重
65
    vector<vector<int>> bucket(n * 2 + 1);
66
    for (int i = 0; i <= n; i++) {
67
        bucket[s[i] + n].push_back(i);
68
    }
69
    for (int x = 0; x <= n << 1; x++) {
70
        int ptr = 0;
71
        for (int i = 0; i < bucket[x].size(); i++) {
72
            vector<int> &pos = bucket[x];
73
            while (ptr < pos.size() && p[pos[i]] > pos[ptr])
74
                ptr++;
75
            tot += ptr - 1 - i;
76
        }
77
    }
78

79
    cout << ans + tot << endl;
80
}
81

82
signed main() {
83
    freopen("bracket.in", "r", stdin);
84
    freopen("bracket.out", "w", stdout);
85
    ios::sync_with_stdio(false);
86
    cin.tie(0);
87
    cout.tie(0);
88
    int T;
89
    cin >> T;
90
    while (T--) {
91
        solve();
92
    }
93
}

对于括号，可以将其视为一串只含有 $\pm 1$ 的序列，并通过下标从 0 开始的前缀和解决问题．

音乐

音乐

P9356 Bracket#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例解释#

数据规模与约定#

$|s_m|$ 的部分#

1 的部分#

容斥掉合法子串#

文章分享

音乐

安吉D2-T4

P9356 Bracket#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

样例解释#

数据规模与约定#

∣sm∣|s_m|∣sm​∣ 的部分#

1 的部分#

容斥掉合法子串#

文章分享

$|s_m|$ 的部分#