P3369 【模板】普通平衡树 题解（Splay/FHQ）

题目链接

P3369 【模板】普通平衡树

解题思路1：Splay

注意查询的时候大于小于等于号千万不要搞错了；注意适时伸展

AC代码1

#include<stdio.h>
#define root t[0].s[1]
struct Tree{
    int s[2];//son
    int sum;//总 数字 数 
    int cnt;//frequence
    int f;//father
    int data;
}t[200010];
int size,tot;//最大节点序号，总 数字 数 
void upd(int x){
    t[x].sum=t[t[x].s[0]].sum+t[t[x].s[1]].sum+t[x].cnt;//更新节点 
}
int id(int x){//查询该节点为左儿子还是右儿子 
    return x==t[t[x].f].s[0]?0:1;
}
void connect(int x,int fa,int son){//x->fa,fa.son->x 
    t[x].f=fa;
    t[fa].s[son]=x;
}
void rotate(int x){//x为中心的旋转 
    int y=t[x].f,idx=id(x),idy=id(y),B=t[x].s[idx^1],R=t[y].f;
    connect(B,y,idx);
    connect(y,x,idx^1);
    connect(x,R,idy);
    upd(y);upd(x);
}
void splay(int now,int to){//把now转为to的父亲的孩子节点（转到to的位置） 
    to=t[to].f;
    while(to!=t[now].f){
        int up=t[now].f;
        if(to==t[up].f)rotate(now);//只能翻上去一次 
        else if(id(now)==id(up)){
            rotate(up);
            rotate(now);
        }
        else{
            rotate(now);
            rotate(now);
        }
    }
}
int create(int v,int fa){//建立节点 
    t[++size].data=v;
    t[size].f=fa;
    t[size].cnt=t[size].sum=1;
    return size;
}
void push(int v){//找到插入的位置插入 
    int sign=0,nxt;
    tot++;
    if(!root)root=create(v,0);
    else{
        int now=root;
        while(now){
            t[now].sum++;
            if(t[now].data==v){
                t[now].cnt++,sign=now;
                break;
            }
            nxt=t[now].data<v?1:0;
            if(!t[now].s[nxt]){
                sign=t[now].s[nxt]=create(v,now);
                break;
            }
            now=t[now].s[nxt];
        }
    }
    splay(sign,root);
}
int find(int v){
    int now=root,nxt;
    while(now){
        if(t[now].data==v){
            splay(now,root);
            return now;
        }
        nxt=t[now].data<v?1:0;
        now=t[now].s[nxt];
    }
    return 0;
}
void destroy(int x){//删除节点 
    t[x].cnt=t[x].data=t[x].f=t[x].sum=t[x].s[0]=t[x].s[1]=0;
    if(x==size)size--;
}
void pop(int v){
    int node=find(v);
    if(!node)return;
    tot--;
    if(t[node].cnt>1){
        t[node].cnt--,t[node].sum--;
        return;
    }
    if(!t[node].s[0])root=t[node].s[1],t[root].f=0;
    else{
        int mx=t[node].s[0],B=t[node].s[1];
        while(t[mx].s[1])mx=t[mx].s[1];//找到左子树最大点，翻上来 
        splay(mx,root);
        connect(B,mx,1);
        connect(mx,0,1);
        upd(mx);
    }
    destroy(node);
}
int rank(int v){
    int ans=0,now=root,nxt;
    while(now){
        if(t[now].data==v){
            int r=ans+t[t[now].s[0]].sum+1;
            splay(now,root);
            return r;
        }
        nxt=t[now].data<v?1:0;
        if(nxt)ans+=t[t[now].s[0]].sum+t[now].cnt;
        now=t[now].s[nxt];
    }
    return ans;
}
int value(int x){
    int now=root,les,res;
    while(1){
        les=t[t[now].s[0]].sum;
        res=les+t[now].cnt;
        if(res<x)now=t[now].s[1],x-=res;
        else if(les>=x)now=t[now].s[0];
        else{splay(now,root);return t[now].data;}
    }
}
int upper(int v){
    int now=root,res=1e9;
    while(now){
        if(t[now].data>v&&t[now].data<res)res=t[now].data;
        now=t[now].s[t[now].data>v?0:1];
    }
    return res;
}
int lower(int v){
    int now=root,res=-1e9;
    while(now){
        if(t[now].data<v&&t[now].data>res)res=t[now].data;
        now=t[now].s[t[now].data>=v?0:1];//注意大于等于 
    }
    return res;
}
int main(){
    int i,n,opt,num;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&opt,&num);
        if(opt==1)push(num);
        else if(opt==2)pop(num);
        else if(opt==3)printf("%d\n",rank(num));
        else if(opt==4)printf("%d\n",value(num));
        else if(opt==5)printf("%d\n",lower(num));
        else printf("%d\n",upper(num));
    }
    return 0;
}

解题思路2：FHQ

AC代码2

#include<cstdio>
#include<cstdlib>
#define root t[0].s[1]
#define ls t[x].s[0]
#define rs t[x].s[1]
struct fhp{
    int size,key,val,s[2];
}t[100010<<1];
int tot;
void upd(int x){
    t[x].size=t[ls].size+t[rs].size+1;
}
void split(int x,int k,int &a,int &b){
    if(!x){a=b=0;return;}
    if(t[x].val<=k)a=x,split(rs,k,rs,b);
    else b=x,split(ls,k,a,ls);
    upd(x);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].key<t[y].key){rs=merge(rs,y),upd(x);return x;}
    else{t[y].s[0]=merge(x,t[y].s[0]),upd(y);return y;}
}
int newnode(int v){
    t[++tot].key=rand();
    t[tot].val=v;
    t[tot].size=1;
    return tot;
}
void ins(int v){
    int x,y;
    split(root,v,x,y);
    root=merge(merge(x,newnode(v)),y);
}
void del(int v){
    int x,y,z;
    split(root,v,x,y);
    split(x,v-1,x,z);
    z=merge(t[z].s[0],t[z].s[1]);
    root=merge(x,merge(z,y));
}
void rank(int x){
    int a,b;
    split(root,x-1,a,b);
    printf("%d\n",t[a].size+1);
    root=merge(a,b);
}
void val(int x,int v){
    while(1){
        if(v<=t[ls].size)x=ls;
        else if(v==t[ls].size+1){
            printf("%d\n",t[x].val);
            return;
        }
        else v-=t[ls].size+1,x=rs;
    }
}
void pre(int v){
    int x,y;
    split(root,v-1,x,y);
    val(x,t[x].size);
    root=merge(x,y);
}
void suc(int v){
    int x,y;
    split(root,v,x,y);
    val(y,1);
    root=merge(x,y);
}
int main(){
    int n,opt,num;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&opt,&num);
        if(opt==1)ins(num);
        else if(opt==2)del(num);
        else if(opt==3)rank(num);
        else if(opt==4)val(root,num);
        else if(opt==5)pre(num);
        else suc(num);
    }
    return 0;
}