treap_a.cpp

一些重要的数据结构

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
const	int  maxn = 201000;
const	int  modium  = 99997;
struct	node{
		int lc,rc,ky,rp;
}		tree[maxn];
int		root,top;
void	rc_rolate(int &r){
		int t = tree[r].lc;
		tree[r].lc = tree[t].rc;
		tree[t].rc = r;
		r = t;
}
void	lc_rolate(int &r){
		int t = tree[r].rc;
		tree[r].rc = tree[t].lc;
		tree[t].lc = r;
		r = t;
}
void	ins(int &r,int d){
		if (r==0){
			r = ++top;
			tree[r].lc = 0;
			tree[r].rc = 0;
			tree[r].ky = d;
			tree[r].rp = rand() % modium;
			return;
		}
		if (d<tree[r].ky){
			ins(tree[r].lc,d);
			if (tree[tree[r].lc].rp<tree[r].rp) rc_rolate(r);
		} else {
			ins(tree[r].rc,d);
			if (tree[tree[r].rc].rp<tree[r].rp) lc_rolate(r);
		}
}
void	del(int &r,int d){
		if (d<tree[r].ky){ del(tree[r].lc,d); return; }
		if (d>tree[r].ky){ del(tree[r].rc,d); return; }  
		if (tree[r].lc!=0 || tree[r].rc!=0){
			if (tree[tree[r].lc].rp<tree[tree[r].rc].rp){
				rc_rolate(r);
				del(tree[r].rc,d);
				return;
			} else {
				lc_rolate(r);
				del(tree[r].lc,d);
				return;
			}
		}
		r = 0;
}
void	newtree(){
		root = 0;
		top  = 0;
		tree[0].rp = modium;
}