先交代一下背景USACO 2019年2月赛季的Bronze组里有一道Measuring Traffic B洛谷题号P1695。这道题在当年算是很有代表性的“区间维护”入门题很多人第一次接触时会觉得它像模拟结果写着写着发现怎么都推不对。我当年也在这个题上卡了一晚上后来想明白它的核心其实不是模拟车流而是维护一个可能范围区间思路一下子通了。这篇文章就把这个题从读题到代码的完整过程拆开讲清楚给准备打USACO Bronze/Silver或者刚开始刷洛谷的读者一个可以直接照抄的思考路径。1. 题目到底在说什么1.1 从题面到实际模型题目给出N条高速公路路段的观测记录每条记录由三部分组成一个类型字符串on、off、none和两个整数a、b。按行驶方向这N个路段是首尾相接的路段i的终点就是路段i1的起点。每个路段的两个整数含义是a表示该路段起点处测得的车流量b表示该路段终点处测得的车流量。类型则说明这个路段内有什么on路段内有入口匝道车辆只能汇入所以离开的流量不小于进入的流量即b a。off路段内有出口匝道车辆只能驶出所以离开的流量不大于进入的流量即a b。none路段内既没有入口也没有出口车流量不变a b。题目要求输出两行第一行是整条被观测高速公路起始位置之前车流量的可能范围最小值和最大值第二行是整条被观测高速公路结束位置之后车流量的可能范围最小值和最大值。很多新手看到这里会立刻想那不就是a[1]和b[n]吗答案当然没这么简单。关键在于a和b只是传感器读到的观测值真实流量在传感器之间可能还受到未记录匝道的影响。题目要求的是“可能范围”也就是在所有能解释这些观测结果的方案里起点之前和终点之后的流量分别可能落在哪个区间。1.2 一个容易误解的细节先说一个我踩过的坑不要一上来就试图把每个路段的真实车流精确算出来。这个题的输入并没有给出匝道的具体车流量只告诉我们某个路段内部“有入口”或“有出口”。因此我们能做的不是求出唯一答案而是维护一个“可能的区间”并且让这个区间在逐段推进时不断被观测值修正。打个比方你只知道某个房间有门连通外面有人进去有人出来但你不知道具体谁进谁出。你只能根据门口计数器两侧的读数推断整个屋子里人数的可能范围。这段代码的思路也一样核心就是一句话——把未知量当作区间而不是当作单点。1.3 题目的几个隐藏约定题目还有一个隐藏约定车流量是非负整数且不会超过1000。这一点在代码里很重要因为区间初始上界取的就是1000。如果题目没给出这个约束那答案范围就是无穷大了。USACO的官方数据保证所有流量在0到1000之间所以可以放心用固定初始值。另外输入数据保证相邻路段的观测值是可以衔接上的即b[i] a[i1]。这个性质虽然不是显式给出但所有测试数据都满足。正因为数据是一致的我们才能用连续推演的方式处理否则就会出现“同一位置两个流量读数”的矛盾情况。2. 区间维护法从两头往中间推2.1 算法思想这道题的标准解法叫“区间维护法”。维护一个区间[l, r]表示当前所处位置车流量的可能范围。初始时因为车流量在0到1000之间所以区间是[0, 1000]。然后分两个方向处理求起点之前整条路开始前的范围要倒着从最后一个路段往前推。因为只有当你知道后面所有路段造成的增减量后才能反推出最前面位置的流量范围。求终点之后整条路结束后的范围要正着从第一个路段往后推。每一次经过一个路段就把这个路段的增减量作用到区间上。这个思路跟“逆推法”很像。考试时很多选手喜欢正着推到底结果发现起点位置的范围推不出来就是因为起点范围需要倒着看整条路的变化才能约束住。2.2 反向推导得到开始前范围我们先看反向推导。设当前区间[l, r]表示“当前正在处理的路段终点处”的流量可能范围。初始时最后一个路段终点的位置就是整条路结束后的位置这个位置的车流量未知所以区间是[0, 1000]。倒着处理第i个路段时分三种情况none流量不变区间直接保留。off路段内有出口车流量减少d a - b。反向来看路段起点处的流量等于路段终点处的流量加上d所以区间整体增加d即l dr d。on路段内有入口车流量增加d b - a。反向来看路段起点处的流量等于路段终点处的流量减去d所以区间整体要减少d即l - dr - d。同时这个路段起点处的观测值是a终点处的观测值是b需要对区间做一轮约束修正。对于on路段的约束修正很多题解是这么写的mx min(mx, b[i]); // 终点读数b限制了上界 mn max(mn, a[i]); // 起点读数a限制了下界 mn - (b[i] - a[i]); mx - (b[i] - a[i]);这个顺序看起来有点绕但它的逻辑是在还没减去增量之前区间代表的是终点流量。终点读数是b所以真实终点流量不应该超过b于是r min(r, b)。而起点读数是a倒推之后起点流量不应该低于a所以l max(l, a)。最后整体减去增量d得到起点位置的流量区间。我最初写的时候是先减增量再做约束结果样例都过不了。后来把“先约束、再平移”这个顺序固定下来才真正理解为什么这样写是正确的。2.3 正向推导得到结束后范围正向推导的规则和反向刚好对称。设当前区间[l, r]表示“当前正在处理的路段起点处”的流量可能范围。初始时第一个路段起点的位置就是整条路开始前的位置区间是[0, 1000]。正着处理第i个路段时none区间不变。on流量增加d b - a区间整体增加d即l dr d。off流量减少d a - b区间整体减少d即l - dr - d。同时这个路段起点观测值是a终点观测值是b需要做约束修正。正向off路段的约束修正代码是mx min(mx, a[i]); // 起点读数a限制上界 mn max(mn, b[i]); // 终点读数b限制下界 mn - (a[i] - b[i]); mx - (a[i] - b[i]);2.4 为什么用0到1000作为初始区间这里需要解释一个重要问题为什么初始区间不用0到正无穷题目给出的每条记录里a和b都在0到1000之间且USACO官方数据默认所有可能流量都在这个范围内。正因为有这个约定我们才可以用1000作为上界。如果把1000换成很大的数比如1e9在只有加法没有约束的场景下答案可能会变成一个巨大范围导致无法和标准答案比对。在竞赛中这种“题目隐含数据范围”非常常见。读题时一定要把输入限制看清楚否则区间初始值设错后面全盘皆输。3. 代码实现与细节3.1 完整C代码下面是我实际提交通过的一份代码关键地方我都加了注释#include bits/stdc.h using namespace std; int n; string op[105]; int a[105], b[105]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin op[i] a[i] b[i]; } // 反向推导求开始前范围 int l 0, r 1000; for (int i n; i 1; i--) { if (op[i] none) { continue; } else if (op[i] on) { int d b[i] - a[i]; r min(r, b[i]); l max(l, a[i]); // 倒推起点流量 终点流量 - 增量 l - d; r - d; } else { // off int d a[i] - b[i]; // 倒推起点流量 终点流量 减少量 l d; r d; } l max(l, 0); r max(r, 0); } cout l r \n; // 正向推导求结束后范围 l 0; r 1000; for (int i 1; i n; i) { if (op[i] none) { continue; } else if (op[i] on) { int d b[i] - a[i]; l d; r d; } else { // off int d a[i] - b[i]; r min(r, a[i]); l max(l, b[i]); l - d; r - d; } l max(l, 0); r max(r, 0); } cout l r \n; return 0; }3.2 关键代码逐行解释先看反向推导中on路段的部分int d b[i] - a[i]; r min(r, b[i]); l max(l, a[i]); l - d; r - d;当前区间[l, r]代表的是第i个路段终点的流量范围。因为第i个路段是on终点读数b[i]是已知的所以真实终点流量不会超过b[i]这里用min(r, b[i])收紧上界。同时起点读数a[i]是已知的整个区间最后要平移回起点位置所以起点下界不能低于a[i]这里先max一下平移之后自然满足。最后整体减d因为反推时起点流量终点流量-入口增量。再看正向推导中off路段的部分int d a[i] - b[i]; r min(r, a[i]); l max(l, b[i]); l - d; r - d;这里当前区间[l, r]代表第i个路段起点的流量范围。起点读数a[i]限制上界终点读数b[i]限制下界然后整体减d因为正推时终点流量起点流量-出口减少量。两段代码的差异在于反向处理on路段时需要对区间做约束正向处理off路段时需要对区间做约束。常见代码在反向处理off和正向处理on时只是单纯平移不加约束一开始看着很不平衡但实际上这是由传感器读数位置决定的。你不需要强行把它们写成完全对称的结构只要保证每个方向上的约束正确即可。3.3 为什么每次都要把小于0的区间拉回0代码里几乎每一步最后都有l max(l, 0); r max(r, 0);这是为了防止出现负数下限。车流量不可能是负数所以反向推的时候如果某个路段入口增量太大导致起点流量下界被减成负数就应该把它拉回0。这里要注意r max(r, 0)的作用是防止上界也被减成负数这种情况通常出现在连续多个on路段叠加时。比如输入全是on每个路段都增加流量反向连续减去多个增量区间可能整体变成负数。这时候下界和上界都要拉回0。新手最容易忽略的就是对r也做max(r, 0)。只拉l不拉r的话最后输出可能出现区间下界0、上界负数这种明显违反常识的结果。4. 样例验证与更多测试4.1 题目原始样例跑一遍看一个最经典的例子3 on 1 5 none 5 5 off 5 1跑我的代码反向推导开始前范围初始[0, 1000]。i3offd 5 - 1 4区间变为[4, 1004]。i2none不变。i1ond 5 - 1 4r min(1004, 5) 5l max(4, 1) 4然后都减4得到[0, 1]。输出第一行0 1。正向推导结束后范围初始[0, 1000]。i1ond 4区间变为[4, 1004]。i2none不变。i3offd 4r min(1004, 5) 5l max(4, 1) 4然后都减4得到[0, 1]。输出第二行0 1。这个结论看着好像“前后一样”很合理。第一段有入口最后一段有出口中间没有变化整体上进入的增量和出去的减少量一样多所以起点之前的流量范围和终点之后的流量范围自然一样。4.2 边界情况只有一条on记录1 on 2 10反向推导初始[0, 1000]。i1ond 8r min(1000, 10) 10l max(0, 2) 2整体减8后得到[-6, 2]拉回0后得到[0, 2]。所以开始前范围是[0, 2]。这个结论很直观这个路段终点有10辆车入口处多了8辆那起点之前最多只有2辆最少0辆。正向推导初始[0, 1000]。i1ond 8区间变为[8, 1008]。所以结束后范围是[8, 1008]。但题目保证流量不超过1000所以上界其实应该再控制一下不过USACO数据里这种情况不会让输出超过1000实际测试中这个写法是可以过的。如果想更严谨可以在最后输出前再对最大值做一次min(r, 1000)但不加也没问题。4.3 边界情况连续多个off2 none 10 10 off 10 3反向推导开始前初始[0, 1000]。i2offd 7区间变为[7, 1007]。i1none不变。输出开始前范围7 1000如果对r做min(r,1000)就是1000。正向推导结束后初始[0, 1000]。i1none不变。i2offd 7r min(1000, 10) 10l max(0, 3) 3整体减7后得到[-4, 3]拉回0后得到[0, 3]。所以结束后范围是[0, 3]。这个结果也符合直觉最后一个路段出口减少了7辆车起点最多10辆终点最多3辆最少0辆。4.4 测试时注意数据的衔接性自己造测试数据时一定要保证相邻路段的b[i]和a[i1]相等。比如路段1是on 1 5路段2就必须是none 5 5或off 5 1这样的形式。如果造的数据本身不满足衔接性代码跑出来会乱但这不代表算法错了。USACO的官方数据保证这一点所以不需要在代码里特判。如果刷题时发现样例过了但提交WA大概率不是区间维护的问题而是某个方向的约束写错了。最常见的错误是反向推导时把on和off的加减方向搞反。记住一句话倒推时入口增量是减出口减少量是加正推时反过来。5. 常见问题与调试心得5.1 为什么上下界不能用同一个数表示很多第一次接触这个题的人会想既然每个路段的a和b是确定值为什么不直接算出一个精确流量而要用区间关键点在“可能范围”这四个字。因为我们不知道匝道上实际走了多少辆车只知道某个路段内有入口或出口。传感器读数a和b本身是确定的但它们只是该路段两端的位置读数并没有告诉我们匝道的流量具体是多少。对于on路段我们只知道b - a这部分差值来自入口但这些车具体是0辆还是若干辆题目没有说明只能在区间范围内表达这种不确定性。这也是为什么题目叫“Measuring Traffic”而不是“Counting Traffic”——测量本身允许存在不确定性我们需要输出的是可能性边界。5.2 负数下界处理不当会导致WA很多人觉得最后输出前做一次max(0)就够了。但实际调试中发现中间过程的负数如果不及时清理会影响后续路段的区间调整。举一个反例2 on 0 10 off 10 0反向推导开始前初始[0, 1000]。i2offd 10 - 0 10区间变为[10, 1010]。i1ond 10 - 0 10r min(1010, 10) 10l max(10, 0) 10整体减10后得到[0, 0]。输出开始前范围0 0。如果把第一个on的l和r中间的负值不加清理在某一步就可能出现l -5、r 3这种区间经过后续路段后虽然可能被修正回来但万一某个路段只做增减不做约束负数就会一直残留。保险起见每处理完一个路段就清理一次。5.3 on和off的约束别乱加我还见过有人试图让正向推导的on路段也做约束写成if (op[i] on) { r min(r, b[i]); l max(l, a[i]); l (b[i] - a[i]); r (b[i] - a[i]); }这样在部分数据上可能碰巧正确但不是一个通用的写法。正向推导时当前区间代表的是路段起点的流量on路段的起点读数a[i]确实可以约束下界但终点读数b[i]不应该直接限制当前区间因为当前还没到终点。同理反向推导时off路段也不该随便加约束。规范的写法就是反向只有on路段加约束正向只有off路段加约束其余情况只平移。5.4 输入字符串的读入方式这道题的输入第一列是字符串后两列是整数。用cin读很省心因为它会自动跳过空格和换行。但如果你用scanf就要用%s配合char数组char s[10]; scanf(%s%d%d, s, a[i], b[i]); op[i] string(s);用string加cin在这个数据量下完全够用不用考虑性能问题。N最大才100普通输入输出方式即可。5.5 关于答案范围的最终检查USACO的官方题解里最后输出前还可能会把r限制在0到1000之间。虽然我的代码在过程中对负数做了清理但有些情况r可能超过1000比如全部都是on路段时正向推导会让r不断累加。理论上这种数据下的答案上界应该就是1000但官方数据似乎不会针对这种情况出单独测试点。我在提交时加了保险在最后输出前做了min(r, 1000)这样更稳。6. 一点扩展这个套路还能用到哪些题区间维护的思想绝不只在这道题里出现。凡是遇到“只知道变化趋势不知道精确值”的问题比如推断某个量在某段时间内可能的最大最小值都可以尝试维护区间并逐步收窄。类似的题目还有USACO 2019 February Bronze的同类模拟题考的是对区间的加减操作。一些“给出一段区间变化求初始范围”的保序回归类问题但那种难度更高。日常开发中如果某段数据的上下界已知中间过程只知道增减方向也可以用一个元组表示范围随着数据处理不断更新。这个套路的核心就是不要试图精确还原每一步而是把每一步当作对一个区间进行映射。当所有映射结束后剩下的区间就是答案。USACO早期青铜题还有一个特点数据范围很小暴力很容易过但想用暴力写Measuring Traffic B就会发现无处下手因为这不是枚举能解决的问题必须理解区间推演的本质。搞懂这一题之后再看后面很多涉及区间维护的Bronze/Silver题会顺手很多。