#399. 星际补给站:五人共享宝箱(一维 vector)

星际补给站:五人共享宝箱(一维 vector)

星际补给站:五人共享宝箱(一维 vector)

题目描述

武锦澄、曹智钦、崔馨月、包瑞鑫、宋奕霏组成了“星际补给小队”。他们从废弃空间站找到一条有顺序的能量球队列,每颗球有一个非负整数能量值。

五位队员轮流操作这个队列:

  • W x:武锦澄把能量为 x 的球放到队尾。
  • C p x:曹智钦在当前队列的第 p 个位置前面插入能量为 x 的球。若 p 等于当前长度加一,就放在队尾。
  • X p:崔馨月拿走当前第 p 颗球,之后的球依次向前移动。
  • B p x:包瑞鑫把当前第 p 颗球的能量直接修改为 x。
  • S l r:宋奕霏扫描队列中第 l 到第 r 颗球(含两端),请输出它们的能量总和。

队列中的位置从 1 开始编号,所有操作都按输入顺序执行。题目保证所有操作的位置在操作发生时都是合法的。

请回答每次 S 操作的结果。

输入格式

第一行包含两个整数 n q,表示最开始的能量球数量和操作次数。

第二行包含 n 个非负整数,表示初始队列中从前往后的能量。若 n=0,这一行可以为空。

接下来 q 行,每行是一条上述五种格式之一的操作。

输出格式

每次遇到 S l r 操作,输出一行整数,表示此时区间 [l,r] 的能量之和。若不存在 S 操作,则不输出内容。

数据范围

  • 0≤n≤500\le n\le 50,1≤q≤20001\le q\le 2000。
  • 所有球的能量值均在 [0,109][0,10^9] 内。
  • 插入的位置满足 1≤p≤当前长度+11\le p\le \text{当前长度}+1。
  • 删除、修改位置与扫描区间均保证合法。
  • 各操作发生后,队列长度不会超过 20502050。
  • 答案可能超过 32 位整数范围,请使用 64 位整数保存区间和。

输入样例

5 8
3 1 4 1 5
S 2 4
W 9
C 3 2
S 1 4
X 2
B 5 7
S 4 6
S 1 6

输出样例

6
10
17
26

样例说明

最初队列为 [3,1,4,1,5]。添加 9 并在第 3 个位置插入 2 之后,队列变为 [3,1,2,4,1,5,9];移走第 2 颗球,再把第 5 颗球改为 7,得到 [3,2,4,1,7,9]。

学习提示

本题适合使用 vector<long long> 维护有序序列,练习 push_back、insert、erase、下标访问和 size。操作次数较少,允许直接遍历求和。