1. 先把题目读懂：什么是“永远在一起”
上个月我们这边打了一场月赛，T2 就是这道 P15445，题面起了个非常文艺的名字叫“永远在一起”。我当时看到这个名字愣了一下，读完题意才发现，它本质上是在问括号匹配的问题：给你一个只包含(和)的字符串，统计里面有多少个连续子串是合法的括号序列。
为什么叫“永远在一起”呢？你可以这么理解：一对左右括号一旦匹配成功，它们的位置关系就固定了，中间不能再被拆散；而一个合法的括号子串，就是一段内部所有括号都“成双成对、永不分离”的区间。
先把题意整理成下面这个版本，方便后面推导：
给定一个长度为 n 的字符串 s，s 中只包含
(和)。 统计 s 中所有连续子串里，有多少个是合法括号序列。 合法括号序列的定义就是标准的括号匹配：空串合法；若 A 合法，则(A)合法；若 A、B 合法，则 AB 合法。 数据范围：n ≤ 10^6，答案可能很大，需要用 64 位整数存储，结果不需要取模。
这道题适合两类人看：一类是刚学完栈和动态规划，想看看这两个东西怎么配合的初学者；另一类是准备算法竞赛，想练一练“把暴力观察转化成线性 DP”思维的选手。
我当时在考场上第一反应是“这题拿个栈扫一遍不就行了”，结果写着写着发现不对劲：传统的括号匹配只是判断整个串是否合法，而这题要求数出所有合法子串的数量，这两件事差得还挺远的。后来冷静下来重新分析，才找到了比较漂亮的线性做法。这篇博客就把完整的思路、推导、代码、坑位一次讲清楚。
1.1 先明确一个容易混淆的点
很多人在读题的时候会下意识把“合法子串”理解成“合法连续区间”，这没问题，但要注意它和“匹配对数”的区别。
比如()()这个串，它有 4 个合法子串吗？不对，你数一下：
- 第一个
()：下标 1 到 2 - 第二个
()：下标 3 到 4 - 整个
()()：下标 1 到 4
一共 3 个。注意空串不算，所以不能把空串数进去。
这个例子告诉我们：不能只统计有多少个“括号对”，因为相邻的合法段会拼成新的合法子串。这个“拼接”性质是整个 DP 的核心，也是暴力做法容易漏算或者重复算的地方。
1.2 题目本质是什么
把合法括号子串这个事情翻译一下，其实就是一个区间[l, r]满足三个条件：
s[l] == '('且s[r] == ')'，要不然不可能合法；- 区间内左括号和右括号数量相等；
- 区间任意前缀中，左括号数量不少于右括号数量。
第 1 和第 2 条都好理解，第 3 条是括号序列的“前缀非负”性质，也就是扫描过程中永远不能让右括号比左括号先多出来。这个必要条件可以独立判断，但是直接拿它去枚举区间，复杂度是下不来的。
所以问题的难点在于：怎么把“所有区间”这个指数级或平方级的概念，压缩成线性扫描可以维护的东西。
2. 从暴力到正解：两种思路的取舍
2.1 暴力枚举：拿到部分分很简单
先不要急着上正解，暴力枚举是最直观的起点。
最简单的写法是枚举左端点l，然后向右扩展右端点r，用一个计数器cnt来维护当前区间[l, r]内左右括号的差值：
- 遇到
(，cnt++； - 遇到
)，cnt--； - 如果
cnt < 0，说明这个左端点往后的区间都不可能合法了，直接剪枝跳出； - 如果
cnt == 0，就说明区间[l, r]合法，答案加一。
这个暴力的时间复杂度是 O(n^2)，因为枚举了所有左端点和右端点。n ≤ 500的点能轻松过，n ≤ 2000的点用剪枝也能勉强跑。但如果数据范围升到10^6，这个复杂度是不可接受的。
不过暴力代码有一个非常大的作用：它可以当对拍器。写正解之前，先写一个暴力版本，生成随机小数据去验证正解的正确性。这个习惯在考场上能救你命，后面我会细说。
2.2 为什么不能用前缀和直接搞定
很多人会想：我用前缀和数组pre[i]表示前 i 个字符里(的数量减去)的数量，然后判断区间[l, r]是否合法，就只需要看pre[r] - pre[l-1] == 0。这样 O(1) 判断数量相等，不就能 O(n^2) 枚举了吗？
这个思路的一半是对的。前两条条件的确认可以用前缀和做到 O(1)，但第三条“任意前缀不低于左端点”做不到。
举个例子：s = ")(()"，前缀和数组自己算一下：
- pre[0] = 0
- pre[1] = -1 （读到
)，减 1） - pre[2] = 0 （读到
(） - pre[3] = 1 （读到
(）
你要判断区间[2, 2]，pre[2]-pre[1] = 0 - (-1) = 1，这不是 0，不合法，没问题。但区间[3, 3]也是一个(，也不合法。再看区间[1, 2]，这一段的 pre 差值是pre[2]-pre[0] = 0 - 0 = 0，数量相等，但它是)(，显然不合法，因为第一个字符就是右括号。
所以只靠前缀和做差值，完全无法捕捉“区间内部某个前缀变成负数”的信息。你必须额外维护区间最小值，而这是一个范围查询问题，用单调栈或线段树可以做，但复杂度已经上去了，而且代码复杂度很高。月赛 T2 通常不该用这么重的数据结构，这说明肯定有更简单的方法。
2.3 核心观察：合法子串可以按“右端点”分类
我最后想到的方法是分而治之：按右端点分类，只统计以每个位置 i 结尾的合法子串数量，最后累加。
设dp[i]表示以s[i]结尾的合法括号子串的数量。
如果s[i] == '('，那不可能有以它结尾的合法子串，因为合法括号序列一定以)结尾，所以dp[i] = 0。
如果s[i] == ')'，它必须先找一个左括号跟它配对。这个左括号是哪个？用栈来维护。
这里的关键是：栈里存的不是字符，而是下标。每遇到一个(，就把它的下标压入栈；每遇到一个)且栈不为空，就弹出栈顶下标，记为m，表示s[m]和s[i]配成了一对。
当这一对匹配成功后，我们得到了一个以s[m]开头、s[i]结尾的合法括号对，也就是子串s[m...i]。但合法子串不止这一个。
如果m-1的位置也是一个合法段的结尾，那s[m...i]前面接上那一整段，拼起来的整体也仍然是一个合法括号序列。比如()()里，第二个)匹配的m = 3，而m-1 = 2恰好是以s[2]结尾的合法段()的结尾，于是拼接成()()，也是合法子串。
所以递推式就出来了：
dp[i] = dp[m - 1] + 1其中m是与s[i]匹配的左括号下标。
为什么加 1？因为s[m...i]本身就是一个合法的括号对，它是一个新的、只算一次的合法子串。dp[m-1]能提供的是所有能拼接到这一对前面的合法段数量。两者相加，正好是所有以 i 结尾的合法子串数。
还是拿()()验证。s[2] 匹配 m=1，dp[2] = dp[0] + 1 = 1，对应(1,2)。s[4] 匹配 m=3，dp[4] = dp[2] + 1 = 2，对应(3,4)和(1,4)。加起来是 3，和手数一致。
2.4 再往前一步：连续的合法括号段
上面这个 DP 本质上已经把“拼接”处理掉了，但它背后还有一个更朴素的视角：我们可以把原串划分成若干个“连续的合法括号段”。
比如()(())整体是一个合法段。如果我们把这个串拆开看，(())内部又嵌了一个()。这个嵌套关系在栈匹配的过程中会自然浮现出来，而 DP 公式里的dp[m-1] + 1正好是在处理嵌套和拼接两种情况的统一表达。
当你遇到内层的)先匹配成功，再遇到外层的)匹配成功，外层的dp = dp[内层配对的前一个位置] + 1，这个加 1 对应的就是外层的那个最大的括号对。嵌套和拼接通过同一个公式被统一了，这就是这题最精妙的地方。
3. 完整代码实现：30分钟能写完的 AC 代码
3.1 核心代码（C++17 注释版）
先把正解代码贴出来。整体非常短，核心循环就十几行。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 5; char s[MAXN]; long long f[MAXN]; int stk[MAXN]; int main() { int n; scanf("%d", &n); scanf("%s", s + 1); int top = 0; long long ans = 0; for (int i = 1; i <= n; i++) { if (s[i] == '(') { stk[++top] = i; f[i] = 0; } else { if (top == 0) { f[i] = 0; } else { int m = stk[top--]; f[i] = (m > 1 ? f[m - 1] : 0) + 1; ans += f[i]; } } } printf("%lld\n", ans); return 0; }这个代码有几个细节值得停下来看：
stk数组手写栈，效率比std::stack高一点，而且下标访问方便，调试也直观。f[i]只在实际匹配成功的时候才更新。匹配失败或者遇到(时，f 保持 0，不参与答案累计。m是配对的左括号下标，m - 1必须大于 0 才去查f[m-1]，否则越界。
3.2 代码各部分的职责拆解
先看压栈分支：遇到(，直接把当前位置压进去，同时把f[i]置 0。因为任何以左括号结尾的合法子串数量都是 0，后续匹配成功时需要用这个位置作为m。
再看弹栈分支：遇到)，先检查栈是不是空的。如果空，说明这个右括号没有可配对的左括号，那么以它结尾的合法子串数量就是 0，后续也没必要继续操作。
如果栈不空，弹出栈顶得到m。注意：这里m一定小于当前i，并且s[m]一定是(。此时我们不仅确定了一个新的配对，还可能顺着这个配对往前拼接。
f[m - 1]的含义要再说清楚：它表示的是所有以s[m-1]结尾的合法子串数。m-1这个位置有两种可能：
- 如果
s[m-1]是)，那它可能属于一个合法段的结尾，此时f[m-1]不为 0，于是(s[m-1]之前的合法段) + s[m...i]就拼成一个更长的合法子串。 - 如果
s[m-1]是(或者不存在，那么f[m-1]是 0，不会产生错误拼接。
这个设计的巧妙之处就是把“前面的合法内容”全部压缩成一个数值，避免了在匹配成功后再回头扫描一遍前面的内容，从而把整体复杂度压到了线性。
3.3 验证样例与边界测试
不要拿到代码就提交，先在本地跑几组数据。
第一组就是刚才说的()()：
4 ()()运行过程（手动推一下）：
- i=1，s[1]='('，压入 1
- i=2，s[2]=')'，弹出 m=1，f[2] = f[0] + 1 = 1，ans=1
- i=3，s[3]='('，压入 3
- i=4，s[4]=')'，弹出 m=3，f[4] = f[2] + 1 = 1 + 1 = 2，ans=3
输出 3，正确。
第二组测一个嵌套(())：
4 (())- i=1，压入 1
- i=2，压入 2
- i=3，s[3]=')'，弹出 m=2，f[3] = f[1] + 1 = 0 + 1 = 1，ans=1
- i=4，s[4]=')'，弹出 m=1，f[4] = f[0] + 1 = 0 + 1 = 1，ans=2
这里注意：以 s[3] 结尾的合法子串是(2,3)；以 s[4] 结尾的合法子串是(1,4)。总共 2 个，和手数一致。
第三组测一个交错但不完全匹配的串())(()：
6 ())(()- i=1，压入 1
- i=2，弹出 m=1，f[2]=1，ans=1
- i=3，s[3]=')'，栈空，f[3]=0
- i=4，压入 4
- i=5，压入 5
- i=6，弹出 m=5，f[6]=f[4]+1=0+1=1，ans=2
最终答案 2，正确：子串(1,2)和(5,6)。
我建议你把这些样例都亲手推一遍，尤其是第二组的嵌套例子，推完了基本就理解dp[m-1]在干什么了。
4. 踩坑记录与常见问题排查
4.1 栈里到底存什么？很多人会存成字符
有人一看到括号匹配，条件反射就写一个stack<char>，存(和)。在这个题里，如果你只存字符，匹配成功之后根本拿不到左括号的下标m，f[m-1]自然没法计算。所以你必须在栈里存下标，而不是字符。
这也是我常常跟人强调的：栈只是工具，存的内容取决于你后续需要什么。题目只要求判断合法性时，存字符就够；题目要求统计区间或子串时，优先考虑存下标。
4.2 答案要用 long long，别用 int
这个很多人会踩。n 最大可以到 10^6，理论上最坏情况是类似于()()()...这样到处都能拼接的串，合法子串数量是 O(n^2) 的规模。你自己算一下：
()()()...()这种连续拼接串，以每个)结尾的 dp 值是 1、2、3、...、n/2，累加起来大约是 n^2/8 级别。- n=10^6 时，这个值超过 10^11，已经远超出
int范围。
所以答案必须用long long，f数组也必须用long long。有些人在 dp 数组上用了 int，小数据没事，一上大数据就 WA，检查半天找不到错，最后发现是溢出，特别憋屈。
4.3 别忽略m > 1这个边界判断
f[m-1]在这里，如果你写成f[m - 1]而不判断m == 1，那f[0]是有定义的，因为数组下标 0 存在且初始化是 0，所以不会越界。但是在一个测试点里，如果你把字符串从下标 1 开始存，f[0]是全局数组自动初始化为 0，所以直接写f[m - 1] + 1其实也不会出错。
不过，如果你的写法是dp[i] = dp[m - 1] + 1，并且 m 恰好是 1，那dp[0]就代表“空串”，它是一个合法的空括号序列。从 DP 语义上，这里取 0 或 1 会有区别。
有人可能会想：空串也算合法括号序列，dp[m-1]是不是应该加 1 表示空串也要算进去？这里要小心：题目要求统计连续子串，空串不是字符串的子串。我们在dp[i]的定义里，统计的是“以 s[i] 结尾的合法子串数量”，这个“子串”要求非空。所以当m == 1时，dp[0] = 0，表示前面没有任何合法段可以拼接，只有s[m...i]这一个新子串。
4.4 为什么不能简单地“遇到一对就加一”
我见过不少人的思路是：每次遇到一对匹配的括号，ans++，最后输出 ans。这在()()这种串上会输出 2，但正确答案是 3，漏掉了拼接出来的整个串。
还有人用另一种做法：维护当前连续合法括号段的长度cnt，遇到匹配就cnt += 2，然后ans += cnt / 2。这个思路比朴素的想法好一点，能处理部分拼接，但它只适用于“当前位置处于一个连续合法段内部”的情况，遇到嵌套和并列混合的串就会算错。
比如()(())用这种思路：
( )匹配，cnt=2，ans+1( ( ) )，中间内层匹配时 cnt=2，ans+1；外层匹配时 cnt=4，ans+2
最后得 4。但正确答案是几个？(1,2)、(3,6)、(4,5)、(3,6) 前面拼接 (1,2)也就是(1,6)。所以是 4 个。这里巧合正确，但换一个交错的情况就会出问题：
())(()用这个思路算也会出错，因为中间断开的))处理不干净。一句话总结：长度法只适合连续的单一合法段，不适合有间隔和嵌套的杂串。
4.5 内存优化：f 数组可以滚动省掉吗
f[i]的更新依赖f[m-1]，而m-1是 i 之前的一个位置，不一定是 i-1。所以你不能只保留一个滚动变量。最坏情况下，()()()...里每个)匹配到的是上一个(，它们可能相隔很远。
但你没发现一个模板吗：这个问题的stk本身其实就承担了一部分“记忆”功能。f[m-1]的值在匹配成功的一瞬间才会被用到，理论上可以用一个辅助数组只存“以某个位置结尾的合法子串数”，这个数组是必须要有的，因为可能在很远之后才被引用。所以f数组没办法省掉。
好在数组内存不大：f用long long最多 8MB，stk用int最多 4MB，总共 12MB，完全能接受。
5. 复杂度分析与同型题目扩展
5.1 时间复杂度和空间复杂度
时间上，每个字符只被扫描一次；每个左括号入栈一次、出栈一次。f数组的更新是 O(1)。所以整体是 O(n)。空间上需要f[MAXN]和stk[MAXN]，都是 O(n)。
这题能做到 O(n)，本质是因为我们在“按右端点分类”之后，每个右端点只需要知道它匹配的左括号位置以及那个位置之前的合法段数量，这两个信息都能在扫描过程中 O(1) 得到。没有 log，没有二分，就是一个单调的栈和一个一维 DP。
如果 n 增加到 10^7，这个算法照样能跑，只是输入输出的常数需要优化。如果数据范围扩大到多组数据，每组求一次 O(n)，总复杂度就是 O(总长度)，也完全没问题。
5.2 进阶方向一：带通配符的括号序列
如果题目把部分字符改成?，表示可以当作左括号或右括号，让你统计所有可能的替换方案对应的合法子串总数，那 DP 状态就得多一维。因为替换方案不同，匹配结果也不同，不能只用一个栈了。
常见的处理思路是把问题转化成“最小替换数”或者“方案数”的 DP，状态为dp[i][j]表示处理到第 i 个字符、栈中剩余 j 个左括号的方案数或数量。这种题型在动态规划里是独立的版块，和今天的单串扫描并不是一个难度。但理解了今天的基础模型，再去学那类问题，会更快。
5.3 进阶方向二：最长合法括号子串
经典的 LeetCode 32 题“最长有效括号”和这个题非常像，只是问的是长度而不是数量。
那道题的 DP 设计是：
- 遇到
)且匹配成功，dp[i] = dp[m-1] + (i - m + 1) - 连续拼接时还要考虑跨过匹配段之前的合法长度
- 最后取最大值
两道题共用同一个“栈匹配 + dp 拼接”思想，只是目标函数从“计数”换成了“求最大值”。如果你能把今天这道题完全吃透，再去写 LeetCode 32，十分钟内就能写出来，因为核心递推式子几乎就是同一个。
5.4 进阶方向三：二维括号矩阵里的矩形子区域
如果把字符串拉长成一个 2D 括号矩阵，问你多少个矩形区域内，按行拼接后是合法括号序列，那就要把每一列的符号转成“某一行的括号差值”，然后用单调栈处理“列之间的最小前缀和”。这种题已经达到区域赛铜牌难度了。做这种题之前，你必须先具备今天这种“把一个区间合法性压缩成一个可拼接数值”的思维，否则面对二维问题根本无法建模。
最后说点题外话
这道 P15445 我打完之后最大的感受是：它一点都不难，但它非常“诚实”。你一旦没想清楚“合法子串既能嵌套又能拼接”这件事，写出来的代码一定在某些刁钻数据上挂掉。我后来拿它去和别人对拍，发现最常见的错误就是只处理了嵌套没处理拼接，或者反过来。
所以如果你在比赛里遇到这种“题面很短、代码很短、但坑很多”的计数题，我建议你多花五分钟手写小数据验证，别急着交。数据结构写挂了还能调，算法模型没想清楚，再调也是白调。
这道题的扩展空间很大，能演化出很多变体。但核心就一句话：用栈找到配对，用 dp 记住前面的合法段，计数就完成了。下次再看到“永远在一起”类似的意象，第一时间往括号匹配上想，大概率不会错。
