有效括号基础问题#

有效括号问题是一个非常经典的入门题型，它的核心在于刻画括号之间的 匹配关系 。一个合法的括号串，本质上由两种结构组成：第一种是 嵌套结构 ，即括号内部还包含完整的括号序列；第二种是 并列结构 ，即多个合法括号序列首尾相接。这两种结构的存在，使得我们在处理括号匹配问题时需要一种能够 “记住最近未匹配状态” 的数据结构，而栈正好满足这一需求。

我们可以将整个过程抽象为一种动态匹配过程：每遇到一个左括号，就相当于产生了一个待匹配项，需要在之后被某个右括号消去；而每遇到一个右括号，则尝试去匹配最近的一个尚未匹配的左括号。因此，我们可以将左括号视为入栈操作，将右括号视为出栈操作，从而用栈来模拟整个匹配过程。

在具体编写代码时，可以从非法情况入手理解整个过程。首先，如果在某一时刻遇到右括号，但此时栈为空，说明当前没有任何左括号可以与之匹配，这种情况称为 右括号多余 ，显然是不合法的。其次，即使在遍历过程中始终没有出现上述情况，如果在遍历结束后栈中仍然存在元素，则说明还有左括号未被匹配，这种情况称为 左括号多余 ，同样不合法。根据上面的思路，我们就可以写出如下的代码。

1
# include <bits/stdc++.h>
2
using namespace std;
3
string s;
4

5
int main(){
6
    cin >> s;
7

8
    stack<char> st;
9
    for (char c : s){
10
        if (c == '('){
11
            st.push(c);
12
        } else if (c == ')'){
13
            if (st.empty()){
14
                cout << "Invalid" << endl;
15
                return 0;
16
            }
17
            st.pop();
18
        }
19
    }
20

21
    if (st.empty()){
22
        cout << "Valid" << endl;
23
    } else {
24
        cout << "Invalid" << endl;
25
    }
26
}

这个代码同样可以扩展到 包含多种类型括号 的情形，例如 () 、[] 、{} 等。整体思路并没有改变：左括号入栈，右括号尝试与栈顶元素匹配。不同之处在于，我们需要额外判断括号类型是否对应，如果栈为空或类型不匹配，则说明当前括号串不合法。因此，在实现时只需为每种括号建立对应关系即可，当遇到右括号时检查其是否与栈顶左括号匹配，匹配成功则出栈，否则直接判定为非法。

1
# include <bits/stdc++.h>
2
using namespace std;
3
string s;
4

5
int main(){
6
    cin >> s;
7

8
    stack<char> st;
9
    for (char c : s){
10
        if (c == '(' || c == '[' || c == '{'){
11
            st.push(c);
12
        } else {
13
            if (st.empty()){
14
                cout << "Invalid" << endl;
15
                return 0;
16
            }
17

18
            char t = st.top();
19
            st.pop();
20

21
            if ((c == ')' && t != '(') ||
22
                (c == ']' && t != '[') ||
23
                (c == '}' && t != '{')){
24
                cout << "Invalid" << endl;
25
                return 0;
26
            }
27
        }
28
    }
29

30
    if (st.empty()) cout << "Valid" << endl;
31
    else cout << "Invalid" << endl;
32
}

不过在算法竞赛中，大多数题目仍然以 单一类型括号 为主。对于这类问题，我们没有必要使用栈来维护匹配关系，因为括号的类型是唯一的，我们只需要关心当前未匹配的左括号数量即可。因此可以用一个变量 bal 来代替栈：遇到左括号时令 bal++ ，遇到右括号时令 bal-- 。在遍历过程中必须始终保证 bal 不会小于 $0$ （否则说明出现了多余的右括号），并且在遍历结束后 bal 恰好等于 $0$ ，才能说明整个括号串是合法的。基于这一思路，可以将原本的栈做法优化为更简洁的计数实现。

1
# include <bits/stdc++.h>
2
using namespace std;
3
string s;
4

5
int main(){
6
    cin >> s;
7

8
    int bal = 0;
9
    for (char c : s){
10
        if (c == '('){
11
            bal++;
12
        } else if (c == ')'){
13
            bal--;
14
            if (bal < 0){
15
                cout << "Invalid" << endl;
16
                return 0;
17
            }
18
        }
19
    }
20

21
    if (bal == 0) cout << "Valid" << endl;
22
    else cout << "Invalid" << endl;
23
}

这种基于 balance 的处理方式具有很强的可拓展性，许多看似复杂的括号问题，本质上都可以转化为对这一变量的约束与维护。例如在 “判断任意区间是否为有效括号” 的问题中，我们不再关心整体是否合法，而是关注某一段区间的结构是否满足条件。这时可以将括号二值化（如左括号记为 $+1$ ，右括号记为 $-1$ ），从而把问题转化为区间和的性质分析。

最有价值的括号#

题目链接

Problem Statement#

给定一个长度为 $2N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_{2N})$ 。

对于一个长度为 $2N$ 的括号序列 $s$ ，定义其得分如下：

对于所有满足 $s_i = \texttt{')'}$ 的位置 $i$ ，将 $A_i$ 的值改为 $0$ ；
然后计算整个序列 $A$ 的元素总和。

也就是说，只有被选为 '(' 的位置对应的 $A_i$ 会被计入答案。

现在要求你在所有 合法括号序列 中，选择一个，使得得分最大，并输出这个最大值。

给定 $T$ 个测试用例，请分别求解。

一个合法括号序列的定义是：可以通过不断删除子串 "()" ，最终变为空串的字符串。

Constraints#

$1 \leq T \leq 500$
$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$
所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$

Input#

输入包含多个测试用例：

第一行包含一个整数 $T$ ，表示测试用例的数量。

$T$

$case_1$

$case_2$

$\ldots$

$case_T$

对于每个测试用例：

第一行包含一个整数 $N$ 。
接下来的 $2N$ 行，每行包含一个整数。

$N$

$A_1$

$A_2$

$\ldots$

$A_{2N}$

Output#

输出 $T$ 行，第 $i$ 行表示第 $i$ 个测试用例的答案。

Sample Input#

Sample Output#

1200
6000000000

题目要点解析#

对于这类结构复杂的有效括号问题，一个自然的切入点是从区间结构出发进行动态规划。由于合法括号序列本身具有明显的递归性质，一个完整序列可以表示为下面这个形式：

\big( \, \text{left} \, \big) \, \text{right}

我们可以尝试固定第一个左括号的位置，并枚举其匹配的右括号，从而将原问题划分为左右两个相互独立的子区间，形成典型的 “枚举划分点” 区间 DP 模型。由于在计算过程中需要对所有可能的匹配点进行枚举，该算法的复杂度高达 $O(n^3)$ ，即便进行一定的优化，其性能依然难以满足本题的数据要求，因此该思路在本题中并不可行。

既然从结构划分的角度难以突破，我们就换一个视角，从合法括号的判定条件入手。根据前面提到的 balance 思想，一个合法括号序列在任意前缀上都必须满足 balance ≥ 0 。将这一条件转化到本题中，可以理解为，在前 $i$ 个位置中，被选择为左括号的数量必须不少于 $\lceil i/2 \rceil$ ，否则一定会出现前缀失衡的情况。因此问题可以转化为一个带有前缀约束的选择问题，我们需要在满足约束的前提下，使被选中的元素权值之和尽可能大。

基于这一点，我们可以采用贪心策略来构造答案。随着位置 $i$ 从左到右推进，每当需要保证前缀合法性时，本质上就是 每经过两个位置，就必须新增一个左括号 。此时我们在当前已经出现的元素中选择一个权值最大的作为左括号，可以借助优先队列维护这些候选元素，每次在需要补充时取出最大值加入答案。通过这种方式，在保证所有前缀始终合法的同时，也尽可能让贡献最大的元素被选中，从而得到全局最优解。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int MAX = 4e5 + 200;
5
int T, N;
6
int a[MAX];
7

8
int main(){
9
    cin >> T;
10
    while(T--){
11
        cin >> N;
12
        for (int i = 0; i < 2 * N; i++){
13
            cin >> a[i];
14
        }
15

16
        ll ans = a[0];
17
        priority_queue<int> pq;
18
        for (int i = 0; i < N - 1; i++){
19
            pq.push(a[2 * i + 1]);
20
            pq.push(a[2 * i + 2]);
21
            ans += pq.top(); pq.pop();
22
        }
23

24
        cout << ans << endl;
25
    }
26
}

有效括号计数问题#

有效括号计数是算法竞赛中非常经典且常见的一类问题。它不仅涉及基础的字符串处理技巧，还常常与动态规划、栈以及组合数学等方法密切相关。理解这一类问题的核心，对于掌握算法思维和提升代码能力都有很大的帮助。在这一类问题中，我们通常可以将它们分为两种主要类型：有效括号子串计数 和 有效括号序列计数 。

这两类问题虽然名称相近，但在解题逻辑上却存在显著差异。前者本质上属于 字符串匹配问题 ，重点在于分析原始字符串中哪些片段能够构成合法的括号配对，通常需要借助栈结构或动态规划来实时维护匹配状态；后者则属于典型的 组合数学问题 ，核心在于依据约束条件计算所有合法序列的总数，这类问题通常采用递归、动态规划或卡塔兰数等数学公式进行推导，无需针对具体字符串进行逐一遍历。

最长有效括号子串#

在深入分析有效括号子串计数问题之前，可以先从 最长有效括号子串 的问题入手，这有助于理解处理括号匹配的一些关键思想。有效括号问题中有一个非常重要的思路是 balance 概念：任意前缀中左括号的数量不能少于右括号的数量。当某个前缀的 balance 小于 $0$ 时，说明从该位置开始到当前位置的括号序列无法形成有效子串，这个位置可以作为一个 分割点 。利用这一性质，可以有效划分字符串并进行匹配计算。

具体实现时，可以在栈中先放入一个 哨兵元素 -1 ，表示初始的分割点位置。随后按照常规的括号匹配方法遍历字符串，但需要对栈操作稍作修改：判断栈的大小而不是是否为空。当栈的大小仅剩 $1$ 时，说明当前的右括号对应的位置也是一个分割点，此时用当前下标更新栈底元素。通过这种方式，就可以正确地记录有效括号子串的起点和长度，从而求出最长有效括号子串。

1
#include <bits/stdc++.h>
2
using namespace std;
3
string s;
4

5
int main() {
6
    cin >> s;
7

8
    stack<int> stk;
9
    stk.push(-1); int ans = 0;
10
    for (int i = 0; i < s.size(); i++) {
11
        if (s[i] == '(') {
12
            stk.push(i);
13
        } else if (stk.size() > 1) {
14
            stk.pop();
15
            ans = max(ans, i - stk.top());
16
        } else {
17
            stk.top() = i;
18
        }
19
    }
20

21
    cout << ans << endl;
22
}

有效括号问题基本上也可以使用动态规划来解决，因此我们可以深入思考一下如何用 DP 来处理这个题目。对于子串类型的问题，有一个非常常见的状态设计方法，就是定义 dp[i] 来表示以下标 $i$ 结尾的子串的状态。具体到最长有效括号问题，我们自然可以定义 dp[i] 表示 以索引 i 结尾的最长有效括号子串的长度 ，即从字符串起始位置到下标 $i$ ，以 $i$ 为右端点的最长有效子串长度。

很显然，如果一个子串以左括号结尾，它不可能形成有效括号，因此在遇到左括号时，我们直接跳过这个位置，并将所有左括号对应位置的 dp[i] 设置为 $0$ 。右括号的处理才是关键。当一个右括号的前一个字符是左括号时，这意味着当前右括号就是于这个左括号直接匹配，形成一对有效括号。但此时 不能简单地认为以 该右括号结尾的有效括号子串就只包括这一对括号，因为它前面可能已经存在一个完整的有效括号子串等待与当前匹配的这一对括号并列。换句话说，我们不仅要考虑这一对括号本身，还要将它之前的有效括号长度累加到当前长度中，从而正确得到以 $i$ 结尾的最长有效括号子串长度。

当右括号的前一个字符也是右括号时，情况就更复杂了，此时我们需要找到与当前右括号匹配的左括号。显然，这个匹配的左括号下标为 j = i - dp[i-1] - 1 ，其中 dp[i-1] 正是中间包含的有效括号子串的长度。匹配到左括号之后，我们得到了一段新的有效括号子串，但同样不能忽略左括号左边可能存在的完整有效括号子串，它们同样会与当前子串并列，因此同样要把这部分长度累加进来。通过这种方式，动态规划可以同时处理 有效括号的嵌套结构（右括号匹配前一个左括号或中间子串）以及 并列结构（前面的有效括号与当前匹配子串累加），从而在遍历整个字符串后得到每个下标结尾的最长有效括号子串长度，保证了完整性和准确性。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MAXN = 2e4 + 100;
4
int dp[MAXN];
5
string s;
6

7
int main() {
8
    cin >> s;
9

10
    int ans = 0;
11
    for (int i = 0; i < (int) s.size(); i++) {
12
        if (s[i] == '(') continue;
13
        if (i > 0 && s[i - 1] == '(') {
14
            dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
15
        } else if (i > 0 && s[i - 1] == ')') {
16
            int j = i - dp[i - 1] - 1;
17
            if (j >= 0 && s[j] == '(') {
18
                dp[i] = dp[i - 1] + 2 + (j - 1 >= 0 ? dp[j - 1] : 0);
19
            }
20
        }
21
        ans = max(ans, dp[i]);
22
    }
23

24
    cout << ans << endl;
25
}

有效括号子串计数#

有效括号子串计数问题可以分为两类：一类是 只要位置不同的有效括号就算一个子串 ，另一类是 统计本质不同的有效括号子串 。前者关注的是 每个连续子串的位置组合 ，只要左右括号位置不同就算作不同的子串；后者关注的是 子串本身的内容是否不同 ，即相同内容的子串只算一次。由于两类问题的计算方式和复杂度差异较大，这里我们先专注于 第一类问题 ，即统计所有位置不重复的有效括号子串。

解决这个问题的思路可以借鉴 最长有效括号子串 的动态规划方法，但需要把重点从子串长度转移到子串数量。我们定义 dp[i] 表示 以下标 i 结尾的有效括号子串数量 。很显然，如果 s[i] 是左括号，则不可能形成有效子串，因此将 dp[i] 置为 $0$ 并跳过。当 s[i] 是右括号时，需要找到与其匹配的左括号下标 $j$ 。

我们可以用栈来优化匹配过程，栈中存储所有未匹配的左括号下标。当遇到右括号时，弹出栈顶左括号 $j$ ，形成一对新的有效括号子串。这里新增的子串数量为 $1$ ，表示当前匹配的这对括号本身。如果没有匹配的左括号，说明以当前右括号结尾不存在有效括号子串，同样直接跳过。

此外，我们还需要考虑有效括号中的 并列结构：如果左括号 $j$ 的左边存在已统计的有效括号子串，那么这些子串可以与当前新匹配的括号并列，形成更多的有效括号子串。因此，我们需要将左边的子串数量累加到当前计数中，得到以当前右括号结尾的总有效括号子串数量：

dp[i] = 1 + (j - 1 \geq 0 \, ? \, dp[j - 1] : 0)

遍历完字符串后，把每个 dp[i] 累加到全局答案 ans ，即可得到整个字符串中 所有位置不重复的有效括号子串总数 。这种方法能够同时处理嵌套和并列结构，保证每个右括号结尾的新有效子串都被正确统计。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MAXN = 2e4 + 100;
4
int dp[MAXN];
5
string s;
6

7
int main() {
8
    cin >> s;
9

10
    stack<int> stk;
11
    int ans = 0;
12
    for (int i = 0; i < (int) s.size(); i++) {
13
        if (s[i] == '(') {
14
            stk.push(i);
15
        }
16
        else if (!stk.empty()) {
17
            int j = stk.top(); stk.pop();
18
            dp[i] = 1 + (j - 1 >= 0 ? dp[j - 1] : 0);
19
            ans += dp[i];
20
        }
21
    }
22

23
    cout << ans << endl;
24
}

（另一个问题需要用到 SAM 去重，暂时不写）

最长有效括号序列#

为了更好地理解 有效括号序列计数问题 ，我们可以先从 最长有效括号序列 入手。与子串问题不同，序列问题的约束更加宽松，因为 不要求连续 ，只需要保持原本的顺序即可。因此，一个很自然的贪心策略就是：只要遇到可以匹配的右括号，就立即匹配 。对于无法匹配的右括号，直接忽略即可。

为什么这个贪心策略是正确的呢？因为有效括号序列的长度增长依赖于 左括号能找到匹配的右括号 。一旦遇到右括号，如果当前有可匹配的左括号，立即匹配不会亏损长度；如果当前没有多余的左括号，这个右括号本身无法做出任何贡献，直接跳过即可。换句话说，在子序列问题中，多余的右括号不会成为序列的分割点阻碍后续的匹配。因此我们只需用贪心策略匹配尽可能多的括号对，就能得到最长有效括号序列的长度。

1
#include <bits/stdc++.h>
2
using namespace std;
3
string s;
4

5
int main() {
6
    cin >> s;
7

8
    int left = 0;
9
    int ans = 0;
10
    for (char c : s) {
11
        if (c == '(') {
12
            left++;
13
        } else if (c == ')' && left > 0) {
14
            ans += 2;
15
            left--;
16
        }
17
    }
18

19
    cout << ans << endl;
20
}

另一种思路是使用区间动态规划。区间 DP 与有效括号问题有很大的联系 ，许多复杂的有效括号序列问题都可以通过区间 DP 得到启发。虽然对于这个问题而言，最优解并不是区间 DP，但这种方法仍然具有很强的启发意义，能够为解决更复杂的有效括号序列问题提供思路。

具体来说，我们可以考虑当前区间的 左端点 L 对应的左括号 应该与哪个右括号匹配。通过这种方式，可以将整个区间的结构拆解为下面这个形式：

\big( \, \text{left} \, \big) \, \text{right}

在此基础上，我们将区间 $[L, R]$ 划分为两个部分：第一个括号及其内部的有效区间 $[L+1, k-1]$ ，以及配对括号后的剩余区间 $[k+1, R]$ 。这种划分方式将原区间拆解为互不重叠的子结构，使得我们可以通过对子区间状态的组合运算得到最终答案。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MAX = 1e3;
4
int dp[MAX][MAX];
5
string s;
6

7
int main() {
8
    cin >> s;
9

10
    for (int len = 2; len <= (int) s.size(); len++) {
11
        for (int i = 0; i + len - 1 < n; i++) {
12
            int j = i + len - 1;
13
            if (s[i] == '(' && s[j] == ')') {
14
                dp[i][j] = dp[i+1][j-1] + 2;
15
            }
16
            for (int k = i; k < j; k++) {
17
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
18
            }
19
        }
20
    }
21

22
    cout << dp[0][n-1] << endl;
23
}

有效括号序列计数#

与有效括号子串计数问题类似，有效括号序列计数问题也可以分为两类：一类是统计 所有位置不同的有效括号序列 ，即使括号序列的内容相同，但其在原字符串中的位置不同，也视为不同的有效括号序列；另一类是统计 本质不同的有效括号序列 ，也就是相同内容的有效括号序列只统计一次。这里我们先讨论第一类问题，也就是统计所有位置不同的有效括号序列数量。

我们可以使用 区间 DP 来解决这一问题，对于任意区间 $[i, j]$ ，可以从该区间的左右端点括号是否匹配的角度来思考。如果左右端点不匹配（不管实际上能否匹配），则可以利用容斥原理，将整个区间拆解为较小的子区间进行处理，从而计算其有效括号序列的数量。计算公式如下：

dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

当左右端点恰好能够匹配时，这对首尾括号不仅能够独立闭合，直接形成一个最简的有效序列，同时它们还可以作为一层外壳，包裹住内部区间 $[i+1, j-1]$ 中已经存在的每一个合法子序列，使这些原有的序列在嵌套之后演变为全新且更长的有效方案。因此我们需要在容斥原理计算出的基础值之上，额外累加这部分新增的贡献。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int MAX = 1e3 + 100;
5
const int MOD = 1e9 + 7;
6
ll dp[MAX][MAX];
7
string s;
8

9
int main() {
10
    cin >> s
11

12
    for (int len = 2; len <= (int) s.size(); len++) {
13
        for (int i = 0; i + len - 1 < n; i++) {
14
            int j = i + len - 1;
15

16
            dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + MOD) % MOD;
17

18
            if (s[i] == '(' && s[j] == ')') {
19
                dp[i][j] = (dp[i][j] + dp[i + 1][j - 1] + 1) % MOD;
20
            }
21
        }
22
    }
23

24
    cout << dp[0][n - 1] << endl;
25
}

接下来我们考虑 本质不同的有效括号序列 问题。所谓 “本质不同” ，指的是括号序列的结构不同，而不考虑括号序列在原字符串中的具体位置。因此在设计具体的动态规划方案时，我们需要构建一个 与位置无关 的思路，而不能单纯依赖具体的区间或索引来定义状态。

在处理这类问题时，一个常用的策略是：假设在所有可能的选择中，总是优先选择最靠左的那一个括号 。举例来说，对于字符串 "(()))" ，如果我们考虑子序列 "(())" ，它的第二个右括号可以对应原字符串的第四个或第五个字符，但按照这个策略，我们总是优先选择第四个字符作为右括号。通过这个设定，我们就能在枚举组合时避免重复计数，从而确保每个有效括号序列只被计算一次。

引入这个 “最靠左优先” 的策略之后，传统的区间 DP 方法就难以直接应用。因为区间 DP 通常依赖于固定的区间边界，而无法表达 “在多个可选位置中优先选择最左侧” 的逻辑。为此，我们可以借用前面提到的 balance 思想来设计 DP 状态：定义 dp[i][j] 表示在处理到字符串第 $i$ 个字符时，当前左括号数量比右括号多 $j$ 个的有效序列数量，其中 $j$ 就是当前的 balance 值。这样 DP 的状态就不依赖于具体位置，从而满足本质不同的要求。

为了方便状态转移，我们可以先预处理出每个位置的下一个左括号和下一个右括号的位置，生成两个数组 nextL 和 nextR 。在 DP 转移时，如果选择添加一个左括号，就从 nextL[i] 找到下一个可用的左括号，然后将 dp[i][j] 累加到 dp[nextL[i]][j + 1] 上；如果选择添加右括号，则从 nextR[i] 找到下一个可用的右括号，将 dp[i][j] 累加到 dp[nextR[i]][j - 1] 上，但前提是 j > 0 ，也就是当前有足够的左括号与之匹配。

最终，我们只需要累加所有 dp[i][0] 的值，就可以得到整个字符串中所有本质不同的有效括号序列的数量。这个方法通过结合 balance 和 “最左优先” 的策略，既避免了重复计数，又实现了与位置无关的精确统计。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int MAX = 1e3 + 100;
5
const int MOD = 1e9 + 7;
6
ll dp[MAX][MAX];
7
int nxtL[MAX], nxtR[MAX];
8
string s;
9

10
int main() {
11
    cin >> s; int n = s.size();
12

13
    // 为了方便起始跳转，我们从一个虚拟的起点开始考虑
14
    int lastL = -1, lastR = -1;
15
    vector<int> nL(n + 1, -1), nR(n + 1, -1);
16
    for (int i = n - 1; i >= 0; i--) {
17
        if (s[i] == '(') lastL = i;
18
        if (s[i] == ')') lastR = i;
19
        nL[i] = lastL;
20
        nR[i] = lastR;
21
    }
22

23
    // 初始状态：从原串最左侧尝试开启序列
24
    if (nL[0] != -1) {
25
        dp[nL[0]][1] = 1;
26
    }
27

28
    for (int i = 0; i < n; i++) {
29
        for (int j = 0; j <= n; j++) {
30
            if (dp[i][j] == 0) continue;
31

32
            // 尝试添加左括号：跳到 i 之后的第一个 '('
33
            if (i + 1 < n && nL[i + 1] != -1) {
34
                int p = nL[i + 1];
35
                dp[p][j + 1] = (dp[p][j + 1] + dp[i][j]) % MOD;
36
            }
37

38
            // 尝试添加右括号：前提是 j > 0，跳到 i 之后的第一个 ')'
39
            if (j > 0 && i + 1 < n && nR[i + 1] != -1) {
40
                int q = nR[i + 1];
41
                dp[q][j - 1] = (dp[q][j - 1] + dp[i][j]) % MOD;
42
            }
43
        }
44
    }
45

46
    ll ans = 0;
47
    for (int i = 0; i < n; i++) {
48
        ans = (ans + dp[i][0]) % MOD;
49
    }
50

51
    cout << ans << endl;
52
}

子序列括号得分#

题目链接

Problem Statement#

对于一个括号序列 $t$ ，定义其 score 如下：

如果 $t$ 不是一个合法括号序列（Regular Bracket Sequence, RBS），则其分数为 $0$ 。
如果存在一个合法括号序列 $r$ ，且 $r$ 比 $t$ 更好，则其分数为所有满足条件的 $r$ 中 $|r|$ 的最大值。
否则，分数为 $0$ 。

若括号序列 $a$ 比 $b$ 更好，当且仅当满足以下条件之一：

$b$ 是 $a$ 的前缀，且 $a \neq b$ 。
令 $i$ 为第一个 $a_i \neq b_i$ 的位置，则 $a_i = \text{'('}$ 且 $b_i = \text{')'}$ 。

简单来说， $t$ 的分数是所有优于 $t$ 的合法括号子序列中，长度最长的那个的长度。给定一个长度为 $n$ 的括号序列 $s$ ，求其所有非空子序列的分数之和，结果对 $998244353$ 取模。

Constraints#

$1 \leq t \leq 30$
$1 \leq n \leq 100$
所有测试用例中 $n$ 的总和不超过 $100$

Input#

输入包含多行：

第一行包含一个整数 $t$ ，表示测试用例的数量。
对于每一组测试用例：
- 第一行包含一个整数 $n$ 。
- 第二行包含一个长度为 $n$ 的字符串 $s$ 。

$t$

$n$

$s$

$\ldots$

$n$

$s$

Output#

输出 $t$ 行，每行一个整数，表示该测试用例中所有子序列的分数之和，结果对 $998244353$ 取模。

Sample Input#

5
1
(
6
()()()
6
(())()
8
(())()()
22
()()())()()(()()()((()

Sample Output#

题目要点解析#

有效括号区间问题#

在处理 有效括号的区间问题 时，传统的栈方法就不再适用了。原因有两点：首先，栈的做法依赖于从左到右的顺序处理括号，这不适合 在线查询 ；其次，栈本质上只能处理单个序列的匹配情况，而无法快速回答任意区间是否为有效括号序列。为此，我们需要重新回到前面提到的 balance 思路来分析问题。

在 balance 的视角下，区间 $[l, r]$ 要想构成有效括号序列，当且仅当满足以下两个条件：首先是区间两端的 balance 值必须相同，即 balance[l-1] = balance[r] ，这保证了整个区间括号数匹配，使得序列整体达到平衡状态；其次是区间内部所有位置的 balance 值都必须大于或等于两端的 balance 值，也就是 区间内部的 balance 不能低于端点的 balance ，这保证了括号不会出现右括号多余的非法情况。

结合这两个条件，可以得到一个关键结论：区间的最小 balance 必须等于区间两端的 balance 值 。换句话说，如果我们能快速查询某个区间 $[l, r]$ 内的最小 balance ，就可以判断这个区间是否为有效括号区间。这正好启发我们使用 线段树 来维护区间最小值，并且线段树还可以高效地处理区间最小值的查询和更新，从而满足大批量在线查询的需求。通过这种方法，我们就能够在 balance 的框架下高效解决有效括号的区间问题。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int MAXN = 1e5 + 10;
5
int balance[MAXN];
6
int seg[4 * MAXN];
7
string s;
8

9
// 构建线段树，维护区间最小值
10
void build(int node, int l, int r) {
11
    if (l == r) {
12
        seg[node] = balance[l];
13
        return;
14
    }
15
    int mid = (l + r) / 2;
16
    build(node*2, l, mid);
17
    build(node*2+1, mid+1, r);
18
    seg[node] = min(seg[node*2], seg[node*2+1]);
19
}
20

21
// 查询区间 [ql, qr] 的最小值
22
int query_min(int node, int l, int r, int ql, int qr) {
23
    if (qr < l || ql > r) return INT_MAX;
24
    if (ql <= l && r <= qr) return seg[node];
25
    int mid = (l + r) / 2;
26
    return min(query_min(node*2, l, mid, ql, qr),
27
               query_min(node*2+1, mid+1, r, ql, qr));
28
}
29

30
// 判断区间 [l, r] 是否为有效括号区间
31
bool is_valid(int l, int r) {
32
    if (balance[l] != balance[r+1]) return false; // 两端 balance 必须相同
33
    int mn = query_min(1, 0, s.size(), l+1, r+1);
34
    return mn >= balance[l]; // 区间内最小 balance >= 左端点 balance
35
}
36

37
int main() {
38
    cin >> s;
39
    int n = s.size();
40
    balance[0] = 0;
41
    for (int i = 0; i < n; i++) {
42
        balance[i+1] = balance[i] + (s[i] == '(' ? 1 : -1);
43
    }
44

45
    // 构建线段树
46
    build(1, 0, n);
47
    vector<pair<int,int>> queries = { {0, n-1}, {0, 1}, {1, 4}, {2, 5} };
48
    for (auto q : queries) {
49
        int l = q.first, r = q.second;
50
        cout << (is_valid(l,r) ? "Yes" : "No") << endl;
51
    }
52
}

如果我们在括号序列上增加 区间反转操作 ，上述基于 balance + 线段树的方法就难以直接使用。原因在于，反转操作会改变区间内括号的顺序，从而使原本依赖左右端点 balance 的判定逻辑失效。为了处理这种情况，我们需要重新思考括号区间的结构，寻找一种能够在 合并和反转操作下仍然保持正确性的表示方法 。

一种自然的思路是考虑 匹配括号的归约 。对于任意一个括号串，如果我们不断地删除 '()' 子串，最终剩下的部分一定是一个非常简单的结构：所有未匹配的右括号都在左侧，所有未匹配的左括号都在右侧。换句话说，经过完全匹配删除后的字符串一定是形如 ")))(((" 的格式：左侧是若干 ')' ，右侧是若干 '(' 。这个观察提供了一种非常方便的表示方法：对于每个区间，我们只需要记录 左边剩余的右括号数量 和 右边剩余的左括号数量 。

在此基础上，区间的合并操作也变得自然。假设我们有两个相邻区间 A 和 B ，各自记录了剩余右括号和剩余左括号。合并时，A 区间右边的未匹配左括号和 B 区间左边的未匹配右括号可以互相抵消，因为它们可以组成新的 '()' 匹配对。抵消后的多余部分仍然作为新的未匹配括号加入合并后的区间表示中。通过这种方式，我们就能在合并时保持对区间未匹配括号的精确统计，而不依赖于原始顺序或具体位置。

这个表示方法最大优点在于，它天然支持 区间反转操作 。当一个区间被反转时，只需要交换 “左边的未匹配右括号” 和 “右边的未匹配左括号” 这两个统计值，就能正确反映反转后的状态，而不必重新计算整个区间 balance 或最小值。这使得我们可以在 线段树 中高效实现区间反转，同时仍然能够快速合并子区间或判断区间有效性。

在此基础上，如果我们想要计算一个区间的 最长有效括号序列长度 ，方法也非常直观：假设区间长度为 len ，左边剩余的右括号数量为 L ，右边剩余的左括号数量为 R ，那么区间内未匹配的括号总数就是 L + R 。由于这些未匹配的括号无法构成有效匹配，其余的括号都能形成匹配对。因此，区间内的最长有效括号序列长度就是：

\text{maxValidLen} = \text{intervalLen} - (L + R)

这个公式非常简洁，而且可以在区间反转操作后快速更新，从而保证了我们可以在 $O(\log n)$ 的时间复杂度下维护和查询任意区间的最长有效括号序列长度。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
int main() {
6

7
}

有效括号基础问题#

最有价值的括号#

Problem Statement#

Constraints#

Input#

Output#

Sample Input#

Sample Output#

题目要点解析#

有效括号计数问题#

最长有效括号子串#

有效括号子串计数#

最长有效括号序列#

有效括号序列计数#

子序列括号得分#

Problem Statement#

Constraints#

Input#

Output#

Sample Input#

Sample Output#

题目要点解析#

有效括号区间问题#

参考文献列表#