[TJOI 2010]中位数

Description

给定一个由N个元素组成的整数序列，现在有两种操作：
1 add a
在该序列的最后添加一个整数a，组成长度为N + 1的整数序列
2 mid 输出当前序列的中位数
中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）
例1：1 2 13 14 15 16 中位数为13
例2：1 3 5 7 10 11 17 中位数为7
例3：1 1 1 2 3 中位数为1

Input

第一行为初始序列长度N。第二行为N个整数，表示整数序列，数字之间用空格分隔。第三行为操作数M，即要进行M次操作。下面为M行，每行输入格式如题意所述。

Output

对于每个mid操作输出中位数的值

Sample Input

6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid

Sample Output

5
13

HINT

对于30%的数据，1 ≤ N ≤ 10,000，0 ≤ M ≤ 1,000
对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000
序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复
每个测试点时限1秒

题解

这道题的思路还是容易想的，
我们可以将数列按大小均分两段，
前一段用大根堆维护，后一半用小根堆维护，
询问/加入时我们只要拿出两个堆顶讨论就好了。

 1 #include<set>
 2 #include<map>
 3 #include<ctime>
 4 #include<cmath>
 5 #include<queue>
 6 #include<stack>
 7 #include<vector>
 8 #include<cstdio>
 9 #include<string>
10 #include<cstring>
11 #include<cstdlib>
12 #include<iostream>
13 #include<algorithm>
14 #define LL long long
15 using namespace std;
16 const int N=100000;
17 
18 int n,m,x;
19 int a[N+5];
20 bool comp(const int &a,const int &b) {return a<b;}
21 priority_queue<int>A;
22 priority_queue<int,vector<int>,greater<int> >B;
23 char ch[5];
24 
25 int main()
26 {
27     scanf("%d",&n);
28     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
29     sort(a+1,a+n+1,comp);
30     int mid=(n>>1)+(n&1);
31     for (int i=1;i<=mid;i++) A.push(a[i]);
32     for (int i=mid+1;i<=n;i++) B.push(a[i]);
33     scanf("%d",&m);
34     while (m--)
35     {
36         scanf("%s",ch);
37         if (ch[0]=='m') printf("%d
",A.top());
38         else if (ch[0]=='a')
39         {
40             scanf("%d",&x);
41             A.push(x);
42             B.push(A.top());
43             A.pop();
44         }
45         if (A.size()<B.size())
46         {
47             A.push(B.top());
48             B.pop();
49         }
50     }
51     return 0;
52 }