题目
题目描述：
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。
你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入描述：
第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出描述：
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
解析
这道题可以直接做一个数组，初始化为0，然后暴力搜（每次操作就将一个位置变成1，表示移平了）。
- 但是巨巨教给我差分了，我就要上手去用！
差分：
- 差分，简单来说就是后一个数与前一个数的差所产生的数组，STL里面也有直接化差分的函数。
- 差分的前缀和就是原来的数组，差分的前缀和的前缀和就是原来数组的前缀和（前缀和求差分也成立）。
操作：
- 因为对一个区间进行加减操作，区间中间的差分是不会变的，只要变两个端点就行了（如果是加的话，就是左端点差分加一，右边减一）。
- 然后一直这样操作下去，最后求一个前缀和可以得到原来的式子了。
- 也就是说，如果我们一开始初始化为0的话，最后不是0的就是被铲除了。
打代码：
- 输入操作区间咯，由此得到差分数组。
- 然后对差分数组求前缀和。
- 最后对原数组判断是否为0。
- 看我代码~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int MAX = 1e4 + 7;
int L, M, delta[MAX], a[MAX];
//全局变量区
int main() {
IOS;
cin >> L >> M;
for (int i = 1; i <= M; i++) {
int l, r; cin >> l >> r;
delta[l + 1]--, delta[r + 2]++;
}
for (int i = 1; i <= L + 1; i++)
a[i] = a[i - 1] + delta[i];
int cnt = 0;
for (int i = 1; i <= L + 1; i++)
if (!a[i]) cnt++;
cout << cnt << endl;
return 0;
}
//函数区 
京公网安备 11010502036488号