网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[河南省队2012]莫比乌斯圈
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | mobius.in | 输出文件 | mobius.out |
【问题描述】
莫比乌斯圈(Möbius strip)如下图
可以理解为一个纸带从某处剪断,扭一圈,然后再用胶水粘合的物体.
关于这个莫比乌斯圈有很多有趣的性质,当然也很复杂,这里不会赘述,但是需要说一点,如果你从圈上的某处出发并前进,那么如果你在走了N/2个单位距离发现起始点在你的背面,那么就称这个带的长度为N(也就意味着你需要绕N的距离才能返回原点)
我们的问题是:
想象”侠盗猎车手”里面的任务骑着摩托车在一个长度为N的莫比乌斯带上踩加分点(我们认为每隔一单位长度就有一个加分点,这个加分点是个整数.我们想知道从位置a开始骑摩托吃分到位置b所有可能的得分之和,我们假设只要他经过得分点就一定能得到分,并且他可能骑车在c处(a<=b<=c)停下来,而放弃b+1到c之间的得分.可是这得分点的分值有时候会变,我们如果想知道从a到b的总分值是多少,就会询问,所以
【输入】
第一行两个整数N,Q,Q是操作数
第二行N个整数表示随便从一个点开始,到之后N个单位长度之间N个加分点的分值,
第三行一个整数Command,表示操作数
接下来Command行每一行由一个指令类型(一个字符串,中间没有空格),后面跟相应的参数.
要么是”C” a b x表示从a到b将键值修加x
要么是”Q” a b 表示询问从a到b之间我们想询问的值,具体见题目描述.
【输出】
对于每个询问给出相应的回答一共Command行
【输入输出样例1】
mobius.in |
mobius.out |
4 5 C 1 4 2 C 1 2 -1 Q 1 2 Q 2 4 Q 1 4
|
3 9 13
|
【数据范围】
40%的数据N<=10000 Q<=10000
100%的数据N<=100000 Q<=100000