954. [河南省队2012] 莫比乌斯圈

【问题描述】

莫比乌斯圈(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】

【数据范围】 

40%的数据N<=10000 Q<=10000

100%的数据N<=100000 Q<=100000