```cpp
#include <cstdio>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cmath>
#define LEFT_SON(p) (p << 1 | 1)
#define RIGHT_SON(p) ((p + 1) << 1)
#define PARENT(p) ((p - 1) >> 1)
template <typename _RandomAccessIterator, typename _Diff, typename _Comp>
inline void min_heap_adjust(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Diff __index, _Comp comp) {
_Diff siz = __last - __first;
_Diff tar = LEFT_SON(__index);
while (tar < siz) {
_RandomAccessIterator child = __first + tar;
if (tar < siz - 1) {
if (comp(*(child + 1), *child)) {
++tar;
++child;
}
}
if (comp(*child, *(__first + __index))) std::iter_swap(__first + __index, child);
else break;
__index = tar;
tar = LEFT_SON(__index);
}
}
template <typename _RandomAccessIterator, typename _Comp>
inline void pop_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
--__last;
std::iter_swap(__first, __last);
min_heap_adjust(__first, __last, 0, comp);
}
template <typename _RandomAccessIterator, typename _Comp>
inline void push_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
_Diff pos = (__last - __first) - 1;
while (pos && comp(*(__first + pos), *(__first + PARENT(pos)))) {
std::iter_swap(__first + pos, __first + PARENT(pos));
pos = PARENT(pos);
}
}
template <typename _RandomAccessIterator, typename _Comp>
inline void make_min_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
_Diff siz = __last - __first;
_Diff parent = PARENT(siz);
while (true) {
min_heap_adjust(__first, __last, parent, comp);
if (!parent) return;
--parent;
}
}
template <typename _RandomAccessIterator, typename _Diff, typename _Comp>
inline void max_heap_adjust(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Diff __index, _Comp comp) {
_Diff siz = __last - __first;
_Diff tar = LEFT_SON(__index);
while (tar < siz) {
_RandomAccessIterator child = __first + tar;
if (tar < siz - 1) {
if (comp(*child, *(child + 1))) {
++tar;
++child;
}
}
if (comp(*(__first + __index), *child)) std::iter_swap(__first + __index, child);
else break;
__index = tar;
tar = LEFT_SON(__index);
}
}
template <typename _RandomAccessIterator, typename _Comp>
inline void pop_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
--__last;
std::iter_swap(__first, __last);
max_heap_adjust(__first, __last, 0, comp);
}
template <typename _RandomAccessIterator, typename _Comp>
inline void push_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
_Diff pos = (__last - __first) - 1;
while (pos && comp(*(__first + PARENT(pos)), *(__first + pos))) {
std::iter_swap(__first + pos, __first + PARENT(pos));
pos = PARENT(pos);
}
}
template <typename _RandomAccessIterator, typename _Comp>
inline void make_max_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp comp) {
typedef typename std::iterator_traits< _RandomAccessIterator>::difference_type _Diff;
_Diff siz = __last - __first;
_Diff parent = PARENT(siz);
while (true) {
max_heap_adjust(__first, __last, parent, comp);
if (!parent) return;
--parent;
}
}
#undef LEFT_SON
#undef RIGHT_SON
#undef PARENT
std::vector<unsigned> lq, gq;
std::less<unsigned> comp;
int main() {
int n;
unsigned x;
scanf("%d%u", &n, &x);
lq.reserve(n / 2 + 1);
gq.reserve(n / 2 + 1);
lq.push_back(x);
printf("%u\n", x);
for (int i = 2; i <= n; i++) {
scanf("%u", &x);
if (x > lq[0]) {
gq.push_back(x);
push_min_heap(gq.begin(), gq.end(), comp);
}
else {
lq.push_back(x);
push_max_heap(lq.begin(), lq.end(), comp);
}
while (abs((int)lq.size() - (int)gq.size()) > 1) {
if (lq.size() > gq.size()) {
gq.push_back(lq[0]);
pop_max_heap(lq.begin(), lq.end(), comp);
lq.pop_back();
}
else {
lq.push_back(gq[0]);
pop_min_heap(gq.begin(), gq.end(), comp);
gq.pop_back();
}
}
if (i & 1) printf("%u\n", lq.size() > gq.size() ? lq[0] : gq[0]);
}
}
```
by Ruiqun2009 @ 2023-01-06 10:52:26
《手写堆》你怕不是哪个地方贺的源码
by Sprague_Garundy @ 2023-01-06 10:58:34
@[Sprague_Garundy](/user/764746) 是我自己写的。你自己看 `bits/stl_heap.h` 会发现完全不一样。
by Ruiqun2009 @ 2023-01-06 11:03:55
@[Sprague_Garundy](/user/764746) 这是大佬，重工业选手，人就习惯这么写QwQ
by C_liar @ 2023-01-06 11:04:45
我是那\*，`push` 的时候没有 `push_heap`
此贴结
by Ruiqun2009 @ 2023-01-06 11:30:25