#1325 : 平衡树·Treap
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho：小Hi，我发现我们以前讲过的两个数据结构特别相似。
小Hi：你说的是哪两个啊？
小Ho：就是二叉排序树和堆啊，你看这两种数据结构都是构造了一个二叉树，一个节点有一个父亲和两个儿子。 如果用1..n的数组来存储的话，对于二叉树上的一个编号为k的节点，其父亲节点刚好是k/2。并且它的两个儿子节点分别为k*2和k*2+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<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-14 const int N=2e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7; const ll INF=1e18+10; struct is { int l,r,v,si,rnd,w;//v 权值 rnd 堆的优先级 w为v的个数 } tree[N]; int n,sz,root,ans; void update(int pos) { tree[pos].si=tree[tree[pos].l].si+tree[tree[pos].r].si+tree[pos].w; } void lturn(int &pos) { int t=tree[pos].r; tree[pos].r=tree[t].l; tree[t].l=pos; tree[t].si=tree[pos].si; update(pos); pos=t; } void rturn(int &pos) { int t=tree[pos].l; tree[pos].l=tree[t].r; tree[t].r=pos; tree[t].si=tree[pos].si; update(pos); pos=t; } void pushin(int &k,int x) { if(k==0) { sz++; k=sz; tree[k].w=tree[k].si=1; tree[k].rnd=rand(); tree[k].v=x; return; } tree[k].si++; if(tree[k].v==x)tree[k].w++; else if(tree[k].v>x) { pushin(tree[k].l,x); if(tree[tree[k].l].rnd>tree[k].rnd) rturn(k); } else { pushin(tree[k].r,x); if(tree[tree[k].r].rnd>tree[k].rnd) lturn(k); } } void query(int pos,int x) { if(pos==0)return; if(tree[pos].v<=x) { ans=pos; query(tree[pos].r,x); } else query(tree[pos].l,x); } char ch[N]; int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { int x; scanf("%s%d",ch,&x); if(ch[0]=='I') pushin(root,x); else ans=0,query(root,x),printf("%d ",tree[ans].v); } return 0; }