ycz的妹子
题目背景
ycz 有很多很多的妹子(ycz:瞎说)
题目描述
机房神犇 ycz 有 $n$ 个青梅竹马,她们分别住在 $1~n$ 号城市中。小时候的她们美丽可爱,但是由于女大十八变,有些妹子的颜值发生了变化,但是十分重感情的 ycz 神犇不忍心抛弃她们,于是记录下来了她们颜值变化的值,我们用 $C, x, y$ 表示第 $x$ 个城市的妹子的颜值下降了 $y$ 。长大之后的 ycz 非常有魅力,有许多妹子被 ycz 迷得神魂颠倒,我们用$I, x, y$ 表示第 $x$ 个城市有一个妹子喜欢上了 ycz ,她的颜值为 $y$ ( $y$ 有可能是负数,但是 ycz 来者不拒)。但在中途有一些妹子和 ycz 吵架了,于是就分手了,我们用 $D, x$ 表示**第 $x$ 个妹子**和 ycz 分手了。
最近神犇 ycz 要去全国各地找他的妹子们,为了方便计算,我们珂以把 ycz 的妹子所在的城市当作是一条直线,并且挨在一起。神犇 ycz 由于忙于和他的妹子们联系此时已经很累了,于是交给你一个这样的任务:他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度,这个愉悦度为他找的妹子的颜值数,你要做的就是求出这个愉悦度之和(注意长大后妹子们的颜值可能为负数/滑稽)。
注意:每个城市只允许有一个妹子,也就是说后来喜欢上 ycz 的妹子会赶走之前这个城市喜欢 ycz 的妹子~~(一城不容二女)~~。
UPD:
青梅竹马都是喜欢 ycz 的。
分手的第 $x$ 个妹子不是第 $x$ 城市的妹子,是指从前往后数第 $x$ 个有妹子的城市的妹子。
青梅竹马长大后就是妹子。
修改的值 $y$ 不为负数,但是颜值减去之后可能为负数。
输入输出格式
输入格式
ycz 有 $5 \times 10^5$ 座城市,开始时,前 $n$ 座城市各有一个妹子,第 $i$ 座城市妹子初始的颜值为 $a_i$。
有 $m$ 次以下四种操作。
- `C x y` 第 $x$ 座城市的妹子颜值减少 $y$
- `I x y` 第 $x$ 座城市出现了一个颜值为 $y$ 的妹子,如果在此之前,第 $x$ 座城市已经有妹子,则之前的妹子被驱赶。
- `D x` 第 $x$ 个有妹子的城市 中的妹子与 ycz 分手
- `Q` ycz 想知道他所有妹子的颜值总和是多少
输出格式
对于每一个$Q$输出一个整数
输入输出样例
输入样例 #1
5 10
1 2 3 4 5
Q
C 3 2
Q
I 6 6
Q
D 4
Q
C 5 2
I 7 9
Q
输出样例 #1
15
13
19
15
22
说明
**样例解释:**
妹子颜值变化如下,删除的就没写在下面了。
```
1 2 1 4 5
1 2 1 4 5 6
1 2 1 5 6
1 2 1 3 6
1 2 1 3 6 9
```
对于 30% 的数据,$1 \le n,m \le 10$
对于 70% 的数据,$1 \le n,m \le 1000$
对于 100% 的数据,$1 \le n,m \le 100000,|a_i|,|y| \le 10^9$