题解 P3406 【海底高铁】

对于其中一小段，我们要么全部买纸票，要么全部刷卡。 所以我们只需要统计每一小段经过的总次数。 如果你暴力模拟统计的话，估计会tle。 怎么快速知道每一段次数呢？ 我们回忆一下“借教室”这道题。 如果你高兴的话，可以上线段树或者树装数组——但是没必要。 假设有5段，我们把1到3加上1，可以像图2一样，开头+1，结尾-1。然后2到4加1，如图3. ```cpp +1 -1 +1 +1 -1 -1 - - - - - -- - - -- - -- -- - -- -- 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 图1 图2 图3 ``` 然后呢，我们求出每一项前缀和（就是从前往后加）： ```cpp 1 2 2 1 0 - - - - - 1 2 3 4 5 图4 ``` 然后每一段直接贪心比较，然后就没有然后了。