AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 797. 差分    原题链接    简单

作者: 作者的头像   自由周某 ,  2020-07-22 18:53:26 ,  所有人可见 ,  阅读 1480


25


10

当时看y总的视频,很难理解为什么要假设a,b数组全部是0,然后把a[i]插入b,就
得到了差分数组。在此写一下自己的理解。
这个操作必须是b已经是a的差分数组的前提下

例如,我们已经知道b是a的差分数组,我只想让某个a[i]加上一个数,比如只想让a[5]加上3
那我就要insert(5,5,3),这对a[5]之前和之后的数是没有影响的,并且操作之后,b仍然是a的差分数组(这是重点)
如果没有这个操作,b就不再是a的差分数组
所以我们知道,如果a[i]改变,要想让b仍然是a的差分数组,那么就要进行insert(i,i,c)操作。
为什么要让b仍然是a的差分数组?因为我们要解题嘛,所以我们要维持a,b的关系

到这里就很明朗了

由于刚开始啊a,b全都是0,b显然是a的差分数组,因为b满足a[i] = b[1] + b[2] + … +b[i] = 0
现在a不是0了,因为a[1]加上了某个数,我们要想让b仍然是a的差分数组,那么就要进行相应的改变
怎么变?就是insert(1,1,c)嘛,c是什么?就看a[1]加上了什么咯。刚开始a[1]是0嘛,后来变成了某个数,即a[1]
所以c就是a[1]嘛,于是我们进行了insert(1,1,a[1])操作,以维持a,b间的关系。
同理,当a[2],a[3]....a[n]依次改变,我们依次进行相应的操作。
所以这就是insert(i,i,a[i])的来源


 #include<iostream>
using namespace std;
const int N = 1e6+5;
int a[N], b[N];
void insert(int l , int r , int x){
    b[l] += x;
    b[r + 1] -= x;
}
int main(){

    int n , m;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++)
        insert(i,i,a[i]); //这一步是改变b,使得b仍然是a的差分数组

    while(m--){//这一步是主要操作,通过操作差分数组b,间接使得把a数组【l,r】里面的数全部加上c
        int l, r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }    

    //差分数组b的前i项和就是a【i】
    for(int i = 1; i <= n; i++) b[i] = b[i - 1] + b[i]; //把b数组前i项求和,这时候b【i】就变成了a【i】

    for(int i = 1; i <= n; i++) a[i] = b[i]; //把b【i】赋给a【i】

    for(int i = 1; i<=n; i++)cout<<a[i]<<" ";

    return 0;
}

4 评论


用户头像
一只小锦李   2021-01-27 23:48         踩      回复

哈哈,明白了,非常感谢


用户头像
cony   2021-01-04 14:54         踩      回复

您好,我想问下
insert(i,i,a[i]); // 就是把a数组的值一 一对应插到b数组
insert(l,r,c); // 将b中[l, r]之间的每个数加上c。
b[i] += b[i - 1] //求b的前缀和 即 a序列
这样理解对吗

用户头像
自由周某   2021-01-08 12:39      2    踩      回复

是可以这么理解,不过这里insert(l, r, c) 的作用应该是:b数组左端点 L 加c,右边的R+1减c,然后在求b的前缀和(即a序列)时,a序列的(L, R)每个数都加上了c,并不是将b的每个数都加了c,而是求前缀和后导致a的每个数加了c

用户头像
自由周某   2021-01-08 12:40    回复了 自由周某 的评论         踩      回复

导致a的(l, r)区间内每个数加了c


你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息