前奇数项求中位数

给定一个长度为 N 的非负整数序列 A，对于前奇数项求中位数。

P1168

输入格式

第一行一个正整数 $N$。
第二行 $N$ 个正整数 $A_{1\dots N}$。

输出格式

共 $?\frac{N+1}{2}?$ 行，第 $i$ 行为 $A_{1\dots 2i?1}$ 的中位数。

样例输入 1

7
1 3 5 7 9 11 6

样例输出 1

1
3
5
6

样例输入 2

7
3 1 5 9 8 7 6

样例输出 2

3
3
5
6

第一次看到这里，首先冒出来的想法是排序（笑死，根本不会 ），先在这里分析一下，我们需要动态地维护，如果先排序再遍历，就会打乱顺序，这题还可以转化为求区间第k大值，看了dalao的题解，秀的天花烂醉，树状数组、权值线段树、主席树、平衡树、二叉排序树、链表······（T-T）

排序

• 方法1
  每插入一个数，就插入在大于等于该数的位置，类似插入排序的操作，使得每次插入之后的数组是有序的，当插入的第i个为奇数，就输出第$\frac{i?1}{2}$个数
  优化：找到大于等于该数的位置可以用二分（$lower$_$bound$）
• 方法2
  每当插入的第i个为奇数，就对数组排序一次，然后输出第$\frac{i?1}{2}$个数，，很遗憾超时

对顶堆

维护两个堆：大顶堆、小顶堆
通俗点就是从中间把大堆切开，左边叫大顶堆，右边叫小顶堆

• 默认$Q2.size>=Q1.size()$，也意味着第一个元素进$Q2$
• 小顶堆的所有元素都比大顶堆的所有元素大

那么该如何实现呢？
两个堆直接用$priority$_$queue$更方便，大顶堆$Q1$，小顶堆$Q2$

1. 如果插入的元素比$Q2.top()$还要小，就放到$Q1$里面，否则放到$Q2$里
2. 然后维护$Q2.size()>=Q1.size()$,当$i$为奇数，输出$Q2.top()$就是答案

最后，献上代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,less<int> >Q1;//大顶堆 
priority_queue<int,vector<int>,greater<int> >Q2;//小顶堆 
int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n;cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		if(i==1) Q2.push(x); //第一个元素进Q2
		else{
			if(x<Q2.top()) Q1.push(x); //比Q2.top()大，就进Q2
			else Q2.push(x);		
		}
		if(i&1){ 
			//维护，使第奇数次，Q2比Q1始终多一个元素
			while(Q2.size()-Q1.size()!=1){ 
				if(Q2.size()>Q1.size())  Q1.push(Q2.top()),Q2.pop();
				else Q2.push(Q1.top()),Q1.pop();
			}
			//输出 
			cout<<Q2.top()<<endl;	
		} 
	}
}