洛谷P3871 [TJOI2010]中位数 题解

题目链接：P3871 [TJOI2010]中位数

题意：

给定一个由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

对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000

序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复

考虑维护一个对顶堆，详细见 P1168

然后就是板子题，注意对询问分类讨论

时间复杂度 $O((n+m) \log (n+m))$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
void clear()
{
    while(!q1.empty())q1.pop();
    while(!q2.empty())q2.pop();
}
void solve(int x,int f)
{
    if(f)
    {
        if(q1.size()<q2.size())cout << q2.top() << '\n';
        else cout << q1.top() << '\n';
    }else
    {
        if(!q1.empty()&&x<=q1.top())q1.push(x);
        else q2.push(x);
        while(abs((int)(q1.size()-q2.size()))>1)
        {
            if(q1.size()>q2.size())q2.push(q1.top()),q1.pop();
            else q1.push(q2.top()),q2.pop();
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,x; char op[5];
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> x;
        solve(x,0);
    }
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> op;
        if(op[0]=='a')
        {
            cin >> x;
            solve(x,0);
        }else solve(x,1);
    }
    return 0;
}