CF1556C Compressed Bracket Sequence 这道题光看名字很容易以为又是括号匹配模板题真正动手之后才发现“Compressed”才是全部考点。题面给的不是一串字符而是压缩后的段比如 4 个左括号、1 个右括号、2 个左括号、3 个右括号这样一段段拼起来要求统计原串里有多少个合法括号子串。括号子串的统计在普通字符串上是一道老题但一旦括号数量被压成数字长度可能达到 1e12 量级直接展开就是灾难。这篇文章我会完整拆解这道题的思路包括我是怎么从错误的暴力跳到正解的、为什么维护“可行起点区间”能批量计数以及代码里最容易被忽略的几个边界。适合正在刷 CF 1500~1700 区间、或者想搞懂“区间计数类括号题”的读者。1. 先把题意翻译成人话压缩括号序列到底在考什么1.1 输入输出到底长什么样输入第一行是 n接下来 n 个整数 c[0], c[1], ..., c[n-1]。n 是偶数。规定偶数下标这一段全是左括号 (数量是 c[i]。奇数下标这一段全是右括号 )数量是 c[i]。原串就是把每一段按顺序接起来。比如 n 4c [4, 1, 2, 3]那原串就是(((( ) (( )))准确写出来是 4 个 (、1 个 )、2 个 (、3 个 ) 拼接的序列。题目要统计的是原串里有多少个连续子串是“合法括号序列”。合法括号序列的定义沿用常规定义左右括号数量相等并且任意前缀中左括号数量不小于右括号数量。1.2 子串合法意味着什么这里很容易把“合法子串”和一般的“从某个左括号到某个右括号”混淆。合法括号序列要求两个条件整体平衡子串中左括号总数等于右括号总数。前缀非负从左往右扫任何时刻左括号数量不能小于右括号数量。举个例子在(())里面整个串(())合法但子串())不合法因为扫到第三个字符时右括号已经超过左括号了。在压缩序列上做统计难点天然被放大了一段内部可能有几亿个左括号或右括号你不可能真的把它们展开成单个字符再枚举子串。所有计数都必须在“段”的粒度上完成。1.3 为什么不能直接展开成原串假设每个 c[i] 都在 1e9 级别n 是 1000展开后的串长度能到 5e11。就算我们忽略内存光把所有子串枚举一遍就已经是 O(N^2) 的复杂度N 是展开后长度完全不可行。所以必须接受一个事实我们只需要关心“段”与“段”之间的括号数量关系而不是单个括号的位置关系。这道题的所有巧妙之处都体现在如何把一段内可能存在的海量合法子串批量算出来而不是一个一个数。2. 两个看着正确的暴力做法是怎么翻车的2.1 暴力一展开后 O(N^2) 枚举我的第一反应是既然括号串可以压缩那我就先展开然后套用经典算法。经典的统计合法子串数量的做法是枚举每个左括号作为起点维护一个计数器遇到 ( 加一遇到 ) 减一当计数器归零时答案加一当计数器变成负数时结束当前起点。这个做法在展开后的串上绝对正确但问题在于展开后的串太大了。CF1556C 的 c[i] 上限是 1e9展开总长度可能超过 5e11直接超时超内存。更隐蔽的问题是即便你硬展开复杂度也无法接受。所以这个暴力只能用来对拍小数据不可能作为正式解法。2.2 暴力二按“段”为单位直接匹配既然段不能展开那自然会想我枚举起点在第几段、终点在第几段然后只看段之间的数量关系。比如枚举起点段是第 L 段左括号段终点段是第 R 段右括号段把中间所有段都完整包含进去然后检查中间左右括号数量是否平衡。这样复杂度是 O(n^2)n 最多 1000听起来没问题。但这么做立刻会漏掉一种情况起点段内部的偏移。假如起点段有 3 个左括号合法子串可能不是从第 1 个左括号开始的而是从第 2 个或者第 3 个左括号开始。按“整段匹配”的思路你默认起点一定用到了该段全部左括号这显然不对。2.3 一个反例让我彻底放弃按段直接匹配我用 c [2, 2] 试了一下。原串是(())。展开后手工数一下合法子串有 2 个位置 0 到 3整个(())。位置 1 到 2内部的()。但按“枚举起点段 终点段”直接匹配从第 0 段开始第 0 段有 2 个左括号第 1 段有 2 个右括号中间没有其他段。你只会把整个(())算进去内部那个()就丢了。为什么丢因为内部()的起点是第 0 段第 2 个左括号它没有用到该段全部左括号。所以正解必须解决一个核心问题起点段内部的偏移怎么批量处理。3. 核心算法枚举起点段维护可行的起点位置区间3.1 关键观察起点只有在起点段里可变如果我们固定一个子串的起点在第 L 段的某个左括号终点在第 R 段的某个右括号那么中间所有段都是完整包含的没有任何偏移。这句话听起来平凡但它意味着整道题里唯一需要处理“部分包含”的段只有两个——起点段和终点段。于是可以这样想我以第 L 段作为起点段。对于第 L 段内的每个左括号它都可以成为一个候选起点。我管理一个区间 [lo, hi]表示当前还能作为起点继续往右延伸的第 L 段内左括号编号范围。初始时候选起点是第 L 段的第 1 个到第 c[L] 个左括号所以 lo 1hi c[L]。3.2 bal 是什么意思再引入一个变量 bal它表示如果起点是第 L 段的第 1 个左括号那么扫描到当前位置为止累计剩余未匹配的左括号数量。这里有一个很容易绕晕的点如果真正的起点是第 k 个左括号那么从第 1 个左括号到第 k-1 个左括号都不属于这个子串所以实际剩余未匹配的左括号数是bal - (k - 1)因为 bal 是从第 1 个左括号开始累计的起点往后挪了 k-1 个左括号参与匹配的左括号就少了 k-1 个。举个例子第 L 段有 5 个左括号bal 当前是 5。如果起点是第 3 个左括号那实际参与匹配的左括号数不是 5而是 5 - 2 3。这个转换是整个算法的枢纽。3.3 右括号段的计数公式怎么来的假设现在扫描到了一个右括号段这一段有 r 个右括号。进入这一段之前bal 是进入前的剩余左括号数。对于某个候选起点 k 来说它实际剩余的左括号数是 bal - (k - 1)。如果这个子串要在当前右段内找到一个终点那么必须满足1 bal - (k - 1) r解释一下至少为 1说明进入右段时还有未匹配的左括号这样才有东西可匹配。最多为 r说明右段有足够的右括号把它全部消耗掉。当实际剩余左括号数是 c 时右段的第 c 个右括号正好让整个子串归零这个位置就是一个合法终点。并且对于一个固定起点来说合法终点是唯一的不会在同一段里数出多个。把不等式解出来得到 k 的范围bal - r 1 k bal再与当前可行区间 [lo, hi] 取交集左端点取 max(lo, bal - r 1)右端点取 min(hi, bal)如果左端点小于等于右端点那么这段交集中的每个 k 都代表一个合法子串贡献数量就是交集长度。这就是为什么算法能做“批量计数”右段一次可以同时结算多个不同起点对应的合法终点。3.4 扫过之后如何更新可行区间计数做完之后当前右段还会消耗掉一部分左括号。我统一用 bal bal - r 来更新剩余左括号数不管 r 比 bal 大还是小。关键问题是候选起点区间 [lo, hi] 要怎么变对于一个候选起点 k经过这一步之后实际剩余左括号数变为bal - r - (k - 1)为了让后续还能继续往右延伸这个值必须不小于 0bal - r - (k - 1) 0也就是k bal - r 1所以每次扫过一个右括号段之后新的 hi 应该是 min(hi, 当前更新后的 bal 1)。这里 bal 更新已经完成了所以直接写 hi min(hi, bal 1)。如果更新之后 hi lo说明没有任何候选起点能够继续向右延伸这一轮枚举可以直接结束。遇到左括号段就简单了左括号段只会增加剩余左括号数不会让任何原本可行的起点变得不可行所以只需要 bal c[j][lo, hi] 保持不变。3.5 用手算验证算法不会漏用 c [2, 2]即(())走一遍。L 0bal 2lo 1hi 2。扫到第 1 段右段r 2计数区间是 [max(1, 2-21), min(2, 2)] [1, 2]贡献 2。更新 bal 0hi min(2, 01) 1。枚举结束。答案 2和手工数的一致。再试一个复杂点的c [1, 1, 2, 2]原串是()(())。L 0第 1 段右段 r 1计数区间 [1, 1]贡献 1bal 变 0。第 2 段左段bal 2。第 3 段右段 r 2计数区间 [max(1, 2-21), min(1, 2)] [1, 1]贡献 1。这一轮贡献 2。L 2bal 2lo 1hi 2。第 3 段右段 r 2计数区间 [max(1, 2-21), min(2, 2)] [1, 2]贡献 2。总贡献 4。展开()(())手工数()、(())、()、整个串()(())正好 4 个。算法完整。4. 完整代码和复杂度分析4.1 核心实现我用 C 写了一个简洁版本大约 30 行。核心就是外层枚举起点段内层向右扫描维护状态。#include bits/stdc.h using namespace std; using ll long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll c(n); for (int i 0; i n; i) { cin c[i]; } ll ans 0; // 枚举起点段起点段一定是左括号段也就是偶数下标 for (int L 0; L 1 n; L 2) { ll bal c[L]; // 从第 L 段第 1 个左括号开始算剩余未匹配左括号数 ll lo 1, hi c[L]; // 候选起点可以是第 L 段内第 lo..hi 个左括号 for (int j L 1; j n; j) { if (j % 2 0) { // 左括号段只会增加 bal bal c[j]; } else { // 右括号段 ll r c[j]; // 实际剩余左括号数 bal - (k - 1)需要在 1..r 之间 ll leftIdx max(lo, bal - r 1); ll rightIdx min(hi, bal); if (leftIdx rightIdx) { ans rightIdx - leftIdx 1; } // 更新状态 bal - r; if (bal 0) break; hi min(hi, bal 1); if (hi lo) break; } } } cout ans \n; return 0; }4.2 复杂度与数据范围外层枚举起点段最多 n/2 个内层每轮向右扫描 O(n)总复杂度 O(n^2)。CF1556C 的 n 最大是 1000O(n^2) 完全够用。空间上只需要存一个 c 数组O(n)实际上直接把数组读进来就行。有一个细节必须说答案必须用 long long不能用 int。原因很简单c[i] 上限是 1e9起点段内部可行起点数量可能到 1e9多段累加之后答案很容易超过 2^31。我在本地对拍时亲眼见过 int 溢出变成负数的情况。4.3 代码里最容易写错的两个地方第一计数时交集左端点一定要用 max(lo, bal - r 1)右端点用 min(hi, bal)。有些代码喜欢先特判 bal 和 r 的大小关系但在区间取交的写法下不需要特判区间为空自然贡献为 0。第二更新 hi 之后要立刻判断 hi lo。如果不判断可能会在其他起点已经完全失效的情况下继续扫描虽然大多数时候最终答案不会错但会多做无用功更重要的是容易让人对自己的状态维护产生怀疑。5. 边界情况实测这些坑值得单独列出来5.1 剩余左括号刚好为 0 的情况很多人计数时会写 bal r 之类的条件然后在 bal 恰好等于 0 的时候也去计数这是错的。如果进入右段前的实际剩余左括号数是 0说明当前候选起点已经没有任何多余左括号了它不可能在右段内“归零”因为它本来就是 0。此时右段的第一个右括号就会让整个子串变成负数非法。我们的公式用 1 bal - (k - 1) r 来限制下界取 1 就自动排除了这种情况。这也是为什么计数区间右端点是 bal 而不是 bal1k bal 1 对应的是实际剩余左括号为 0 的起点不能计入。5.2 bal 变成负数后必须立刻 break当 bal 0 时说明从第 L 段第 1 个左括号开始整个区间连最靠前的起点都撑不过当前右段。那后面的起点更不可能因为它们可用的左括号数量更少。代码里if (bal 0) break;就是做这件事。这里要注意顺序必须先计数再更新 bal 和判断。有些人习惯先判断再计数但那样会把当前右段本来能产生的合法子串给丢掉。最稳妥的顺序是先算当前右段贡献再更新状态。5.3 多个连续的左括号段或右括号段压缩序列里可能出现左右段交替不规律的情况比如连续两个左括号段或者连续两个右括号段。连续左括号段在我们的算法里没有任何特殊处理难度反正碰到左段就 bal c[j]候选起点区间完全不变。连续右括号段反而容易想明白第一个右段可能把 bal 削到很小hi 会因此被压缩甚至直接变成空集。第二个右段再出现时如果 hi lo说明当前起点段已经没有候选起点能延伸到这么远直接 break 是正确的。我曾经有一个版本试图把连续右段合并起来再算结果引入了大量边界判断反而容易写错。直接在每一段上顺序处理是最稳妥的。5.4 用一组小数据快速对拍输入实际含义正确输出说明2 1 1()1最简单的情况2 2 2(())2注意内部()4 1 1 1 1()()3两个独立括号对加整体2 1 2())1只有第一个()4 1 1 2 2()(())4跨段整体匹配不能丢4 3 1 1 1((()())3整体不平衡时的计数对拍的时候如果发现自己实现的答案和预期不一致优先检查是不是把起点段内部的多个起点漏了。这是这道题最常见的错误来源。6. 从这题延伸出去区间计数题的通用思考路径6.1 按起点分批处理是区间计数的经典套路CF1556C 给我的启发是当合法子串数量不好直接统计时可以固定一个维度把起点作为分批依据。每次枚举起点段然后把所有可能起点放在一个集合里用一个区间 [lo, hi] 表示。右括号段能一次结算多个起点是因为这些起点在段内的相对位置虽然不同但它们的实际剩余左括号数只差了一个常数偏移。这个“常数偏移”正好能翻译成区间交集的长度。类似题目里“固定右端点统计可行左端点数量”是更常见的思路但 CF1556C 因为压缩序列的原因固定起点段反而更自然。做这类题时先想清楚哪个维度适合固定哪个维度适合批量结算能少走很多弯路。6.2 和“最长合法括号子串”的思路差异很多人看到合法括号序列第一反应是栈、前缀和、DP。最长合法括号子串的经典做法是维护栈底位置或者用 DP 记录以某个右括号结尾的最长长度。但这道题有本质不同它统计的是所有合法子串数量不是最长的一个。数量统计要求我们不能只保留一个最优状态而是要把所有可能的起点都纳入考虑。栈和 DP 在这种场景下要么需要扩展成二维要么就得想别的方式批量计数。所以我个人觉得 CF1556C 更适合被归入“区间计数 双指针式状态维护”这一类而不是普通括号匹配题。做的时候如果钻进了“怎么用栈”的牛角尖很容易卡住。6.3 复盘时最有价值的一个细节整个算法里我第一次没想到的是把 bal 定义成“从第 1 个左括号开始”的累计值而不是“从候选起点开始”的累计值。这样定义的好处是候选起点 k 只要用 bal - (k - 1) 就能转成实际剩余值于是计数变成了区间求交。如果 bal 直接定义为实际剩余值那每次遇到新段都要为每个起点单独更新复杂度立刻爆炸。“用基准状态加偏移量来表示一批状态”这个思想不止在这道题有用。很多需要批量处理连续整数范围的问题都能靠一个基准值加区间偏移来统一表达。这个感悟我会记很久。
