[week5] TT's Magic Cat——差分

题意

Thanks to everyone’s help last week, TT finally got a cute cat. But what TT didn’t expect is that this is a magic cat.

One day, the magic cat decided to investigate TT’s ability by giving a problem to him. That is select n cities from the world map, and a[I] represents the asset value owned by the i-th city.

Then the magic cat will perform several operations. Each turn is to choose the city in the interval [l,r] and increase their asset value by c. And finally, it is required to give the asset value of each city after q operations.

Could you help TT find the answer?

【多亏了上周大家的帮助，它终于得到了一只可爱的猫。但没想到这是一只神奇的猫。

有一天，神奇的猫决定调查TT的能力，给他一个问题。即从世界地图中选择n个城市，a[I]表示第I个城市拥有的资产价值。

然后，这只神奇的猫将执行几项操作。每轮选择[l,r]区间内的城市，并将其资产价值增加c。最后，需要给出q操作后各城市的资产价值。

你能帮我找到答案吗?】

Input

The first line contains two integers n,q (1≤n,q≤2·10^5)— the number of cities and operations.

The second line contains elements of the sequence a : integer numbers a1,a2,…,an (−10^ 6 ≤ a i≤ 10^ 6).

Then q lines follow, each line represents an operation. The i-th line contains three integers l,r and c (1≤l≤r≤n,−10^ 5≤c≤10^ 5) for the i-th operation.

【第一行包含两个整数n,q(1≤n,q≤2·10^5)——城市和操作的数量。

第二行包含序列a的元素:整数a1,a2，…，an(−10^ 6≤a i≤10^ 6)。

接下来是q行，每一行代表一个操作。第i行包含3个整数l,r和c(1≤l≤r≤n，−10^ 5≤c≤10^ 5)】

Output

Print n integers a1,a2,…,an one per line, and ai should be equal to the final asset value of the i-th city.

【打印n个整数a1,a2，…，每行一个，ai应该等于第i个城市的最终资产价值】

输入输出

提示

---

分析

这道题重点在于理解差分优化的特点和原理。

---

• 差分的原理和特点

差分是将一组数进行二次构造的方式。

一组数a1～an（不论是否有序）

可以将其转换为同样有n个的一组差分数：

bi = ai - a(i-1)
（当i=0时，b0 = a0）

即，差分数组中每一个数为原数组中相同下标处所存数与其前一个数的差值。

则，a1～an与构造的差分数组关系为：

a0 = b0
a1 = a0 + (a1 - a0) = b0 + b1
a2 = a1 + (a2 - a1) = a1 + b2 = b0 + b1 + b2
.......
ai = a(i-1) + (ai - a(i-1)) = a(i-1) + bi = b0+...+bi

差分数组一般不作为一个完整的算法去解决问题，而是用于算法中的部分操作进行优化。

• 根据差分原理的优化

显然想要构造一个差分数组是非常容易的。那么根据它的原理可以进行什么优化呢？

假设有一组数a1～an，现在需要将这组数中的ai～am( 1 ≦ i ≦ m ≦ n ）都加上一个c。如何快速求出新的这组数？

原数组的每一个数实际上都是通过累加其之前的所有差值得到的。因此，要想将一系列连续的数同上加上相同c，只需要将这一串数中的第一个数的差分数加上c即可。之后的数都要通过叠加该差分数得到，因此就可以实现在原数的基础上增加c。

ai = a(i-1) + (ai - a(i-1)) + c = a(i-1) + bi + c = b0+...+ (bi + c)

ai+1 = ai + (a(i+1) - ai) + c = ai + b(i+1) + c = b0+...+(bi + c )+ b(i+1)

.......

am = a(m-1) + (am - a(m-1)) + c = a(m-1) + bm + c = b0+...+(bi + c )+ ...+bm

但是，区间外的数不需要加上c，又该如何处理呢？

显然，通过以上的举证，可以得知：若在最后一个需要增加c的数的下一个数的差分数减去c，就能使之后叠加该差分数所有的数都抵消之前增加的c，从而不改变原数。

---

• 代码实现

这道题就是以上举例的应用。因此只需要先构造出差分数组，再将范围内的差分数组都加上给定的c，并将范围之后的第一个差分数减去c，就可以实现题目要求。

这些都可以通过简单的循环和计算完成。具体过程参考本代码。

---

• 本次程序遇到的问题

1. 边界问题

在将范围外第一个差分数减去c还原的操作中，需要注意一下数组边界问题。当需要增加c的数范围的右端点正好是整个数组序列的最右端时，就不再需要进行该操作。

---

总结

1. 还需要在以后遇到的具体情况中进一步熟悉如何用差分进行优化
2. 简单的题目快速AC的感觉真好呜哇哇????

---

代码

//
//  main.cpp
//  lab-b
//
//

#include <iostream>
#include <vector>
using namespace std;

vector<long long> value;
vector<long long> difference;

int main()
{
    ios::sync_with_stdio(false);
    
    int n = 0,q = 0,l = 0,r = 0;
    long long a = 0,num = 0;
    cin>>n>>q;
    
    for( int i = 0 ; i < n ; i++ )          //存储所有资产
    {
        cin>>a;
        value.push_back(a);
    }
    
    difference.push_back(value[0]);
    //生成资产的差分数组，（即每个差分值都为当前资产与上一个资产值的差值）
    
    for( int i = 1 ; i < n ; i++ )
        difference.push_back(value[i] - value[i-1]);
    
    while( q-- )                        //在[l,r]区间都增加num，则将第l个差分值加num就可以
    {
        cin>>l>>r>>num;
        
        difference[l-1] += num;
        if( r < n )                     //当且仅当r不为最后一个资产值时
            difference[r] -= num;
        //但是，第r+1个资产要减去num，才能让区间之后的资产值不受影响，抵消第l个增加的num
    }
    
    value[0] = difference[0];
    cout<<value[0]<<" ";

    for( int i = 1 ; i < n ; i++ )
    {
        value[i] = value[i-1] + difference[i];          //计算新的资产值，并逐个输出
        cout<<value[i]<<" ";
        
    }
    
    cout<<endl;
    
    return 0;
}