51nod3658 小明统计数组

51nod3658 小明统计数组

3658 小明统计数组

小明最近喜欢上数组统计，但是他遇到了一道难题，题目如下：

最初数列是空的，那么一共有下面五种操作：

1. a x 表示向数列里面增加数值为x的数；

2. d x 表示删除数列里面数值为x的数；

3. I 表示删除数列里面数值最大的数；

4. m 表示删除数列里面数值最小的数；

5. q 询问当前数列的和。

保证添加的元素都不不一样，对于删除操作，如果数列里面不存在这个元素，则不进行删除操作。小明不会做这个题，希望寻求你的帮助，聪明的你可以帮助小明解决这个问题吗？

在处理输入的时候要特别注意！题目中操作 3 的操作字符是 大写的 i，而不是小写的 l。

输入

第一行输入两个数n，表示操作的数目；
之后n行，每行为题目中描述的五种操作。

输出

对于每个询问，输出当前数列的和。

数据范围

1<=n<=100000
1<=x<=100000且x互不相同

输入样例

11
a 1
d 2
q
a 2
a 3
a 4
q
I
q
m
q

输出样例

1
10
6
5

样例解释

 a 1 增加1到数列里面
 d 2 删除数列里面数值为2的元素，因为数列里面没有，所以不进行操作
 q 询问，当前数列的和为1
 a 2 增加2到数列里面
 a 3 增加3到数列里面
 a 4 增加4到数列里面
 q 询问，当前数列的和为10
 I  删除数列里面数值最大的元素，删除4
 q 询问，当前数列的和为6
 m 删除数列里面数值最小的元素，删除1
 q 询问，当前数列的和为5

解析：

由于题目中每个元素都是不同的，且有删除最大值和最小值的操作，所以我们可以用一个 set 来维护这个数列，时间复杂度为O(nlogn)。

set 可以直接删除具体的元素，因为 set是有序的，所以最小值是第一个，最大值是最后一个，直接进行删除即可，我们可以用一个变量来维护当前数列元素的总和。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){set<int> s;int t, sum = 0;  cin >> t;while(t--){char op;  cin >> op;int x;if(op == 'a'){cin >> x;s.insert(x);sum += x;}else if(op == 'd'){cin >> x;if(s.find(x) != s.end()){s.erase(x);sum -= x;}}else if(op == 'm'){if(!s.empty()){sum -= *(s.begin());s.erase(*s.begin());	}}else if(op == 'I'){if(!s.empty()){sum -= *(--s.end());s.erase(*--s.end());	}}else if(op == 'q'){printf("%dn", sum);}}return 0;
}