HRBUST

用户名：HRBUST123456789

访问量：5964

签　名：

等　　级
排　　名	212
经　　验	6217
参赛次数	0
文章发表	21
年　　龄	0
在职情况	学生
学　　校	哈尔滨理工大学
专　　业

　　自我简介：

TA的其他文章

字符串的反码-题解(C++代码)
浏览：426

链表之报数问题-题解建立循环链表解决
浏览：531

数据结构-图的遍历——DFS深度优先搜索-题解（C++代码）
浏览：153

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

简单易懂应对多次操作的差分组解法

　　作者: HRBUST　　　　发表时间：2021-04-13 21:54:29 浏览：497　|　评论：2　

原题链接：校门外的树

这道题我做过很多次了。。。
各种各样的变种，决定总结一下

首先读题，题意很清晰明了，就是把从a到b的树砍光，之后反复重复m次，每次的a，b都会变化
因此第一种朴素的想法诞生了。。。
将有树的位置用数组标记为0，一但进行砍伐活动，就将从a到b的所有数都加上1
最后一次砍伐结束后去遍历数组，看数组中有几个0
例子：
数组a一开始初始化全为0
第一次砍伐1-3
a[0] a[1] a[2] a[3] a[4] a[5] ...
  0    1    1    1    0    0

第二次砍伐2-5
a[0] a[1] a[2] a[3] a[4] a[5] ...
  0    1    2    2    1    1
 
依次类推
解法一的代码
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        for(j=l;j<=r;j++) a[j]++;
    }

for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

```

这种方法很好理解，编写过程也较为简单，但我并不建议这样解决问题，因为这道题的数据范围很小 m竟然只有100！！！

这道题的变种m往往会达到一个极大的数值比如1000000或者更多，在这种情况下上面的方法就会超时因为询问的次数过多，同时每次从a到b遍历赋值的过程过于繁琐
对这道题进行更加深入的分析，可以发现实质进行的操作是在对一个区间的所有数进行加减操作，这个操作可以使用线段树实现，但是在这道题中，可以使用差分组进行运算
差分数组指的是当前数组与前一个数组进行做差，并储存在新的数组中
公式即 c[i]=a[i]-a[i-1]（公式不唯一）

例子：
a[i] 0 0 0 0 0
c[i] 0 0 0 0 0

砍伐1-3
a[i] 0 1 1 1 0
c[i] 0 1 0 0 -1

从这个例子可以看出在对一个区间进行加减操作时只需要变化c[a]和c[b+1] 即可
在得出变化后的差分组后，可反向推导公式
a[i]=c[i]+a[i-1]
只需要遍历一次就可以解决问题，成倍的提高效率。。。

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        c[l]++;
        c[r+1]--;
    }

a[0]=c[0];
    for(i=1;i<=len;i++)
    {
        a[i]=a[i-1]+c[i];
    }

for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }

cout<<ans<<endl;
    return 0;
}

```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

李嘉

为什么要a[0]=c[0]; 不应该是原数组的值赋给差分数组吗，还有为什么要放到修改完数组再赋给第一个值，而不是一开始就进行赋值

2023-09-26 21:23:29

sor

9个头文件，啥个意思？

2021-11-02 23:09:26

HRBUST

TA的其他文章

你可能喜欢

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

用筛法求之N内的素数。（C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

逆反的01串（C++代码）（依旧推荐switch）

简单易懂应对多次操作的差分组解法

评论区

精彩推荐

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

兰顿蚂蚁（C++代码）

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

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

C语言训练-求函数值（C语言代码）

IP判断（C语言代码）

完数（C语言代码）

一元一次方程（C语言代码）

1162答案错误，为什么

小O的乘积（C++代码）

HRBUST

TA的其他文章

你可能喜欢

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

用筛法求之N内的素数。 （C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

逆反的01串 （C++代码）（依旧推荐switch）

简单易懂 应对多次操作的差分组解法

评论区

精彩推荐

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

兰顿蚂蚁 （C++代码）

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

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

C语言训练-求函数值 （C语言代码）

IP判断 （C语言代码）

完数 （C语言代码）

一元一次方程 （C语言代码）

1162答案错误，为什么

小O的乘积 （C++代码）

用筛法求之N内的素数。（C++代码）

逆反的01串（C++代码）（依旧推荐switch）

简单易懂应对多次操作的差分组解法

　　评论区

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

兰顿蚂蚁（C++代码）

C语言训练-求函数值（C语言代码）

IP判断（C语言代码）

完数（C语言代码）

一元一次方程（C语言代码）

小O的乘积（C++代码）