首页 算法题

[latexpage]

题目描述

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

  1. 插入$x$ 数
  2. 删除 $x$ 数(若有多个相同的数，因只删除一个)
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 +1 )
  4. 查询排名为 $x$ 的数
  5. 求 $x$ 的前驱(前驱定义为小于 $x$，且最大的数)
  6. 求 $x$ 的后继(后继定义为大于 $x$，且最小的数)

输入格式

第一行为 $n$，表示操作的个数,下面 $x$ 行每行有两个数 opt 和 $x$，opt 表示操作的序号.

输出格式

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

splay的定义

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在 O(logn)内完成插入、查找和删除操作.
它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的.

在伸展树上的一般操作都基于伸展操作：
假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置.
于是想到设计一个简单方法：
在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方.
伸展树应运而生：
伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去.
它的优势在于不需要记录用于平衡树的冗余信息.

总的来说,伸展树在每一次增改查之后就会把被查询的元素放到根部

数据结构定义

1
2
3
4
5
6
7
8
9
struct splay{
    int ch[2];
    int val;//数值
    int size;//子树大小
    int cnt;//每个节点所含副本数
    int parent;
}splay[N];
int total;
int root;

这里用数组来模拟树,树的节点个数为total,根结点记录在root,那么splay[root]就是根结点,其中每个节点记录本身的值,左子树和右子树信息,每个节点含有副本数量,和这个节点对应子树的大小.

PushOff操作

在每一次对树进行操作的之后都要进行一次pushoff操作,来更新size区域.

1
2
3
4
5
void pushup(int node_id){
    int l=splay[node_id].ch[0];
    int r=splay[node_id].ch[1];
    splay[node_id].size=splay[l].size+splay[r].size+splay[node_id].cnt;
}

单旋转操作

每次旋转操作其实上都是将父亲和儿子进行交换,就是x和x.parent进行交换.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void rotate (int x) {
    int fa = splay[x].parent;
    int Gfa = splay[fa].parent;
    int k = (splay[fa].ch[1]==x);
    int g = (splay[Gfa].ch[1]==fa);
    splay[Gfa].ch[g]=x;
    splay[x].parent=Gfa;
    
    splay[fa].ch[k]=splay[x].ch[k^1];
    splay[splay[x].ch[k^1]].parent=fa;
    
    splay[x].ch[k ^ 1]=fa;
    splay[fa].parent=x;
    pushup(fa);
    pushup(x);
}

交换需要借助父亲的父亲,也就是祖父的力量,首先我们先记录x是fa=x.parent左儿子还是右儿子,结果记为k(1:右儿子,0:左儿子),然后记录fa是Gfa=fa.parent的左儿子还是右儿子,计为g(1:右儿子,0:左儿子).

下面为了叙述方便,我们定义一个奇怪的定义,就是外孙,比如说x是fa的左儿子,那么x的右儿子就是fa的外孙;x是fa的右儿子,那么x的左儿子就是x的外孙.

这个时候有三个点,分别是父亲、祖父和儿子,分别代表Gfa、fa和x.
首先第一步就是祖父的儿子从fa替换成x.
第二步就是父亲的儿子从x替换成x的外孙.
第三步就是原本x的外孙的位子由fa占领.

这个是最难的一部分,还是希望还是可以记住执行的顺序,一个是替换祖父的儿子,然后替换父亲的儿子,然后替换儿子的儿子,这是替换顺序,替换成什么可以记下来,分别是儿子,父亲的外孙和父亲.

实在太难怎么办?把旋转的画法画下来带进考场,反正CSP是开卷orz.

splay操作

我们需要做到的就是增改查的节点送到根结点,那么我们可以设计一个函数,这个函数叫做splayed(x,y).目的就是把编号为x的节点送到y的儿子处.所以说用形式语言我们可以这么写$x.parent==y$.就是x的父亲为y.

说句题外话,因为节点是从1开始编号的,所以说有且只有一个结点就是根结点的父亲为0.所以说想把数送到根结点需要执行splayed(x,0).

我们在之前还是知道rotate操作可以把一个数在树中的层数-1.这就好办,我们每次都做rorate操作,直到这个数的父亲是y为止.但是学过AVL的旋转我们知道,旋转可以分为单旋和双旋的,其实这个也是一样的.

判断究竟是一字旋转还是之字旋转其实就判断(splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x).这个异或可以判断儿子情况是不是一样的.

但是有一个问题就是,我们不知道旋转能不能做,因为在rotate函数中,我们充分相信fa和Gfa都是有意义的.所以说在splay操作调用rotate时我们要保证x是有意义的.

由于旋转是两个两个来做的,首先第一步,我们判断我们能不能做两次旋转操作,然后判断我们能不能做一次操作.判断的方法在代码中有说.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
    while (splay[x].parent != goal) {
        int fa = splay[x].parent, Gfa = splay[fa].parent;
        //能做两次吗?
        if (Gfa!= goal)
            ((splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
        //splay[x].parent != goal 判断能做一次旋转操作吗?
        rotate (x);
    }
    //如果goal为0,代表要改根结点
    if (!goal)
        root=x;
}

insert操作

解决了最核心的旋转问题,我们可以专注搞增删改查了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(int x) {
    int u=root, fa=0;
    while (u && splay[u].val!=x) {
        fa = u;
        u=splay[u].ch[x>splay[u].val];
    }
    if (u)
        splay[u].cnt ++;
    else {
        u=++total;
        if (fa)
            splay[fa].ch[x > splay[fa].val] = u;
        splay[u].ch[0] = splay[u].ch[1] = 0;
        splay[u].val = x;
        splay[u].parent = fa;
        splay[u].cnt = splay[u].size = 1;
    }
    splayed(u,0);
}

我们注意到有一个前提,这个前提就是这个树是一个BST,也就是说我们查找可以根据BST性质来进行查找,查找的目的就是找到合适的地方来处理.

如果查找到的地方是空,说明之前没有插入过值为x的结点,如果找到了就增加引用数即可.

find操作

insert操作其实就是基于find操作执行的,也是满足BST性质,如果你忘了我就告诉你一下,小的往左,大的往右,在空和找到了的地方下停下来.

1
2
3
4
5
6
7
8
void find(int x){
    if (!root)
            return;
        int u=root;
        while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
            u=splay[u].ch[x > splay[u].val];
        splayed (u,0);
}

前序和后序操作

我们首先调用find(x)函数,find(x)函数会帮我找到x并且把x放到根.我们假设x存在,那么x是根结点.那么就很好做,前序结点就是先往左然后一直往右,后序结点就是先往右然后一直往左.

但是万一x没找到呢?也不要紧,那么我们可以知道查询的结果往往是最接近x的结果,所以说我们可以假设,如果找的是前序结点并且当前根结点小于x,那就是根结点.同样的,如果要找后序结点并且根结点大于x,那就是根结点.如果不对的话,那我们还是按照x存在的方法寻找.

1
2
3
4
5
6
7
8
9
10
11
12
13
int PreSuf (int x, int f) {
    find (x);
    if (splay[root].val>x&&f)
        return root;
    if (splay[root].val < x && !f)
        return root;
    int u = splay[root].ch[f];
    if (!u)
        return 0;
    while (splay[u].ch[f ^ 1])
        u =splay[u].ch[f ^ 1];
    return u;
}

Delete操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Delete (int x) {
    int pre = PreSuf(x,0);
    int suf = PreSuf(x,1);
    splayed(pre,0);
    splayed(suf,pre);
    int u = splay[suf].ch[0];
    if (splay[u].cnt>1) {
        splay[u].cnt--;
        splayed ( u, 0 );
    }
    else{
        splay[suf].ch[0] = 0;
    }
}

我们求得x的前序和后序,然后把前序放到根,后序在根的右儿子,这个时候比x前序还小的在根结点左儿子,比x后序还大的在根结点的右儿子的右儿子,x就在根结点的右儿子的左儿子.然后比较cnt,删除即可.

第k个操作

之前的size派上用场了!因为左子树的size就是比x小的个数,右子树的size是比x大的个数.那么我们可以选择往左还是往右,判断的依据是$k>left.size?right:left$.如果往右的话,k要减去left.size+1,因为我们不考虑最小的left.size+1个元素了,你现在是k-left.size+1小的元素了.以此类推.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findkth (int x) {
    if (splay[root].size<x)
        return -1;
    int u=root;
    while (1) {
        if ( x <= splay[splay[u].ch[0]].size )
            u = splay[u].ch[0];
        else if ( x <= splay[u].cnt + splay[splay[u].ch[0]].size )
                return u;
            else {
                x -= ( splay[splay[u].ch[0]].size + splay[u].cnt );
                u = splay[u].ch[1];
            }
    }
}

插入INF和-INF

INF和-INF可以作为哨兵,如果有哨兵存在，那么这些点永远都不会是死在最前面或者死的时候垫在最下面，就帮助我们少考虑很多边界，我昨天没有加哨兵，不停地补刀做手术，还是千疮百孔，病很多都是并发症，医不过来，加了个哨兵，自己就好了

总的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <stdlib.h>
#define N 1000005
#define INF 0x7f7f7f7f
struct splay{
    int ch[2];
    int val;//数值
    int size;//子树大小
    int cnt;//每个节点所含副本数
    int parent;
}splay[N];
int total;
int root;
int na;
void pushup(int node_id){
    int l=splay[node_id].ch[0];
    int r=splay[node_id].ch[1];
    splay[node_id].size=splay[l].size+splay[r].size+splay[node_id].cnt;
}

void rotate (int x) {
    int fa = splay[x].parent;
    int Gfa = splay[fa].parent;
    int k = (splay[fa].ch[1]== x);
    splay[Gfa].ch[splay[Gfa].ch[1]==fa] = x;
    splay[x].parent = Gfa;
    splay[fa].ch[k] = splay[x].ch[k^1];
    splay[splay[x].ch[k^1]].parent= fa;
    splay[x].ch[k ^ 1] = fa;
    splay[fa].parent = x;
    pushup(fa);
    pushup(x);
}
//将x旋转到goal的儿子
void splayed ( int x, int goal ) {
    while (splay[x].parent != goal) {
        int fa = splay[x].parent, Gfa = splay[fa].parent;
        if (Gfa!= goal )
            ( (splay[Gfa].ch[0] == fa) ^ (splay[fa].ch[0] == x)) ? rotate(x) : rotate (fa);
        rotate (x);
    }
    if (!goal)
        root=x;
}
void insert(int x) {
    int u=root, fa=0;
    while (u && splay[u].val!=x) {
        fa = u;
        u=splay[u].ch[x>splay[u].val];
    }
    if (u)
        splay[u].cnt ++;
    else {
        u=++total;
        if (fa)
            splay[fa].ch[x > splay[fa].val] = u;
        splay[u].ch[0] = splay[u].ch[1] = 0;
        splay[u].val = x;
        splay[u].parent = fa;
        splay[u].cnt = splay[u].size = 1;
    }
    splayed(u,0);
}

void find(int x){
    if (!root)
            return;
        int u=root;
        while (splay[u].ch[x > splay[u].val] && x!=splay[u].val)
            u=splay[u].ch[x > splay[u].val];
        splayed (u,0);
}
int PreSuf (int x, int f) {
    find (x);
    if (splay[root].val>x&&f)
        return root;
    if (splay[root].val < x && !f)
        return root;
    int u = splay[root].ch[f];
    if (!u)
        return 0;
    while (splay[u].ch[f ^ 1])
        u =splay[u].ch[f ^ 1];
    return u;
}

void Delete (int x) {
    int pre = PreSuf(x,0);
    int suf = PreSuf(x,1);
    splayed(pre,0);
    splayed(suf,pre);
    int u = splay[suf].ch[0];
    if (splay[u].cnt>1) {
        splay[u].cnt--;
        splayed ( u, 0 );
    }
    else{
        splay[suf].ch[0] = 0;
    }
        
}

int findkth (int x) {
    if (splay[root].size<x)
        return -1;
    int u=root;
    while (1) {
        if ( x <= splay[splay[u].ch[0]].size )
            u = splay[u].ch[0];
        else if ( x <= splay[u].cnt + splay[splay[u].ch[0]].size )
                return u;
            else {
                x -= ( splay[splay[u].ch[0]].size + splay[u].cnt );
                u = splay[u].ch[1];
            }
    }
}
void build(){
    insert(INF);
    insert(-INF);
}
int main(){
    int n;
    build();
    scanf("%d",&n);
    int opt,x;
    int u;
    while(n--){
        scanf("%d %d",&opt,&x);
        switch (opt) {
            case 1:
                insert(x);
                break;
            case 2:
                Delete(x);
                break;
            case 3:
                find(x);
                printf("%d\n",splay[splay[root].ch[0]].size);
                break;
            case 4:
                u=findkth(x+1);
                printf("%d\n",splay[u].val);
                break;
            case 5:
                u=PreSuf(x, 0);
                printf("%d\n",splay[u].val);
                break;
            case 6:
                u=PreSuf(x, 1);
                printf("%d\n",splay[u].val);
                break;
            default:
                break;
        }
    }
}
更新于

请我喝[茶]~(￣▽￣)~*

Sukuna 微信支付

微信支付

Sukuna 支付宝

支付宝