前言

差分是竞赛中非常常用的技巧，正巧这次的USACO题目中可以用上差分，顺便做一个普及

这一个小节大概就只准备讲这一题，因为剩下的题目只涉及到进制转换和回文判断，属于对语法的巩固，没有太多想讲的知识点

题意

[Milking Cows]

给定若干条线段(数量不大于5000)，左右端点范围[0,1000000]，求没有被线段覆盖的最长区间和被至少一条线段覆盖的最长区间

题目分析

首先可以得到这个题的一个非常朴素的做法，将每个线段在数组中对覆盖到的位置+1，然后扫描整个区间得到答案，USACO的原数据较弱，所以我看到有些同学是这么过的，但是这么做的复杂度是O(nL)的，并不是一个合理的复杂度

IMOS

IMOS又被称为累积和法，其实就是通过前缀和以及差分思想来维护数据，在数据结构题中这个技巧非常实用

举一个简单的例子：

有一辆公交车，现在告诉你每个人上车和离开的时间点，要求查询任意时刻车上的人数

IMOS的做法就是，对于每个人，我们只需要在其上车的时间点+1，下车的时间点-1，计算这个时间表的前缀和，就可以得到关于时间点的答案数组

计算前缀和

二维的处理方法看下图应该就能看懂

图是从我自己比较古老的讲课slide里面截的，将就着看吧

回到题目

那么有了IMOS这个手段，对于刚才那种朴素的做法，我们可以用IMOS来优化，对于每个区间，在左端点的位置+1，在右端点的后一个位置-1，然后对数组求前缀和就得到了覆盖数组，扫描求解答案即可

然而此题其实还有一个更具有普适性的做法，将区间排序，然后比较左右端点来更新两个答案，具体细节留给大家自己来思考实现

任务清单

  • 实现朴素的区间覆盖数组求解，并用IMOS优化
  • 对区间排序，顺序扫描区间计算答案