2 shunfurh shunfurh 于 2017.01.10 22:27 提问

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个回答

caozhy
caozhy   Ds   Rxr 2017.01.16 23:41
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
php.ini中notice级的错误提示
php.ini ; Common Values: ;   E_ALL (Show all errors, warnings and notices including coding standards.) ;   E_ALL & ~E_NOTICE  (Show all errors, except for notices) ;   E_ALL & ~E_NOTICE & ~E_STR
精益软件开发(Lean Software Development)
Introducing Lean Software Development IntroductionAs software systems grow more complex and more people become involved, managing software development becomes increasingly difficult. For years, en
Development Mode 和 Production Mode
就是这一段@rem Set Production Mode.  When set to true, the server starts up in production mode.  When@rem set to false, the server starts up in development mode.  The default is false.set START
Implementing Customer Relationship Management
CRM is concerned with creating improved shareholder value through the use of customer- centric business processes and the development of appropriate relationships with consumers.
hdu 4037 线段树 Development Value
题意:http://acm.hdu.edu.cn/showproblem.php?pid=4037 解:数据结构 线段树       这题特别的地方在于前面的东西会影响到之后的所有。
【Unity3d】关于打APK包勾选DevelopmentBuild摄像机正常,不勾则不正常问题
一:问题描述 前天打包时,碰到了这样的问题:生成android APK包时,勾选和非勾选developmentbuild选项,在真机上测试时,不同机型表现不同; 二:现象如下 三星的表现完成正常,小米和酷派却是下面的画面:即显示主相机天空盒背景,但是音乐和点击却没有问题;在点击过程中,播放粒子特效后,画面就马上恢复; 三:临时解决 找来找去,看到其他啊猿都说,
Centos Development Tools 安装
yum groupinstall "Development Libraries" yum groupinstall "Development Tools" yum install ncurses-devel zlib-devel texinfo gtk+-devel gt
自动弹出Microsoft Development Environment窗口的解决故障
该文档解决VS6.0会出现自动弹出Microsoft Development Environment窗口的现象
Java SE Development Kit的下载、安装及环境变量的配置
目前Java SEDevelopment Kit最新的版本为Java SE Development Kit 8u112(以下简称JDK)。下面将逐步介绍该版本Java SDK的下载、安装步骤及其环境变量的配置。 一、JDK下载(推荐在ORACLE官网中下载) 1.在浏览器地址栏中输入http://www.oracle.com/technetwork/java/javase/downloads/
Signing for "xxx" requires a development team. Select a development team
出现这个问题的原因是你的team没有设置对。 解决办法,TARGETS---->Genernal----->Signing------>team,选择合适的选项,编译即可 或者更改一下Bundle Identifier 。