题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=3282
Running Median
Description
For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
Input
The first line of input contains a single integer $P, (1 \leq P \leq 1000)$, which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer $M, (1 \leq M \leq 9999)$, giving the total number of signed integers to be processed.
The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space.
The last line in the dataset may contain less than 10 values.
Output
For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.
SampleInput
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
SampleOutput
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
动态的求中位数，套个平衡树即可。。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using std::cin;
using std::cout;
using std::endl;
using std::find;
using std::sort;
using std::set;
using std::map;
using std::pair;
using std::vector;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define iter(c) decltype((c).begin())
#define cls(arr,val) memset(arr,val,sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define fork(i, k, n) for (int i = (int)k; i <= (int)n; i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
const int Max_N = ;
typedef unsigned long long ull;
struct Node {
int v, s;
Node *ch[];
inline void setc(int _v, int _s, Node *p) {
v = _v, s = _s;
ch[] = ch[] = p;
}
inline void push_up() {
s = ch[]->s + ch[]->s + ;
}
};
struct SBT {
Node stack[Max_N];
Node *root, *null, *tail;
inline void init() {
tail = &stack[];
null = tail++;
null->setc(, , NULL);
root = null;
}
inline Node *newNode(int v) {
Node *p = tail++;
p->setc(v, , null);
return p;
}
inline void rotate(Node *&x, bool d) {
Node *k = x->ch[!d]; x->ch[!d] = k->ch[d]; k->ch[d] = x;
k->s = x->s;
x->push_up();
x = k;
}
inline void Maintain(Node *&x, bool d) {
if (!x->ch[d]->s) return;
if (x->ch[d]->ch[d]->s > x->ch[!d]->s) rotate(x, !d);
else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) rotate(x->ch[d], d), rotate(x, !d);
else return;
Maintain(x, ), Maintain(x, );
}
inline void insert(Node *&x, int v) {
if (!x->s) { x = newNode(v); return; }
bool d = v > x->v; x->s++;
insert(x->ch[d], v);
x->push_up();
Maintain(x, d);
}
inline int kth(int k) {
int t;
Node *x = root;
for (; x->s;) {
t = x->ch[]->s;
if (k == t + ) break;
else if (k <= t) x = x->ch[];
else k -= t + , x = x->ch[];
}
return x->v;
}
inline void go() {
vector<int> res;
int v, q, n, k = ;
scanf("%d %d", &q, &n);
printf("%d %d\n", q, (n + ) >> );
fork(i, , n) {
scanf("%d", &v);
insert(root, v);
if (i & ) res.push_back(kth((root->s >> ) + ));
}
n = sz(res);
rep(i, n) {
if ((i + ) % ) {
if (i == n - ) printf("%d\n", res[i]);
else printf("%d ", res[i]);
}
else printf("%d\n", res[i]);
}
}
}sbt;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int t;
scanf("%d", &t);
while (t--){
sbt.init();
sbt.go();
}
return ;
}