洛谷 P3369 【模板】普通平衡树（算法竞赛进阶指南，普通平衡树，模板 ）

算法竞赛进阶指南，238页，普通平衡树，模板

本题要点：
1、设计普通普通平衡树的，增加，删除，左旋，右旋，前驱，后继，按值查排名， 按排名查询值
等等操作。
2、代码抄书上的，作为模板参考。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 100010;
int tot, root, n, INF = 0x7fffffff;struct Treap
{
    int l, r;int val, dat;int cnt, size;	//副本数，子树的大小
}a[MaxN];int New(int val)
{
    a[++tot].val = val;a[tot].dat = rand();a[tot].cnt = a[tot].size = 1;return tot;
}void Update(int p)
{
    a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}void Build()
{
    New(-INF), New(INF);root = 1, a[1].r = 2;Update(root);
}int getRankByVal(int p, int val)	// 数值 --> 排名
{
    if(0 == p)	return 0;if(a[p].val == val)	return a[a[p].l].size + 1;else if(val < a[p].val)	return getRankByVal(a[p].l, val);else return a[a[p].l].size + getRankByVal(a[p].r, val) + a[p].cnt;
}int getValByRank(int p, int rank)	//排名 --> 数值
{
    if(0 == p)	return INF;if(a[a[p].l].size >= rank)	return getValByRank(a[p].l, rank);else if(a[a[p].l].size + a[p].cnt >= rank)	return a[p].val;else return getValByRank(a[p].r, rank - a[a[p].l].size - a[p].cnt);
}void zig(int &p)	//右旋转
{
    int q = a[p].l;a[p].l = a[q].r, a[q].r = p, p = q;Update(a[p].r), Update(p);
}void zag(int &p)	//左旋
{
    int q = a[p].r;a[p].r = a[q].l, a[q].l = p, p = q;Update(a[p].l), Update(p);
}void Insert(int &p, int val)
{
    if(0 == p){
    p = New(val);		return;}if(val == a[p].val){
    a[p].cnt++, Update(p);return;}if(val < a[p].val){
    Insert(a[p].l, val);if(a[p].dat < a[a[p].l].dat)	zig(p);	//不满足堆的条件，右旋}else{
    Insert(a[p].r, val);if(a[p].dat < a[a[p].r].dat)    zag(p);}Update(p);
}int GetPre(int val)
{
    int ans = 1;	//a[1].val = -INF;int p = root;while(p){
    if(val == a[p].val){
    if(a[p].l > 0){
    p = a[p].l;while(a[p].r > 0){
    p = a[p].r;		//左子树一直往右走}ans = p;}break;}if(a[p].val < val && a[p].val > a[ans].val)	ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}int GetNext(int val)
{
    int ans = 2;	//a[2].val = INFint p = root;while(p){
    if(val == a[p].val){
    if(a[p].r > 0){
    p = a[p].r;while(a[p].l > 0){
    p = a[p].l;	//右子树一直往左走}ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val){
    ans = p;}p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}void Remove(int &p, int val)
{
    if(0 == p)	return;if(val == a[p].val)	//检查到val{
    if(a[p].cnt > 1){
    a[p].cnt--;Update(p);return;}if(a[p].l || a[p].r){
    if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
    zig(p);Remove(a[p].r, val);}else{
    zag(p);Remove(a[p].l, val);}Update(p);}else{
    p = 0;	//叶子节点，直接删除}return;}val < a[p].val ? Remove(a[p].l, val) :  Remove(a[p].r, val);Update(p);
}int main()
{
    Build();int op, x;scanf("%d", &n);for(int i = 0; i < n; ++i){
    scanf("%d%d", &op, &x);switch(op){
    case 1:		//插入Insert(root, x);break;case 2:		//删除Remove(root, x);break;case 3:		//按值查询 排名printf("%d\n", getRankByVal(root, x) - 1);break;case 4:		//按排名查询值printf("%d\n", getValByRank(root, x + 1));break;case 5:		//前驱printf("%d\n", GetPre(x));break;case 6:		//后继printf("%d\n", GetNext(x));break;}}return 0;
}/* 8 1 10 1 20 1 30 3 20 4 2 2 10 5 25 6 -1 *//* 2 20 20 20 */