欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1013. -- 挖掘机

1013: 挖掘机

时间限制: 1 Sec  内存限制: 128 MB
提交: 227  解决: 51
[提交][状态][讨论版]

题目描述

挖掘机是一种非常著名的机器。现在需要修筑一条长度为n米的公路,已知公路第i~(i+1)米内的海拔高度hi(0<=i<n,1米范围内的微小起伏可以忽略),为了使公路尽量平整,可以用挖掘机对第l米到第r米之间的(r-l)个路段(1米长)进行一次挖掘操作,使这些路段的海拔都降低k米。已知项目负责人规划的m次挖掘操作,请求出操作后公路的平整度。

平整度定义为,各路段海拔高度与平均海拔高度之差的平方和。为了避免浮点误差,平均海拔向零的方向舍入到最近整数,例如2 4 5的平均数是3.6666667,我们将其舍入到3;-2 -4 -5的平均数是-3.6666667,我们将其舍入到-3。

数据范围:1<=n,m<=105,0<=l<r<=n,|hi|<=104,1<=k<=10。

输入

输入文件包含多组数据。

每组数据,第1行,一个整数n。
第2行,n个用空格分割的整数h0,h1,h2,...,hn-1
第3行,一个整数m。
之后m行,每行3个整数l、r、k。

输出

对于每组数据,输出1行,包含1个整数,表示公路的平整度。

样例输入

5
1 2 2 2 1
1
1 4 1
7
1 2 1 2 1 2 1
2
1 2 1
3 4 1

样例输出

0
1

提示

来源

[提交][状态][讨论版]