题目
题解
题目给定一条长度为 $N$ 的走廊，共有 $M$ 张地毯，第 $i$ 张地毯会覆盖区间 $[l_i,r_i]$ 内的所有位置，要求我们计算最终有多少个位置没有被任何地毯覆盖。
首先明确一个容易混淆的地方：题目并不要求统计一共铺设了多少次地毯，而是统计有多少个位置至少被覆盖一次。因此，即使同一个位置被多张地毯覆盖，也只需要把它当作一个已经覆盖的位置。
一、直接模拟
我们先考虑最直观的方法。
声明一个长度为 $N+1$ 的数组 $vis$，其中 $vis[i]$ 表示编号为 $i$ 的位置是否已经被地毯覆盖。初始时，所有位置均未被覆盖，因此数组所有元素都为 $0$。
对于输入的一张地毯 $[l,r]$，直接枚举：
$$
l\le i\le r
$$
并执行：
vis[i] = 1;当全部地毯处理完毕后，再遍历一次 $vis$，统计值为 $0$ 的位置数量即可。
例如走廊有 $10$ 个位置，依次铺设三张地毯：
- 第一张覆盖 $[1,3]$。
- 第二张覆盖 $[2,5]$。
- 第三张覆盖 $[7,8]$。
那么最终被覆盖的位置为 $1,2,3,4,5,7,8$，未覆盖的位置为 $6,9,10$，答案为 $3$。
这个算法的正确性非常直观，但是我们还需要分析时间复杂度。
一共有 $M$ 张地毯，每张地毯在最坏情况下需要枚举 $N$ 个位置，因此总时间复杂度为：
$$
O(NM)
$$
观察题目的子任务，前两个子任务满足 $N\le 2000$，又因为 $M\le N$，因此最多只需要进行大约 $4\times10^6$ 次位置标记，可以顺利获得这两个子任务的分数，共计 $50$ 分。
但是对于全部数据：
$$
N,M\le 2\times10^5
$$
最坏情况下需要进行：
$$
NM=4\times10^{10}
$$
次操作，显然难以在通常的时间限制内完成。
那么问题来了：我们是否真的需要把每张地毯覆盖的全部位置都重新枚举一遍？
二、差分数组
这里介绍一种非常适合处理区间修改的数据结构：差分数组。
我们先不考虑这道题，假设现在有一个数组 $a$，要求我们对区间 $[l,r]$ 内的所有元素增加 $1$。
直接模拟需要枚举 $r-l+1$ 个位置，但是如果我们预先定义差分数组 $d$：
$$
d_i=a_i-a_{i-1}
$$
其中令 $a_0=0$，那么就存在一个非常重要的关系：
$$
a_i=\sum_{j=1}^{i}d_j
$$
也就是说，原数组中的某个元素，等于差分数组对应位置的前缀和。
接下来我们考虑区间加一操作。
假设要使 $a_l,a_{l+1},\ldots,a_r$ 全部增加 $1$，实际上只需要修改差分数组的两个位置：
$$
\boxed{
\begin{aligned}
d_l&\gets d_l+1\
d_{r+1}&\gets d_{r+1}-1
\end{aligned}
}
$$
为什么这样修改就能达到要求？
我们根据前缀和还原原数组：
- 当 $i<l$ 时，前缀和没有包含 $d_l$，因此原数组不受影响。
- 当 $l\le i\le r$ 时，前缀和包含 $d_l$ 增加的 $1$，却尚未包含 $d_{r+1}$ 减少的 $1$，因此该位置的值增加 $1$。
- 当 $i>r$ 时，前缀和同时包含 $+1$ 和 $-1$，二者相互抵消，因此原数组同样不受影响。
所以，一次原本可能需要 $O(N)$ 时间的区间修改，现在只需要 $O(1)$ 时间！
三、回到本题
我们可以令 $a_i$ 表示位置 $i$ 被多少张地毯覆盖，那么每铺设一张地毯 $[l,r]$，就相当于执行：
$$
a_l,a_{l+1},\ldots,a_r\gets a_l+1,a_{l+1}+1,\ldots,a_r+1
$$
因此直接使用刚才的差分操作即可：
d[l]++;
d[r + 1]--;全部地毯处理结束后，通过前缀和还原每个位置的覆盖次数：
$$
a_i=a_{i-1}+d_i
$$
如果 $a_i=0$，说明没有任何地毯覆盖这个位置，答案增加 $1$；否则说明这个位置已经被至少一张地毯覆盖，不需要统计。
注意，题目允许多张地毯重叠，因此 $a_i$ 可能大于 $1$，但我们只需要判断它是否等于 $0$。
还有一个值得注意的下标问题：因为我们需要修改 $d[r+1]$，而 $r$ 最大可以等于 $N$，所以建议直接将差分数组开为 $N+2$，避免越界。
四、C++ 代码
#include <bits/stdc++.h>
using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;
void solve()
{
int n, m; cin >> n >> m;
vector<int> d(n + 2, 0);
while (m--)
{
int l, r; cin >> l >> r;
d[l]++;
d[r + 1]--;
}
int ans = 0;
int cnt = 0;
for (int i = 1; i <= n; ++i)
{
cnt += d[i];
if (cnt == 0) ans++;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}五、总结
本题的核心在于发现：地毯覆盖区间相当于对一段连续数组进行区间加一操作，而我们不需要在每次操作之后立即查询结果，因此可以先使用差分数组记录全部修改，最后统一还原覆盖次数。
与前缀和主要用于快速查询不同，差分数组主要用于快速执行区间修改。二者之间具有密切的联系：差分数组进行前缀和运算，就可以还原原数组。
本题只进行区间修改和最终的一次统计，因此非常适合使用差分。
复杂度分析：
- 处理全部地毯需要 $O(M)$ 时间。
- 还原覆盖次数并统计答案需要 $O(N)$ 时间。
- 差分数组需要 $O(N)$ 空间。
所以最终复杂度为：
$$
\boxed{O(N+M)}
$$
难度： 普及−（橙，个人评估）
考点： 枚举、模拟、差分数组、前缀和
时间复杂度： $O(N+M)$
空间复杂度： $O(N)$