动态中位数(对顶堆)

上面是一个小根堆，下面是一个大根堆

维护两个性质：1、小根堆元素>=大根堆元素2、大根堆元素个数比小根堆元素个数多1

结果出堆大根堆top即可

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define x first
#define y second
typedef pair<int,int> PII;
const int N=5e5+10,mod=1e5+3;
int n,m,ans;





int main() {

	//上面是小根堆，下面是大根堆

	int T;
	cin>>T;
	while(T--) {
		cin>>n>>m;
		priority_queue<int,vector<int>,greater<int> >up;//不要开在外部 
		priority_queue<int,vector<int>,less<int> >down;

		cout<<n<<" "<<(m+1)/2<<endl;
		int cnt=0;
		for(int i=1; i<=m; i++) {
			int x;
			cin>>x;
			//上面元素大于等于下面所有元素
			if(down.empty()||x<=down.top())down.push(x);
			else up.push(x);
			//下面个数比上面多1
			if(down.size()>up.size()+1)up.push(down.top()),down.pop();
			if(up.size()>down.size())down.push(up.top()),up.pop();
			if(i&1)//奇数
				printf("%d%c",down.top(),++cnt%10==0 ? '\n':' ');//每10个数换一行

		}
		if(cnt%10)cout<<endl;
	}




	return 0;
}