利用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_bound和std::upper_bound，可以得到下面的这样两条语句：

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

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

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 如下：

#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，运行时间得以缩小一半。

代码：

#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);
        }
    }
}