P4879 ycz’s Girls

ycz has a lot, a lot of girls (ycz: just kidding).

The legendary ycz has $n$ childhood sweethearts, and they live in cities numbered $1 \sim n$. When they were young, they were pretty and cute. But as time went by, some girls’ looks changed. Since ycz is very sentimental and cannot bear to abandon them, he recorded the amount of change in their looks. We use $C, x, y$ to mean that the girl in city $x$ has her looks decreased by $y$. After growing up, ycz became very charming, and many girls fell for him. We use $I, x, y$ to mean that in city $x$ a girl appears who likes ycz, and her looks value is $y$ ($y$ may be negative, but ycz accepts everyone). However, some girls quarrel with ycz and then break up. We use $D, x$ to mean that the **$x$-th girl** breaks up with ycz. Recently, ycz is going to visit his girls all around the country. For easier calculation, we can treat the cities where his girls are as points on a straight line, placed next to each other. ycz is already tired from keeping in touch with his girls, so he gives you this task: He wants to know, at some time, how much “happiness” he can get by visiting all of his girls. This happiness is defined as the sum of the girls’ looks values he visits. Your job is to compute this sum (note that after growing up, a girl’s looks value may be negative). Note: Each city is allowed to have only one girl. That is, a girl who appears later in a city will drive away the previous girl in that city ~~(two girls cannot share one city)~~. UPD: Childhood sweethearts all like ycz. The $x$-th girl to break up is not the girl in city $x$. It means the girl in the $x$-th city (counting from left to right) that currently has a girl. Childhood sweethearts become “girls” after growing up. The modified value $y$ is not negative, but the looks value may become negative after subtraction.

ycz has $5 \times 10^5$ cities. Initially, each of the first $n$ cities has one girl, and the initial looks value of the girl in city $i$ is $a_i$. There are $m$ operations of the following four types. - `C x y` The looks value of the girl in city $x$ decreases by $y$. - `I x y` A girl with looks value $y$ appears in city $x$. If there was already a girl in city $x$ before, the previous girl is driven away. - `D x` The girl in the $x$-th city (among the cities that currently have a girl) breaks up with ycz. - `Q` ycz wants to know the total sum of looks values of all his girls.

For each `Q`, output one integer.

**Sample explanation:** The looks values change as follows. Deleted ones are not written below. ``` 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 ``` For 30% of the testdata, $1 \le n,m \le 10$. For 70% of the testdata, $1 \le n,m \le 1000$. For 100% of the testdata, $1 \le n,m \le 100000,|a_i|,|y| \le 10^9$. Translated by ChatGPT 5