编程介的小学生 2017-01-10 14:27 采纳率: 20.5%
浏览 770
已采纳

Development Value

Problem Description
StarCraft 2 (SC2) is a famous game. More and more people fall in love with this game.

As a crazy fan of SC2, Ahua (flower fairy) play it day and night. Recently, he found that the most important part of being a top player of SC2 is economic development, which means you should get as much mine as possible by training SCVs (space construction vehicle) to collect mine. Train a SCV at ith second costs Ci units of mine. After training, this SCV can collect Di units of mine each second. Training a SCV needs one second of time.

Based on that, he composes a formula to evaluate the development in a time span from xth second to yth second. Assume at xth second, Ahua has no SCV and mine. He trains one SCV at each second during xth second and yth second (the mount of mine can be negative, so that he always can train SCV). Each SCV will collect some amount of mines for Ahua in each second after it was trained. At ith second Ahua has Mi units of mine in total. The development value is defined as sum(Mi) (x ≤ i ≤ y). Now he asks you to help him calculate the development value. To make it more interesting, Ahua can apply following operations:

Cost x y z: the cost of training a SCV between xth second to yth second will increase by z units of mine. i.e. Ci for x ≤ i ≤ y will increase by z.

Collect x y z: each SCV trained between xth second and yth second can collect z more mines every second after it has been trained. i.e. Di for x ≤ i ≤ y will increase by z.

Query x y: output the development value between xth second and yth second.

Input
First line of the input is a single integer T (T ≤ 10), indicates there are T test cases.
For each test case, the first line is an integer N (1 ≤ N ≤ 100000), means the maximum time you should deal with.

Following N lines, each contain two integers Ci and Di (0 ≤ Ci, Di ≤ 100000), the cost and collect speed of SCV training in ith second initially as described above.

The next line is an integer Q (1 ≤ Q ≤ 10000), the number of operations you should deal with. Then Q lines followed, each line will be “Cost x y z”, "Collect x y z” or “Query x y”.
1 ≤ x ≤ y ≤ N, 0 ≤ z ≤ 100000

Output
For each test case, first output “Case k: “ in a single line, k is the number of the test case, from 1 to T. Then for each "Q x y", you should output a single line contains the answer mod 20110911.

Sample Input
1
5
1 3
2 3
3 1
2 2
3 3
5
Query 1 3
Cost 2 2 1
Query 1 3
Collect 1 1 5
Query 1 3

Sample Output
Case 1:
2
0
15

  • 写回答

1条回答

  • threenewbee 2017-01-16 15:41
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗