leafy tree

cmwqf · 2018-12-14 22:52:34 · 题解

看起来整个题解区都没有一个leafy tree的题解，那我就来贡献一个吧

调了一个晚上的心血啊

#include<cstdio>
#include<iostream>
#define ls tree[node].l
#define rs tree[node].r
#define merge(a,b) new_Node(tree[b].value,tree[a].size+tree[b].size,a,b)
using namespace std;
const int maxN=3e5 + 100,ratio=4;
struct leafy
{
    int value,size;
    int l,r;
}tree[maxN*2+1];
int cnt,root;
int read()
{
    int num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
    return num*f;
}
int new_Node(int value,int size,int l,int r)//创建新节点 
{
    int node=++cnt;
    tree[node]=(leafy){value,size,l,r};
    return node;
}
void update(int node)
{
    if(!tree[node].l) {tree[node].size=1; return;}
    tree[node].size=tree[ls].size+tree[rs].size; tree[node].value=tree[rs].value;
}
void rotate(int node)//旋转 
{
    if(tree[ls].size>tree[rs].size*ratio) rs=merge(tree[ls].r,rs),ls=tree[ls].l;
    if(tree[rs].size>tree[ls].size*ratio) ls=merge(ls,tree[rs].l),rs=tree[rs].r;
}
int rank(int node,int x)//查x的排名 
{
    if(tree[node].size==1) return 1;
    if(x>tree[ls].value) return tree[ls].size+rank(rs,x);
    else return rank(ls,x); 
}
int find(int node,int x)//查排名为x的数 
{
    if(tree[node].size==1) return tree[node].value;
    if(x>tree[ls].size) return find(rs,x-tree[ls].size);
    else return find(ls,x);
}
void insert(int node,int x)//插入x 
{
    if(tree[node].size==1) ls=new_Node(min(tree[node].value,x),1,0,0),rs=new_Node(max(tree[node].value,x),1,0,0);
    else insert(x>tree[ls].value?rs:ls,x);
    update(node); rotate(node);
}
void del(int node,int x)//删除x 
{
    int now,other;
    if(x>tree[ls].value) now=rs,other=ls;
    else now=ls,other=rs;
    if(tree[now].size==1)
        if(x==tree[now].value)
        {
            tree[node].l=tree[other].l;
            tree[node].r=tree[other].r;
            tree[node].value=tree[other].value;
        }else return;
    else del(now,x);
    update(node); rotate(node);  
}
int main()
{
    int n=read();
    root=new_Node(1e8,1,0,0);
    while(n--)
    {
        int op,x;
        op=read();x=read();
        switch(op)
        {
            case 1:insert(root,x);break;
            case 2:del(root,x);break;
            case 3:printf("%d\n",rank(root,x));break;
            case 4:printf("%d\n",find(root,x));break;
            case 5:printf("%d\n",find(root,rank(root,x)-1));break;
            case 6:printf("%d\n",find(root,rank(root,x+1)));break;
        }
    }
    return 0;
}