#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 操作,则不输出内容。
数据范围
- ,。
- 所有球的能量值均在 内。
- 插入的位置满足 。
- 删除、修改位置与扫描区间均保证合法。
- 各操作发生后,队列长度不会超过 。
- 答案可能超过 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。操作次数较少,允许直接遍历求和。