题目描述
样例
input
3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5
output
-5
-7
-13
-13
-18
算法1
(差分)
本题考察差分序列的性质,设原数组为$a_{i=1,2,..n}$,差分数组为$b_{i=1,2,…n}$。
差分数组里的每一项$b_i$都是相对于原数组$a_{i-1}$的差值,即$b_i=a_i-a_{i-1}$。
由此性质得:
1、通过$b_i$可以计算出$风的温度$=$\sum\limits_{i=1}^nb_i$。
2、每次$l~r$的地壳变化,只会改变$b_l,b_{r+1}$的两个端点值。
3、每次求得的风的温度都要删去原始的$b_l,b_{r+1}$,再加上变化后的$b_l,b_{r+1}$。
注意:当$r=n$时不能减去$b_{r+1}$的值。
时间复杂度
$O(n)$
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e7+10;
typedef long long LL;
LL a[N],b[N];
int n,q;
LL s,t;
void insert(int l,int r,LL c)
{
a[l]+=c;
a[r+1]-=c;
}
LL get(LL x)
{
return x>0?-(x*s):-(x*t);
}
int main()
{
scanf("%d%d%lld%lld",&n,&q,&s,&t);
LL ans=0;
for (int i = 0; i <= n; i ++ ) {
LL x;
scanf("%lld", &x);
insert(i,i,x);
ans+=get(a[i]);
}
for (int i = 1; i <= q; i ++ )
{
int l,r;
LL x;
scanf("%d%d%lld",&l,&r,&x);
ans-=get(a[l]);
a[l]+=x;
ans+=get(a[l]);
if(r!=n)ans-=get(a[r+1]),a[r+1]-=x,ans+=get(a[r+1]);
cout<<ans<<endl;
}
}