splay 模板洛谷3369

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 xx 数

删除 xx 数(若有多个相同的数，因只删除一个)

查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 。若有多个相同的数，因输出最小的排名)

查询排名为 xx 的数

求 xx 的前驱(前驱定义为小于 xx ，且最大的数)

求 xx 的后继(后继定义为大于 xx ，且最小的数)

输入输出格式

输入格式：

第一行为 nn ，表示操作的个数,下面 nn 行每行有两个数 optopt 和 xx ， optopt 表示操作的序号( 1 \leq opt \leq 6 1≤opt≤6 )

输出格式：

对于操作 3,4,5,63,4,5,6 每行输出一个数，表示对应答案

输入输出样例

输入样例#1：复制

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

输出样例#1：复制

106465

84185

492737

说明

时空限制：1000ms,128M

1.n的数据范围： n \leq 100000 n≤100000

2.每个数的数据范围： [-{10}^7, {10}^7][−10

7

,10

7

]

来源：Tyvj1728 原名：普通平衡树

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN = 100005;

const int inf = 0x7f7f7f7f;

struct Node{

    int v,fa;

    int ch[2];

    int sum;

    int recy;

}node[MAXN];

int n,cnt,points;

inline void update(int x){

    node[x].sum=node[node[x].ch[1]].sum+node[node[x].ch[0]].sum+node[x].recy;

}

inline bool jud(int x){

    return node[node[x].fa].ch[0]==x?0:1;

}

inline void connect(int x,int f,int son){

    node[x].fa=f;

    node[f].ch[son]=x;

}

inline void rotate(int x){

    int y=node[x].fa;

    int mroot=node[y].fa;

    int mrootson=jud(y);

    int yson=jud(x);

    int oth=node[x].ch[yson^1];

    connect(oth,y,yson);

    connect(y,x,(yson^1));

    connect(x,mroot,mrootson);

    update(y);update(x);

}

inline void splay(int at,int to){

    to=node[to].fa;

    while(node[at].fa!=to){

        int up=node[at].fa;

        if(node[up].fa==to) rotate(at);

        else if(jud(up)==jud(at)){

            rotate(up);

            rotate(at);

        }

        else{

            rotate(at);

            rotate(at);

        }

    }

}

inline int crepoint(int x,int f){

    node[++cnt].v=x;

    node[cnt].fa=f;

    node[cnt].sum=1;

    node[cnt].recy=1;

    return cnt;

}

inline void destroy(int x){

    node[x].v=node[x].fa=node[x].sum=node[x].recy=node[x].ch[0]=node[x].ch[1]=0;

    if(x==cnt) cnt--;

}

inline int find(int v){

    int now=node[0].ch[1];

    while(1){

        if(node[now].v==v){

            splay(now,node[0].ch[1]);

            return now;

        }

        int nxt=v<node[now].v?0:1;

        if(!node[now].ch[nxt]) return 0;

        now=node[now].ch[nxt];

    }

}

inline int build(int x){

    points++;

    if(cnt==0){

        node[0].ch[1]=1;

        crepoint(x,0);

    }

    else{

        int now=node[0].ch[1];

        while(1){

            node[now].sum++;

            if(x==node[now].v){

                node[now].recy++;

                return now;

            }

            int nxt=x<node[now].v?0:1;

            if(!node[now].ch[nxt]){

                crepoint(x,now);

                node[now].ch[nxt]=cnt;

                return cnt;

            }

            now=node[now].ch[nxt];

        }

    }

    return 0;

}

inline void push(int x){

    int add=build(x);

    splay(add,node[0].ch[1]);

}

inline void pop(int v){

    int deal=find(v);

    if(!deal) return;

    points--;

    if(node[deal].recy>1){

        node[deal].recy--;

        node[deal].sum--;

        return;

    }

    if(!node[deal].ch[0]){

        node[0].ch[1]=node[deal].ch[1];

        node[node[0].ch[1]].fa=0;

    }

    else{

        int lef=node[deal].ch[0];

        while(node[lef].ch[1]) lef=node[lef].ch[1];

        splay(lef,node[deal].ch[0]);

        int rig=node[deal].ch[1];

        connect(rig,lef,1);connect(lef,0,1);

        update(lef);

    }

    destroy(deal);

}

int rank(int x){

    int ans=0;

    int now=node[0].ch[1];

    while(1){

        if(node[now].v==x) return ans+node[node[now].ch[0]].sum+1;

        if(now==0) return 0;

        if(x<node[now].v) now=node[now].ch[0];

        else{

            ans+=node[node[now].ch[0]].sum+node[now].recy;

            now=node[now].ch[1];

        }

    }

    if(now) splay(now,node[0].ch[1]);

    return 0;

}

int atrank(int x){

    if(x>points)    return -inf;

    int now=node[0].ch[1];

    while(1){

        int minn=node[now].sum-node[node[now].ch[1]].sum;

        if(x>node[node[now].ch[0]].sum && x<=minn) break;

        if(x<minn) now=node[now].ch[0];

        else{

            x=x-minn;

            now=node[now].ch[1];

        }

    }

    splay(now,node[0].ch[1]);

    return node[now].v;

}

inline int lower(int x){

    int now=node[0].ch[1];

    int res=-inf;

    while(now){

        if(node[now].v<x && node[now].v>res) res=node[now].v;

        if(x>node[now].v) now=node[now].ch[1];

        else now=node[now].ch[0];

    }

    return res;

}

inline int upper(int x){

    int now=node[0].ch[1];

    int res=inf;

    while(now){

        if(node[now].v>x && node[now].v<res) res=node[now].v;

        if(x<node[now].v) now=node[now].ch[0];

        else now=node[now].ch[1];

    }

    return res;

}

int main(){

    scanf("%d",&n);

    push(inf);push(-inf);

    for(register int i=1;i<=n;i++){

        int opt,x;

        scanf("%d%d",&opt,&x);

        if(opt==1) push(x);

        else if(opt==2) pop(x);

        else if(opt==3) printf("%d\n",rank(x)-1);

        else if(opt==4) printf("%d\n",atrank(x+1));

        else if(opt==5) printf("%d\n",lower(x));

        else printf("%d\n",upper(x));

    }

    return 0;

}

巴特西

splay 模板洛谷3369

最新文章

热门文章

巴特西

splay 模板 洛谷3369

最新文章

热门文章

splay 模板洛谷3369