问题 1297. -- Tr0y And His Startup

1297: Tr0y And His Startup

时间限制: 1 Sec  内存限制: 256 MB
提交: 18  解决: 8
[提交][状态][讨论版]

题目描述

Tr0y创办了一家安全公司,主要提供抗DDoS服务。
假设有n家公司共用Tr0y的第三方服务器,各公司初始最大承受带宽为xi Gbps,当其受到大于或等于最大承受带宽流量时,会判断为DDoS攻击并进行清洗操作,将流量引到第三方服务器。
下面有Q次攻击,每次使得[Li,Ri]的公司遭受到流量为c Gbps(c为整数,在[1,C]上离散均匀分布)的攻击,且每家公司在承受攻击后会增大qi Gbps的最大承受带宽。
Tr0y的资金有限,他想知道每次攻击时,他的服务器期望承受流量为多少?
答案应该会很大,请膜1e9+7

输入

第一行为三个整数n(1<=n<=1e5),C(1e7<=C<=1e9),Q(1<=n<=1e5)。
第二行含n个整数xi(1<=xi<=10)。
接下来Q行,每行包含三个整数L,R(1<=L<=R<=n),q(1<=q<=10).

输出

共Q行,每行输出服务器期望承受流量.

样例输入

3 10000000 3
1 2 3
1 1 1
1 2 1
1 3 1

样例输出

505000004
581428605
86428702

提示

来源

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