# 洛谷P1168 中位数(Treap解法)

但是，本着杀鸡用牛刀的原则（抄板子），这个题还可以用名次树来完成，N次插入，大约N/2次查询名次，仍然是 O ( N l o g N ) O(NlogN) 的级别，在1e5的情况下可行！

insert(a,root)是插入数a
erase(a,root)删除数a，有多个只删除一个
rank(a,root)返回a的名次
find(a,root)返回名次a的数

#include "cstdlib"
#include "iostream"
#include "cstdio"
#include "cstring"
#include queue//队列
#define update( cur ) if(cur- left- size)cur- size = cur - left-size + cur - right - size , cur - value = cur - right - value
#define new_Node( s , v , a , b ) (  ( * st [ cnt++ ] = Node ( s , v , a , b) ) )
#define merge( a , b ) new_Node( a - size + b - size , b - value , a , b )
#define ratio 4

int n, cnt, s, a;

{
register int x = 0, v = 1, ch = getchar();
while (!isdigit(ch))
{
if (ch == '-') v = -1;
ch = getchar();
}
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x * v;
}

class Node
{
public:
int size, value;
Node* left, * right;
Node(int s, int v, Node* a, Node* b) : size(s), value(v), left(a), right(b) {}
Node() {}
};
Node* root, * st[300010], t[300010], * null, * father;

inline void maintain(register Node* cur)
{
if (cur-left-size  cur-right-size* ratio) cur-right = merge(cur-left-right, cur-right), st[--cnt] = cur-left, cur-left = cur-left-left;
if (cur-right-size  cur-left-size* ratio) cur-left = merge(cur-left, cur-right-left), st[--cnt] = cur-right, cur-right = cur-right-right;
}
int find(int x, Node* cur)
{
if (cur-size == 1) return cur-value;
return x  cur-left-size ? find(x - cur-left-size, cur-right) : find(x, cur-left);
}

int rank(int x, Node* cur)
{
if (cur-size == 1) return 1;
return x  cur-left-value ? rank(x, cur-right) + cur-left-size : rank(x, cur-left);
}

void insert(int x, Node* cur)
{
if (cur-size == 1) cur-left = new_Node(1, std::min(cur-value, x), null, null), cur-right = new_Node(1, std::max(cur-value, x), null, null);
else insert(x, x  cur-left-value ? cur-right : cur-left);
update(cur);
maintain(cur);
}

void erase(int x, Node* cur)
{
if (cur-size == 1) *father = cur == father-left ? *father-right : *father-left;
else father = cur, erase(x, x  cur-left-value ? cur-right : cur-left);
update(cur);
}

//main之前都是板子内容

int main()
{
for (register int i = 0; i  300010; i++) st[i] = t[i];
null = new Node(0, 0, 0, 0);
root = new Node(1, 2147483647, null, null);
for(int i=0;in;i++)
{
insert(s, root);
if(i%2==0)printf("%d\n", find(i/2+1, root));
}
return 0;
}