链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
?题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
? ? ? ? ?按普通做法（一个个标记判断），这道题的数据如果再大一点，就TLE了。为了求更优解，应该想些别的方法避免高时间复杂度的速算法。
差分法
????????首先想到，是否可以通过逆向思维，先求该点覆盖地铁的次数，由此维护一个差分数组delta（储存比前一个点多覆盖多少层，有关差分数组的使用说明：前缀和与差分的引入_Winnie_deer的博客-CSDN博客例1 读入一个班n个同学的成绩，之后读入一个数q，表示q次询问，每次询问当一个同学分数为x时，他排多少名。 很明显，挨个数时间复杂度太高。只需要统计大于等于x分的人数即可得到该同学的名次。可以使用greater[i]数组维护，方式是不断加上分数大于等于i的人数。将对区间的查询转化为对区间端点的查询，这种思想就是前缀和的核心。要求对于区间操作尽可能往这里想。 前缀和可用于求区间和。我们还可以发现，不仅可以通过greater数组轻松求出同学的总成绩，甚至...https://blog.csdn.net/Winnie_deer/article/details/121344888?spm=1001.2014.3001.5501），这样差分数组转化为原数组a（该点覆盖多少层，a[i]=a[i-1]+delta[i]）就可以在O(n)的时间复杂度下求出是否有树啦（当a[i]=0时没有覆盖，此时即为有树）。再经思考发现，因为在统计覆盖层数时仅是从前向后挨个统计，只需要用一个变量a依次向后更新即可，故a并不需要被开成数组（这里脑洞总结：那么什么时候需要开成数组呢？数组的作用之一是储存信息方便读取，也就是说在需要多次查询不同区间的树的数目的时候需要）。
????????总结的差不多了，上代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const ll maxn=10005;
const ll mod=1000000007;
int l,m,delta[maxn],s,e,a,ans;
int main(){
cin>>l>>m;
for(int i=0;i<m;++i){
scanf("%d%d",&s,,&e);
delta[s]++;
delta[e+1]--;
}
for(int i=0;i<=l;++i){
a+=delta[i];
if(a==0) ans++;
}
cout<<ans;
return 0;
}? ? ? ?
区间合并法
? ? ? ? 另外，我们考虑将多重区间不断合并为整个区间。为了合并的便捷，我们考虑先将覆盖的左右地铁的地点信息存为结构体数组，再通过sort按照优先级从大到小为左端点值、右端点值的升序对数组进行排序。利用L和R记录当前区间左右端点。当出现区间重合时，通过判断右区间是否比R大决定是否修改R；当出现不重合区间时，用原来树的数目减去(R-L+1)，即之前记录的区间的树木的数量，再让L和R分别等于此不重合区间的左右端点。另外，别忘了在最后再减去(R-L+1)（最后一次更新L和R并没减去）。上代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=105;
const ll mod=1000000007;
int l,m,ans;
struct ty{
int s, e;
}a[maxn];
bool cmp(ty a,ty b){
if(a.s==b.s) return a.e<b.e;
return a.s<b.s;
}
int main(){
cin>>l>>m;
ans=l+1;
for(int i=0;i<m;++i)
scanf("%d%d",&a[i].s,&a[i].e);
sort(a,a+m,cmp);
int L=a[0].s, R=a[0].e;
for(int i=1;i<m;++i){
if(a[i].s<=R){
if(a[i].e>R) R=a[i].e;
}else{
ans-=R-L+1;
L=a[i].s; R=a[i].e;
}
}
cout<<ans-(R-L+1);
return 0;
}由区间合并受到的启发
????????对数据加以强化。当L<=10^9、M<=10^5时，发现单纯使用差分的话数组根本存不下。而且发现，本身就是对区间端点进行操作，为何在查询最终值时又是遍历区间？很明显还可以对算法继续进行优化。
? ? ? ? 受区间合并启发，我们想是否可以通过只存输入信息的delta，并通过这些值求出最终结果？即，求解树木数量的区间应该如何依靠差分数组的信息求得？分析发现，当该点无地铁覆盖时，值应为0；刚开始有地铁覆盖时，值由一贯的0变为1。这就是有树区间的起点和终点啦。此时的我们只要创建delta结构体数组使其存位置信息pos、对差分数组的维护信息num（加减1），以pos升序、num升序为序（由于最终还是要从0向L遍历，故位置信息也应该是pos越靠近0越先考虑；num为-1排在num为+1前，因为-1肯定说明前面已经覆盖过一次+1，这个-1是拿来抵消的）。代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=105;
const ll mod=1000000007;
int l,m,ans;
struct ty{
int pos,num;
}delta[maxn<<1];
int s,e,a;
bool cmp(ty a,ty b){
if(a.pos==b.pos) return a.num<b.num;
return a.pos<b.pos;
}
int main(){
cin>>l>>m;
for(int i=1;i<=m;++i){
scanf("%d%d",&s,&e);
delta[i].num=1; delta[i].pos=s;
delta[i+m].num=-1; delta[i+m].pos=e+1;
}
sort(delta+1,delta+1+2*m,cmp);
ans=0;
for(int i=1;i<=2*m;++i){
a+=delta[i].num;
if(a==1&&delta[i].num==1)
ans+=delta[i].pos-delta[i-1].pos;
}
ans+=l-delta[2*m].pos+1;
cout<<ans;
return 0;
}? ? ? ? 对于差分还是掌握的不够熟练，这里做一下总结：
? ? ? ? 1、当还原减1时，是在区间右端点的下一个位置进行操作；
? ? ? ? 2、注意到满足有树区间条件时，直接用当前pos（开始的端点）-之前pos（前一个右端点+1），这里画图可知。