利用vector重现set

提供一种小数据下运行效率极高的std::set替代方法。

此页面存在相关页面。关于普通平衡树,请参见「Splay」

众所周知,平衡树有两类:一类维护集合,一类维护序列。维护序列的平衡树通常作为线段树的替代,用于解决线段树并不支持的区间翻转操作;而维护集合的平衡树则可以被看作是在重现std::set

但是这并不是最简便的方案,实际上,我们可以利用std::vector去吊锤维护集合的平衡树。此种方法在 $10^5$ 量级下速度极快,运行时间甚至优于普通 Splay。

维护集合的平衡树被用来解决这样一类问题:

您需要写一种数据结构,来维护一些数,其中需要提供以下操作:

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

设 $n$ 为集合的最大大小,对所有数据,满足 $n\le 10^5$。

利用std::lower_boundstd::upper_bound,可以得到下面的这样两条语句:

1
2
lower_bound(v.begin(), v.end(), x) - v.begin() // < x 的元素个数
upper_bound(v.begin(), v.end(), x) - v.begin() // <= x 的元素个数

于是可以得到下面这份代码实现。显然,它吊锤了 Splay

1
2
3
4
5
6
7
8
9
10
11
vector<int> v; int n = read();
while(n--){
int tp = read(), x = read();
if(tp == 1) v.insert(lower_bound(v.begin(), v.end(), x), x);
if(tp == 2) v.erase(lower_bound(v.begin(), v.end(), x));
if(tp == 3) printf("%d", lower_bound(v.begin(), v.end(), x) - v.begin() + 1);
if(tp == 4) printf("%d", v[x - 1]);
if(tp == 5) printf("%d", v[lower_bound(v.begin(), v.end(), x) - v.begin() - 1]);
if(tp == 6) printf("%d", v[upper_bound(v.begin(), v.end(), x) - v.begin()]);
if(tp > 2) puts("");
}

理性分析一下,这份代码的时间复杂度为 $O(n^2\log n)$,瓶颈在于erase()insert()

但是我们可以对其进行测试,Generator 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
#include<string>
int n = 100000;
int main() {
freopen("_in.in", "w", stdout);
printf("%d", n), puts("");
int t1 = 1, t2 = 1000000000;
for(int i = 1; i < n; i++){
if(i & 1) printf("1 %d", t1++), puts("");
else printf("1 %d", t2--), puts("");
}
printf("4 %d", n / 2);
}

本机测试结果如下:

数据范围 $n=5\times10^4$ $n=10^5$ $n=5\times 10^5$ $n=10^6$
运行时间(平均,向下近似) 100ms 280ms 7.7s 30s
运行时间(平均,向下近似,O2) 70ms 280ms 7s 28s
对比(普通 Splay) 30ms 30ms 260ms 380ms

容易发现当 $n$ 超过 $10^5$ 的量级后,其运行效率略大于 $O(n\sqrt{n})$,而在之前效率及其优秀。但是实际上题目中插入操作的数量并没有达到测试中的量级,因此出现了吊锤 Splay 的现象。

于是我们可以初步地得出结论:在 $10^5$ 的数据量级下,利用vector代替 Splay 有着优秀的运行效率。

一个栗子

$n$ 个点的图,给出 $m$ 对点和 $q$ 条边。顺序尝试加入每条边,如果不会使得 $m$ 对点中的任意一对点联通,则加入,否则不加入。判断每条边是否会被加入。
$n,m,q\le 10^5$

条件反射:看到不可逆性修改操作,就应该想到结构合并。

容易想到对每个点维护一个set,表示该点不能到达的点集,然后连一条边相当于合并两个set,在合并前判断一下,然后启发式合并就好了。
然后把set换成vector,运行时间得以缩小一半。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

const int CN = 2e5 + 5;

int read(){
int s = 0,ne = 1; char c = getchar();
while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}

class DSU {
public: int fa[CN]; DSU() {for(int i = 1; i <= 100000; i++) fa[i] = i;}
int fd(int x) {return fa[x] ^ x ? fa[x] = fd( fa[x] ) : x;}
} C;

int n, m, q; vector<int> v[CN];

int main()
{
// freopen("_in.in", "r", stdin);

n = read(), m = read(), q = read();
while(m--){
int x = read(), y = read();
v[x].push_back(y), v[y].push_back(x);
}

while(q--){
int x = read(), y = read(), fx = C.fd(x), fy = C.fd(y);
if(fx == fy) {putchar('1'); continue;}

int szx = v[fx].size(), szy = v[fy].size();
if(szx > szy) swap(fx, fy), swap(szx, szy);

bool flag = true;
for(int i = 0; i < szx && flag; i++) if(C.fd( v[fx][i] ) == fy) flag = false;
if(!flag) {putchar('0'); continue;} putchar('1');
/* fx -> fy */
C.fa[fx] = fy;
for(int i = 0; i < szx; i++){
int u = v[fx][i], p = lower_bound(v[fy].begin(), v[fy].end(), u) - v[fy].begin() - 1;
if(v[fy][p] == u) continue;
v[fy].insert(lower_bound(v[fy].begin(), v[fy].end(), u), u);
}
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×