题目:
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]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?
input:
The first line contains two integers n,q (1≤n,q≤2⋅105) — the number of cities and operations.
The second line contains elements of the sequence aa: integer numbers a1,a2,…,an(−106≤ai≤106)
Then qq lines follow, each line represents an operation. The ii-th line contains three integers l,r and c (1≤l≤r≤n,−105≤c≤105) for the ii-th operation.
output:
Print nn integers a1,a2,…,an one per line, and ai should be equal to the final asset value of the ii-th city.
example:
思路:
假设要处理的数组元素的长度为q,该题如果直接使用对原数组进行处理,则时间复杂度为O(q*n);如果将原数组转化为差分数组进行处理,则时间复杂度会降为O(q+n);且如果将原数组转化为差分数组进行处理,将从原来的区间修改转变为点的修改,即A[L,R]会变为B[X]+=C,B[Y+1]-=C,差分数组B的前缀和就是A修改后的最终值。综上,在这选用差分数组进行操作。
注意:
此题要用long long类型进行处理,而不是int类。
代码:
#include <iostream>
using namespace std;
const int N = 1e7;
long long n, k, x, y, c;
long long a[N], b[N], temp[N];
void change()
{
b[1] = a[1];
for (long long i = 2; i <= n; i++)
{
b[i] = a[i] - a[i - 1];
}
}
int main()
{
while (scanf_s("%lld %lld",&n,&k)!=EOF)
{
for (long long i = 1; i <= n; i++)
scanf_s("%lld", &a[i]);
change();
for (long long i = 0; i < k; i++)
{
scanf_s("%lld %lld %lld", &x, &y, &c);
b[x] += c;
b[y + 1] -= c;
}
temp[1] = b[1];
cout << temp[1];
for (long long i = 2; i <= n; i++)
{
temp[i] = temp[i - 1] + b[i];
cout << ' ' << temp[i];
}
cout << endl;
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)