灬荣丶

用户名：uq_14130869763

访问量：3109

签　名：

等　　级
排　　名	495
经　　验	4617
参赛次数	4
文章发表	2
年　　龄	0
在职情况	学生
学　　校	内蒙古大学
专　　业

　　自我简介：

TA的其他文章

从O(n)到O(m)--从差分到扫描线
浏览：528

你可能喜欢

从O(n)到O(m)--从差分到扫描线

　　作者: 灬荣丶　　　　发表时间：2022-01-11 15:58:17 浏览：528　|　评论：0　

原题链接：校门外的树

##### 用差分的方法可以实现时间复杂度O(n)，这里使用扫描线，可以实现更快时间复杂度O(m)！
### 解题思路:
######   与差分数组这里不同的是这里要使用c++内部的map容器。
######让每个区间的两端点在对应容器 a[] 上赋值，使左右端点的值为相反数；
###### 数组初始为0，flag等于0;
###### 从前到后遍历整个路段, 若是到一个左端点flag就会增加（或者减少），直到右端点，会重新变回 0,所以在flag == 0 的时候代表该下标有树，这样可以实现时间复杂度为O（n）。

### 优化：
#####   这段路有500米，但端点只有6个，一下运行500次是不是浪费时间了。
##### 我们每次修改两端点就可以实现差分，那我们可不可以只遍历所有端点来完成统计树的数量。
我们每到一个端点都会修改flag的值。而当我们的flag > 0时，从**当前端点开始一直到下一个端点这其中的路程**就是**移走的树**的数量。依次累加所有的区间。

正如区间<4-18>和<7-20>;正如区间<4-18>和<7-20>;

a[4] = 1,a[18] = -1; a[7] = 1,a[20] = - 1;    
这里就只需要遍历四个点就行了，可以看出**移走的树**的数量 ****ans = 7 - 4 + 18 - 7 + 20 - 18******；	
 ![图解](/image_editor_upload/20210221090016_15443.png "图解")

### 参考代码:
```c++
#include <bits/stdc++.h>
using namespace std;

map<int,int> a;
int main() {
    int l, m, x, y, ans = 0, flag = 0;
    scanf("%d%d",&l,&m);
    for(int i = 0; i < m; i++){
        scanf("%d%d",&x,&y);
        a[x]++;//左端点为正
        a[y+1]--;//右端点为负，只有两个都遍历到flag变为0
    }
    int last;
    for(auto& x : a){//x.first是下标，x.second是差分值
        if(flag > 0) ans += x.first - last;
        flag += x.second;
        last = x.first;
    }
    ans = l + 1 - ans;
    printf("%d\n",ans);
}
```

**n范围到10000，O（n）要运行10000次,但O(m)最多运行600次**

0.0分

11 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

灬荣丶

TA的其他文章

你可能喜欢

字符统计（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

【明明的随机数】（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

【回文数(二)】（C语言代码）

从O(n)到O(m)--从差分到扫描线

评论区

精彩推荐

钟神赛车（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

wu-淘淘的名单（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-计负均正（C语言代码）

企业奖金发放（C语言代码）

灬荣丶

TA的其他文章

你可能喜欢

字符统计 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

【明明的随机数】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

【回文数(二)】 （C语言代码）

从O(n)到O(m)--从差分到扫描线

评论区

精彩推荐

钟神赛车 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

wu-淘淘的名单 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-计负均正 （C语言代码）

企业奖金发放 （C语言代码）

字符统计（C语言代码）

【明明的随机数】（C语言代码）

【回文数(二)】（C语言代码）

　　评论区

钟神赛车（C++代码）

wu-淘淘的名单（C++代码）

字符逆序（C语言代码）

C二级辅导-计负均正（C语言代码）

企业奖金发放（C语言代码）