BruceJay's Blog

BZOJ3224 普通平衡树

| Comments

To start with

Bruce最近在学平衡树。

智商限制,Bruce看了很久才看懂《伸展树的基本操作与应用》,但还是不会打模板,于是实力copy别人的模板,这题算是一道不错的模板题了。

Problem

Solution

Splay的模板题,Bruce打(chao)了很久,终于A了。
包含6种操作:
插入:不多说,注意更新子树的size。
删除:将被删除节点x转到根部,若为只有一个儿子,好办;如果有两个儿子,就需要找前驱l和后继r了,将l转到根,r转到l的右儿子,那么r的左子树只有一个节点x(好神奇),直接删了。
查询排名:转到根便是。
查询排名为x的数:后面的好几道题都要用这个,用子树size比就是了。
查询前驱:不多说,看代码。
查询后继:不多说,看代码。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
int a[N]; int tr[N][2];
int size[N]; int fa[N];
int n,root=0,sz=0;
const int INF = 0x3f3f3f3f;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Update(int &k)
{
    size[k]=size[tr[k][0]]+size[tr[k][1]]+1;
}

void Rotate(int x,int& k)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(y==k) k=x;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Update(y); Update(x);
}

void Splay(int x,int& k)
{
    while(x!=k){
        int y=fa[x];
        if(y!=k){
            int z=fa[y];
            if(tr[z][0]==y^tr[y][0]==x) Rotate(x,k);
            else Rotate(y,k);
        }
        Rotate(x,k);
    }
}

int Find(int x,int &k)
{
    if(!k) return 0;
    if(a[k]>=x){
        int t=Find(x,tr[k][0]);
        if(t) return t;
        else return k;
    }
    else return Find(x,tr[k][1]);
}

void Ins(int x,int& k,int pre)
{
    if(!k){
        k=++sz; a[k]=x; fa[k]=pre;
        size[k]=1; return;
    }
    if(a[k]>x) Ins(x,tr[k][0],k);
    else Ins(x,tr[k][1],k);
    Update(k);
}

void Insert(int x)
{
    Ins(x,root,0);
    Splay(sz,root);
}

void Del(int x)
{
    x=Find(x,root);
    Splay(x,root);
    int l=tr[x][0],r=tr[x][1];
    if(!(l*r)){
        root=l^r;
        return;
    }
    while(tr[l][1]) l=tr[l][1];
    while(tr[r][0]) r=tr[r][0];
    Splay(l,root); Splay(r,tr[l][1]);
    fa[r]=l; tr[r][0]=0;
    fa[x]=0; a[x]=0;
    Update(r); Update(l);
}

int Rank(int x)
{
    x=Find(x,root);
    Splay(x,root);
    return size[tr[root][0]]+1;
}

int FindRank(int x,int &k)
{
    int t=size[tr[k][0]]+1;
    if(t==x) return a[k];
    else if(t>x) return FindRank(x,tr[k][0]); 
    else return FindRank(x-t,tr[k][1]);
}

int Prefix(int x,int &k)
{
    if(!k) return -INF;
    if(a[k]<x) return max(a[k],Prefix(x,tr[k][1])); 
    else return Prefix(x,tr[k][0]);
}

int Suffix(int x,int &k)
{
    if(!k) return INF;
    if(a[k]>x) return min(a[k],Suffix(x,tr[k][0]));
    else return Suffix(x,tr[k][1]);
}

int main()
{
    int opt,x;
    freopen("3224.in","r",stdin);
    freopen("3224.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        opt=read(); x=read();
        if(opt==1) Insert(x);
        else if(opt==2) Del(x);
        else if(opt==3) printf("%d\n",Rank(x));
        else if(opt==4) printf("%d\n",FindRank(x,root));
        else if(opt==5) printf("%d\n",Prefix(x,root));
        else printf("%d\n",Suffix(x,root));
    }
    return 0;
}

Last but not least

感觉这一题很绕啊,一会儿排名,一会儿数,很不爽啊。
模板实力抄了hzwer,大家莫嘲讽。

Comments

comments powered by Disqus