描述
小Ho：小Hi，我发现我们以前讲过的两个数据结构特别相似。
小Hi：你说的是哪两个啊？
小Ho：就是二叉排序树和堆啊，你看这两种数据结构都是构造了一个二叉树，一个节点有一个父亲和两个儿子。 如果用1..n的数组来存储的话，对于二叉树上的一个编号为k的节点，其父亲节点刚好是k/2。并且它的两个儿子节点分别为k2和k2+1，计算起来非常方便呢。
小Hi：没错，但是小Hi你知道有一种办法可以把堆和二叉搜索树合并起来，成为一个新的数据结构么？
小Ho：这我倒没想过。不过二叉搜索树满足左子树<根节点<右子树，而堆是满足根节点小于等于(或大于等于)左右儿子。这两种性质是冲突的啊？
小Hi：恩，你说的没错，这两种性质的确是冲突的。
小Ho：那你说的合并是怎么做到的？
小Hi：当然有办法了，其实它是这样的....
输入
第1行：1个正整数n，表示操作数量，10≤n≤100,000
第2..n+1行：每行1个字母c和1个整数k：
若c为'I'，表示插入一个数字k到树中，-1,000,000,000≤k≤1,000,000,000
若c为'Q'，表示询问树中不超过k的最大数字
输出
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
样例输入
5
I 3
I 2
Q 3
I 5
Q 4
样例输出
3
3
题解
官方讲解treap还是不错的
传送门
#include <queue>
#include <cstdio>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1000000000
#define PI acos(-1)
#define bug puts("here")
#define REP(i,x,n) for(int i=x;i<=n;i++)
#define DEP(i,n,x) for(int i=n;i>=x;i--)
#define mem(a,x) memset(a,x,sizeof(a))
typedef unsigned long long ull;
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(int a){
if(a<0) putchar('-'),a=-a;
if(a>=10) Out(a/10);
putchar(a%10+'0');
}
const int N=100000+5;
int size,root;
struct data{int l,r,v,rnd;}tr[N];
void rturn(int &k){
int t=tr[k].l;
tr[k].l=tr[t].r;
tr[t].r=k;k=t;
}
void lturn(int &k){
int t=tr[k].r;
tr[k].r=tr[t].l;
tr[t].l=k;k=t;
}
void insert(int &k,int x){
if(k==0){
size++;k=size;
tr[k].v=x;tr[k].rnd=rand();
return;
}
if(tr[k].v==x) return;
else if(x<tr[k].v){
insert(tr[k].l,x);
if(tr[tr[k].l].rnd<tr[k].rnd) rturn(k);
}else{
insert(tr[k].r,x);
if(tr[tr[k].r].rnd<tr[k].rnd) lturn(k);
}
}
int t1;
void dfs1(int k,int x){
if(!k) return;
if(x>=tr[k].v){
t1=tr[k].v;
dfs1(tr[k].r,x);
}
else dfs1(tr[k].l,x);
}
int main(){
root=size=0;
int n=read();char op;
for(int i=1;i<=n;i++){
cin>>op;
int x=read();
if(op=='I') insert(root,x);
else{
dfs1(root,x);
Out(t1);puts("");
}
}
return 0;
}