问题 1297. -- Tr0y And His Startup

1297: Tr0y And His Startup

时间限制:1000 ms 内存限制:256 MB
提交:30 解决:9
[ 提交][ 状态][ 讨论版]

题目描述

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

提示

来源

西电2018校赛现场赛

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