Treap(Tree+Heap)---是一种通过 rand() 来随机生成数字作为修正值来调整的平衡树。
基本操作：
1.旋转。
2.插入（合并重复的），删除（懒惰删除）。
3.查最值，求第k小，求排名。
4.中序遍历就是从小到大的。
5.维护附加关键字.
1.求第k小:
POJ1442
//12321199 1442 Accepted 976K 204MS C++ 2080B 2013-11-22 20:33:35静态
//12321216 1442 Accepted 1804K 329MS C++ 2125B 2013-11-22 20:39:40动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 30005
int a[MAX];
int u[MAX];
int tot;
class Node
{
public:
int vol,fix;
int size;
Node *left;
Node *right;
int lsize(){return left?left->size:0;}
int rsize(){return right?right->size:0;}
}*root;//space[MAX]
void left_rotate(Node *&a)
{
Node *b=a->right;
a->right=b->left;
b->left=a;
a=b;
b=a->left;
b->size=b->lsize()+b->rsize()+1;
a->size=a->lsize()+a->rsize()+1;
}
void right_rotate(Node *&a)
{
Node *b=a->left;
a->left=b->right;
b->right=a;
a=b;
b=a->right;
b->size=b->lsize()+b->rsize()+1;
a->size=a->lsize()+a->rsize()+1;
}
void insert(Node*&p,int vol)
{
if(!p)
{
p=new Node();
//p=&space[tot++]; //静态
p->fix=rand();
p->vol=vol;
p->size=1;
}
else if(vol<=p->vol)
{
insert(p->left,vol);
p->size++;
if(p->left->fix < p->fix)
right_rotate(p);
}
else
{
insert(p->right,vol);
p->size++;
if(p->right->fix < p->fix)
left_rotate(p);
}
}
int get_kth(Node *&p,int k)
{
int key=p->lsize()+1;
if(k < key)
return get_kth(p->left,k);
else if(k > key)
return get_kth(p->right,k-key);
else
return p->vol;
}
void init()
{
root=NULL;
//memset(space,0,sizeof(space));静态
//tot=1;
}
int main()
{
srand(time(0));
int n,m;
while(~scanf("%d%d",&m,&n))
{
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&u[i]);
int j=1;
init();
for(int i=1;i<=m;i++)
{
insert(root,a[i]);
while(j<=n&&i==u[j])
{
printf("%d\n",get_kth(root,j));
j++;
}
if(j>n) break;
}
}
return 0;
}
2.动态求最值
//12321728 3481 Accepted 212K 282MS C++ 1857B 2013-11-22 22:26:19动态
#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
//#define MAX 10000005
class Node
{
public:
int vol,fix,cus;
Node* left;
Node* right;
}*root;//,space[MAX]
int tot=1;
void r_rotate(Node*&a)
{
Node*b=a->left;
a->left=b->right;
b->right=a;
a=b;
b=a->right;
}
void l_rotate(Node*&a)
{
Node*b=a->right;
a->right=b->left;
b->left=a;
a=b;
b=a->left;
}
void insert(Node*&p,int cus,int vol)
{
if(!p)
{
p=new Node();
//p=&space[tot++];
p->fix=rand();
p->vol=vol;
p->cus=cus;
}
else if(p->vol >= vol)
{
insert(p->left,cus,vol);
if(p->left->fix < p->fix)
r_rotate(p);
}
else
{
insert(p->right,cus,vol);
if(p->right->fix < p->fix)
l_rotate(p);
}
}
int Min(Node*&p)
{
if(!p)return 0;
if(!p->left)
{
Node*t=p;
int ans=p->cus;
p=p->right;
delete t;
return ans;
}
else return Min(p->left);
}
int Max(Node*&p)
{
if(!p)return 0;
if(!p->right)
{
Node*t=p;
int ans=p->cus;
p=p->left;
delete t;
return ans;
}
else return Max(p->right);
}
int main()
{
srand(time(0));
int a;
while(~scanf("%d",&a)&&a)
{
if(a==1)
{
int b,c;
scanf("%d%d",&b,&c);
insert(root,b,c);
}
else if(a==3)
{
printf("%d\n",Min(root));
}
else
{
printf("%d\n",Max(root));
}
}
return 0;
}
3.区间第k小:
//12329808 2761 Accepted 3500K 1844MS C++ 3889B 2013-11-25 21:28:45静态
//12329836 2761 Accepted 3900K 3922MS C++ 3962B 2013-11-25 21:34:10动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000005
int dog[MAX];
int ans[MAX];
class Interval
{
public:
int s,e,k;
int id;
bool operator<(const Interval a) const
{
return s<a.s;
}
}qu[MAX];
class Node
{
public:
int vol,fix,size;
Node*left;
Node*right;
int lsize(){return left?left->size:0;}
int rsize(){return right?right->size:0;}
}*root,space[MAX];
int tot;
void r_rotate(Node*&a)
{
Node*b=a->left;
a->left=b->right;
b->right=a;
a=b;
b=a->right;
b->size=b->lsize()+b->rsize()+1;/**RE在这里，不要把求size顺序搞反了*/
a->size=a->lsize()+a->rsize()+1;
}
void l_rotate(Node*&a)
{
Node*b=a->right;
a->right=b->left;
b->left=a;
a=b;
b=a->left;
b->size=b->lsize()+b->rsize()+1;
a->size=a->lsize()+a->rsize()+1;
}
void insert(Node*&p,int vol)
{
if(!p)
{
p=&space[tot++];
//p=new Node();
p->left=NULL;
p->right=NULL;
p->fix=rand();
p->vol=vol;
p->size=1;
}
else if(p->vol > vol)
{
p->size++;
insert(p->left,vol);
if(p->left->fix < p->fix)
r_rotate(p);
}
else
{
p->size++;
insert(p->right,vol);
if(p->right->fix < p->fix)
l_rotate(p);
}
}
void del(Node*&p,int key)
{
if(!p) return ;
p->size--; /**注意size的减减**/
if(key==p->vol)
{
if(!p->left || !p->right)
{
//Node *t=p;
if(!p->left)
p=p->right;
else
p=p->left;
//delete t;
}
else
{
if(p->right->fix < p->left->fix)
{
l_rotate(p);
p->size--;/**注意size的减减**/
del(p->left,key);
}
else
{
r_rotate(p);
p->size--;/**注意size的减减**/
del(p->right,key);
}
}
}
else if(key < p->vol)
del(p->left,key);
else
del(p->right,key);
}
int find_kth(Node*&p,int k)
{
int sum=p->lsize()+1;
if(k < sum)
{
return find_kth(p->left,k);
}
else if(k>sum)
{
return find_kth(p->right,k-sum);
}
else
{
return p->vol;
}
}
int solve(Interval t1,Interval t2)
{
for(int i=t1.s;i<=min(t2.s-1,t1.e);i++)
del(root,dog[i]);
if(t1.e > t2.e)
{
for(int i=t2.e+1;i<=t1.e;i++)
del(root,dog[i]);
}
for(int i=max(t1.e+1,t2.s);i<=t2.e;i++)
insert(root,dog[i]);
return find_kth(root,t2.k);
}
int main()
{
srand(time(0));
//int T;
//scanf("%d",&T);
int n,m;
while(~scanf("%d%d",&n,&m))
{
root=NULL;
tot=1;
memset(space,NULL,sizeof(space));
for(int i=1;i<=n;i++)
scanf("%d",&dog[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&qu[i].s,&qu[i].e,&qu[i].k);
if(qu[i].s > qu[i].e) swap(qu[i].s,qu[i].e);
qu[i].id=i;
}
sort(qu+1,qu+1+m);
for(int i=qu[1].s;i<=qu[1].e;i++)
insert(root,dog[i]);
ans[qu[1].id]=find_kth(root,qu[1].k);
for(int i=2;i<=m;i++)
{
ans[qu[i].id]=solve(qu[i-1],qu[i]);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}