程式設計思維與實踐 Week5 作業 B 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 nn cities from the world map, and a[i]a[i] represents the asset value owned by the ii-th city.

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

Could you help TT find the answer?

簡述：給出n給數，沒有q次操作。每次操作給出一個區間[l,r]，對于該區間中的每個元素，加上c，輸出最終n個數的值

input：

The first line contains two integers n,qn,q (1≤n,q≤2⋅105)(1≤n,q≤2·105) — the number of cities and operations.

The second line contains elements of the sequence aa: integer numbers a1,a2,...,ana1,a2,...,an (−106≤ai≤106)(−106≤ai≤106).

Then qq lines follow, each line represents an operation. The ii-th line contains three integers l,rl,r and cc (1≤l≤r≤n,−105≤c≤105)(1≤l≤r≤n,−105≤c≤105) for the ii-th operation.

簡述：第一行包含兩個整數n，q。第2行到第q+1行，每行三個整數：l r c，表示區間[l,r]，以及要加上的數c

output：

Print nn integers a1,a2,…,ana1,a2,…,an one per line, and aiai should be equal to the final asset value of the ii-th city.

簡述：輸出最終每個數的值

思路：

經典的差分題，對于n個數a[1]~a[n]。令b[1]=a[1]，b[i]=a[i]-a[i-1]。則b的字首和為對應的a[i]

#include<iostream>
using namespace std;
long long ans,a[300010],b[300010];
int n,q,l,r,c;
int main()
{
  cin>>n>>q;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    if(i==1)
      b[i]=a[i];
    else
      b[i]=a[i]-a[i-1];
  }
  for(int i=1;i<=q;i++)
  {
    cin>>l>>r>>c;
    b[l]+=c;
    b[r+1]-=c;
  }
  for(int i=1;i<=n;i++)
  {
    ans+=b[i];
    cout<<ans<<" ";
  }
  return 0;
}