原理可以看hihocoder上面的讲解,很清楚，不多说了。
模板抄lrj训练指南上面的。
/**
Treap 实现 名次树
功能： 1.找到排名为k的元素
2.值为x的元素的名次 初始化：Node* root = NULL;
*/
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; struct Node {
Node * ch[]; // 0左子树 1右子树
int r; // 随机优先级
int v; // 值
int s; // 以s为根的子树的大小
Node(int v):v(v)
{
ch[] = ch[] = NULL;
r = rand();
s = ;
}
bool operator<(const Node& rhs) const { // 按随机优先级排序
return r < rhs.r;
}
int cmp(int x) const
{
if (x == v) return -;
return x < v ? : ;
}
void maintain() // 更新
{
s = ;
if (ch[] != NULL) s += ch[]->s;
if (ch[] != NULL) s += ch[]->s;
}
} ; void rotate(Node* &o, int d) // d=0 代表左转, d=1代表右转
{
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
} void insert(Node* &o, int x) // o是根 x是插入的值
{
if (o == NULL) {
o = new Node(x);
} else {
int d = (x < o->v ? : ); // 不用cmp函数因为可能有重复的值
insert(o->ch[d], x);
if ((o->ch[d]->r) > (o->r)) rotate(o, d^);
}
o->maintain();
} void remove(Node* &o, int x)
{
int d = o->cmp(x);
if (d == -) {
Node* u = o;
if (o->ch[] != NULL && o->ch[] != NULL) {
int d2 = ((o->ch[]->r) > (o->ch[]->r) ? : );
rotate(o, d2);
remove(o->ch[d2], x);
} else {
if (o->ch[] == NULL) o = o->ch[];
else o = o->ch[];
delete u;
}
} else {
remove(o->ch[d], x);
}
if (o != NULL) o->maintain();
} int find(Node* o, int x) // 因为remove和insert都没有查值存不存在 记得操作之前调用find
{
while (o != NULL) {
int d = o->cmp(x);
if (d == -) return ;
else o = o->ch[d];
}
return ;
} int kth(Node* &o, int k, int fg) // fg=1第k大的值 fg=0第k小的值 返回0表示没找到
{
if (o == NULL || k <= || k > o->s) return ;
int s = (o->ch[fg] == NULL ? : o->ch[fg]->s);
if (k == s+) return o->v;
else if (k <= s) return kth(o->ch[fg], k, fg);
else return kth(o->ch[fg^], k-s-, fg);
} int prv(Node* &o, int x) // 查找x前面的元素 （<x的最大值
{
if (o == NULL) return -;
if (x <= o->v) return prv(o->ch[], x);
int ans = prv(o->ch[], x); return ans == - ? o->v : ans;
} int nxt(Node* &o, int x) // 查找x后面的元素 （>x的最大值
{
if (o == NULL) return -;
if (x >= o->v) return nxt(o->ch[], x);
int ans = nxt(o->ch[], x);
return ans == - ? o->v : ans;
} void mergeto(Node* &src, Node* &dest) // 合并两棵树 把src加到dest上 src和dest都是树的根
{
if (src->ch[] != NULL) mergeto(src->ch[], dest);
if (src->ch[] != NULL) mergeto(src->ch[], dest);
insert(dest, src->v);
delete src;
src = NULL;
} void print(Node* &o)
{
if (o == NULL) return ;
print(o->ch[]);
printf("%d ", o->v);
print(o->ch[]);
} int main()
{
Node* root = NULL;
insert(root, );
insert(root, );
insert(root, );
insert(root, );
remove(root, );
print(root);
return ;
}
例题：
上面hihocoder的例题，这个代码是照着讲解自己写的
//Treap.cpp #include <stdio.h>
#include <string.h>
#include <stdlib.h> const int N = ; struct Treap {
int father, left, right;
int key, weight;
void init(int k, int w, int fa) {
left = right = -;
father = fa, key = k, weight = w;
}
} tp[N];
int root;
int treap_cnt; int new_treap(int k, int w, int fa = -)
{
tp[treap_cnt].init(k, w, fa);
return treap_cnt++;
} void left_rotate(int a) // 左旋 把节点A的右儿子节点B转到A的父亲节点
{
int b = tp[a].right;
tp[b].father = tp[a].father;
if (tp[tp[a].father].left == a) { // 判断a是父节点的左儿子还是右儿子 并用b替换
tp[tp[a].father].left = b;
} else {
tp[tp[a].father].right = b;
}
tp[a].right = tp[b].left;
if (tp[b].left != -) tp[tp[b].left].father = a;
tp[b].left = a;
tp[a].father = b;
} void right_rotate(int a) // 右旋 把节点A的左儿子节点B转到A的父亲节点
{
int b = tp[a].left;
tp[b].father = tp[a].father;
if (tp[tp[a].father].left == a) tp[tp[a].father].left = b;
else tp[tp[a].father].right = b;
tp[a].left = tp[b].right;
if (tp[b].right != -) tp[tp[b].right].father = a;
tp[b].right = a;
tp[a].father = b;
} int insert(int a, int key)
{
if (key < tp[a].key) {
if (tp[a].left == -) {
tp[a].left = new_treap(key, rand(), a);
return tp[a].left;
} else {
return insert(tp[a].left, key);
}
} else {
if (tp[a].right == -) {
tp[a].right = new_treap(key, rand(), a);
return tp[a].right;
} else {
return insert(tp[a].right, key);
}
}
} void rotate(int a) // 维持小顶堆
{
int fa = tp[a].father;
while (fa != -) {
if (tp[a].weight < tp[fa].weight) {
if (a == tp[fa].left) right_rotate(fa);
else left_rotate(fa);
fa = tp[a].father;
} else {
break;
}
}
if (fa == -) root = a;
} int find(int a, int key)
{
int cur = a, pre = -;
while (cur != -) {
if (tp[cur].key > key) {
pre = cur;
cur = tp[cur].left;
} else if (tp[cur].key < key) {
pre = cur;
cur = tp[cur].right;
} else {
return key;
}
}
while (pre != -) {
if (tp[pre].key < key) return tp[pre].key;
pre = tp[pre].father;
}
return -;
} void print(int a)
{
if (a == -) return;
print(tp[a].left);
printf("%d(%d) ", a, tp[a].key);
print(tp[a].right);
} int main(int argc, char const *argv[])
{
//freopen("in", "r", stdin);
root = -;
treap_cnt = ;
int n;
char op[];
int k;
scanf("%d", &n);
while (n--) {
scanf("%s%d", op, &k);
if (*op == 'I') {
if (root == -) root = new_treap(k, rand());
else rotate(insert(root, k));
} else {
printf("%d\n", find(root, k));
}
}
return ;
}
poj1442，直接套模板，比较简单
/**
Treap 实现 名次树
功能： 1.找到排名为k的元素
2.值为x的元素的名次
*/
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; struct Node {
Node * ch[]; // 0左子树 1右子树
int r; // 随机优先级
int v; // 值
int s; // 以s为根的子树的大小
Node(int v):v(v)
{
ch[] = ch[] = NULL;
r = rand();
s = ;
}
bool operator<(const Node& rhs) const { // 按随机优先级排序
return r < rhs.r;
}
int cmp(int x) const
{
if (x == v) return -;
return x < v ? : ;
}
void maintain() // 更新
{
s = ;
if (ch[] != NULL) s += ch[]->s;
if (ch[] != NULL) s += ch[]->s;
}
} ; void rotate(Node* &o, int d) // d=0 代表左转, d=1代表右转
{
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
} void insert(Node* &o, int x) // o是根 x是插入的值
{
if (o == NULL) {
o = new Node(x);
} else {
int d = (x < o->v ? : ); // 不用cmp函数因为可能有重复的值
insert(o->ch[d], x);
if ((o->ch[d]->r) > (o->r)) rotate(o, d^);
}
o->maintain();
} void remove(Node* &o, int x)
{
int d = o->cmp(x);
if (d == -) {
Node* u = o;
if (o->ch[] != NULL && o->ch[] != NULL) {
int d2 = ((o->ch[]->r) > (o->ch[]->r) ? : );
rotate(o, d2);
remove(o->ch[d2], x);
} else {
if (o->ch[] == NULL) o = o->ch[];
else o = o->ch[];
delete u;
}
} else {
remove(o->ch[d], x);
}
if (o != NULL) o->maintain();
} int find(Node* &o, int x) // 因为remove和insert都没有查值存不存在 记得操作之前调用find
{
while (o != NULL) {
int d = o->cmp(x);
if (d == -) return ; // exist
else o = o->ch[d];
}
return ; // not exist
} int kth(Node* &o, int k, int fg) // fg=1第k大的值 fg=0第k小的值 返回0表示没找到
{
if (o == NULL || k <= || k > o->s) return ;
int s = (o->ch[fg] == NULL ? : o->ch[fg]->s);
if (k == s+) return o->v;
else if (k <= s) return kth(o->ch[fg], k, fg);
else return kth(o->ch[fg^], k-s-, fg);
} void mergeto(Node* &src, Node* &dest)
{
if (src->ch[] != NULL) mergeto(src->ch[], dest);
if (src->ch[] != NULL) mergeto(src->ch[], dest);
insert(dest, src->v);
delete src;
src = NULL;
} const int N = ;
int a[N];
int main()
{
//freopen("in", "r", stdin);
int m, n;
while (~scanf("%d%d", &m, &n)) {
Node* root = NULL;
for (int i = ; i <= m; ++i) {
scanf("%d", a+i);
}
int x = , u, cnt = ;
for (int i = ; i < n; ++i) {
scanf("%d", &u);
while (cnt < u) {
insert(root, a[++cnt]);
}
printf("%d\n", kth(root, ++x, ));
}
}
return ;
}
hdu4557
每个结点加了一个元素t，排序查找都要考虑t
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
using namespace std; struct Node {
Node * ch[]; // 0左子树 1右子树
int r; // 随机优先级
int v; // 值
int t;
int s; // 以s为根的子树的大小
Node(int v, int t):v(v), t(t)
{
ch[] = ch[] = NULL;
r = rand();
s = ;
}
bool operator<(const Node& rhs) const { // 按随机优先级排序
if (r == rhs.r) return t < rhs.t;
return r < rhs.r;
}
int cmp(int x, int y) const
{
if (x == v && y == t) return -;
if (x == v) return y < t ? : ;
return x < v ? : ;
}
void maintain() // 更新
{
s = ;
if (ch[] != NULL) s += ch[]->s;
if (ch[] != NULL) s += ch[]->s;
}
} ; void rotate(Node* &o, int d) // d=0 代表左转, d=1代表右转
{
Node* k = o->ch[d^];
o->ch[d^] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
} void insert(Node* &o, int x, int y) // o是根 x是插入的值
{
if (o == NULL) {
o = new Node(x, y);
} else {
int d = o->cmp(x, y);
insert(o->ch[d], x, y);
if ((o->ch[d]->r) > (o->r)) rotate(o, d^);
}
o->maintain();
} void remove(Node* &o, int x, int y)
{
int d = o->cmp(x, y);
if (d == -) {
Node* u = o;
if (o->ch[] != NULL && o->ch[] != NULL) {
int d2 = ((o->ch[]->r) > (o->ch[]->r) ? : );
rotate(o, d2);
remove(o->ch[d2], x, y);
} else {
if (o->ch[] == NULL) o = o->ch[];
else o = o->ch[];
delete u;
}
} else {
remove(o->ch[d], x, y);
}
if (o != NULL) o->maintain();
} int nxt(Node* &o, int x, int &res) // 查找x后面的元素 （>=x的最小值
{
if (o == NULL) return -;
if (o->v < x) return nxt(o->ch[], x, res);
res = o->v;
int ans = nxt(o->ch[], x, res);
return ans == - ? o->t : ans;
} void print(Node* &o)
{
if (o == NULL) return ;
print(o->ch[]);
printf("%d ", o->v);
print(o->ch[]);
} int main()
{
freopen("in", "r", stdin);
int T;
cin >> T;
int cas = ;
while (T--) {
printf("Case #%d:\n", ++cas);
int n;
cin >> n;
char op[];
string name;
int abi, res;
Node* root = NULL;
map<int, string> mp;
for (int i = ; i < n; ++i) {
scanf("%s", op);
if (*op == 'A') {
cin >> name;
scanf("%d", &abi);
mp[i] = name;
insert(root, abi, i);
printf("%d\n", root->s);
} else {
scanf("%d", &abi);
int ans = nxt(root, abi, res);
if (ans == -) printf("WAIT...\n");
else {
cout << mp[ans] << endl;
remove(root, res, ans);
}
}//printf("debug:"); print(root); printf("\n");
}
}
}