模板——数据结构

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

模板——数据结构

ST 表，Trie 树，并查集，笛卡尔树，树上启发式合并，Kruskal 重构树，Bitset，线性基，链表。

ST 表

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
#include<bits/stdc++.h>
using namespace std;
const int V = 17, N = 200000 + 5;
int st[V + 5][N], b[N], n, m;

int main() {
    int x, y, len;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &st[0][i]);
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= n; j++)
            st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); //区间最大max 区间最小min
    /*     f[i-1][j]     f[i-1][j+2^(i-1)]
       |----------------|----------------|
                 total: f[i][j]               */
    for (int i = 1; i <= V; i++) //快速得到 log_2 N
        b[1 << i] = 1;
    for (int i = 1; i <= n; i++)
        b[i] += b[i - 1];
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        len = y - x + 1;
        printf("%d\n", max(st[b[len]][x], st[b[len]][y + 1 - (1 << b[len])]));
    }
    return 0;
}

Trie 树

经常在一些二进制相关题目中使用（01-Trie），出现二进制应考虑。

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
#define mset(a) memset(a,0,sizeof(a))
const int FOUND = 1, VISITED = 2, UNFOUND = 3; //找到了，重复找，未找到
struct Trie {
    int index = 0; //用以做编号
    struct Node {
        int qcnt = 0, exist = 0, etc; //字符串访问次数，是否为字符串等附加信息
        int son[50] = {}; //儿子节点
        //字符串这里意为完整的、自根节点到叶子节点组成的字符串
    } node[500000 + 10];

    int getid(char ch) { return ch - 'a'; }

    void insert(char s[]) //插入操作
    {
        int sons, root = 0, len = strlen(s);
        for (int i = 0; i <= len - 1; i++) {
            sons = getid(s[i]);
            if (!node[root].son[sons])
                node[root].son[sons] = ++index;
            root = node[root].son[sons];
        }
        node[root].exist = 1; //标记这是个字符串
    }

    int find(char s[]) //查询操作
    {
        int sons, root = 0, len = strlen(s);
        for (int i = 0; i <= len - 1; i++) {
            sons = getid(s[i]);
            if (!node[root].son[sons])
                return UNFOUND;
            root = node[root].son[sons];
        }
        if (!node[root].exist)
            return UNFOUND;
        if (!node[root].qcnt) {
            node[root].qcnt++;
            return FOUND;
        }
        return VISITED;
    }
} trie;

并查集

路径压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct UFDS {
    ll dad[M], n;
    void init(ll p) {
        n = p;
        for (ll i = 1; i <= n; i++)
            dad[i] = i;
    }
    ll find(ll x) {
        while (x != dad[x])
            x = dad[x] = dad[dad[x]];
        return x;
    }
    void merge(ll x, ll y) {
        ll d1 = find(x), d2 = find(y);
        dad[d1] = d2;
    }
    bool check(ll x, ll y) {
        ll d1 = find(x), d2 = find(y);
        if (d1 == d2)
            return 1;
        return 0;
    }
} ufds;

递归版路径压缩：

1
2
3
4
5
6
int find(int x)
{
	if(dad[x]==x)
    	return dad[x];
    return dad[x]=find(dad[x]);
}

按秩合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void start(int n) {
    for (int i = 1; i <= n; i++)
        dad[i] = i, rank[i] = 0; //树的高度为0
    return;
}
ll find(ll x) {
    while (x != dad[x])
        x = dad[x];
    return x;
}
void merge(int x, int y) {
    int d1 = find(x), d2 = find(y);
    if (d1 == d2) return;
    if (rank[d1] > rank[d2])
        swap(d1, d2);
    dad[d1] = d2;
    if (rank[d1] == rank[d2]) //如果相等，只能增加树高
        rank[d2]++;
    return; //否则树高是不增加的
}

扩展域并查集

扩展域并查集可以维护多组关系，适用于有多组关系需要用并查集维护的题目，并且可以不用推像带权并查集那样繁琐的式子。其主要思想是将一个点拆分成好几个点来维护多组关系。

这类题目只要找准题目中有几组关系，把握住，我的敌人的敌人就是我的朋友的原则（大部分题满足，可能有少部分题不满足这个原则，注意分析）。

例如：一个表示“朋友”关系，另一个表示“敌人”关系。每次合并 x 和 y 的敌人域 ，以及 y 和 x 的敌人域。“敌人域”的实现：设 x 和 x+n 是敌人，那么 x+n 和 y 就是朋友了。

笛卡尔树

笛卡尔树是一种特殊的二叉树，每一个节点由一个键值二元组构成，并且同时满足以下两个性质：

  • 键——二叉搜索树（BST）性质：对于树中的每一个节点，其左子树中的所有节点的值都小于该节点的值；其右子树中的所有节点的值都大于该节点的值。这保证了树在中序遍历时会按照输入序列的顺序访问元素。
  • 值——堆性质：如果我们将笛卡尔树看作是一个最大堆或最小堆，则对于每个节点来说，它的值要么不小于或者不大于其子节点的值。具体采用哪种堆取决于应用场景。

经常用于最值维护、最近公共祖先问题。例如柱状图找面积最大的矩形。Treap 维护的也是笛卡尔树。

1
2
3
4
5
6
7
8
9
10
11
12
13
int cartesian_build(int n) {
    // 建树，满足小根堆性质
    for (int i = 1; i <= n; i++) {
        int k = i - 1;
        while (tree[k].val > tree[i].val)
            k = tree[k].par;
        tree[i].ch[0] = tree[k].ch[1];
        tree[k].ch[1] = i;
        tree[i].par = k;
        tree[tree[i].ch[0]].par = i;
    }
    return tree[0].ch[1];
}

树上启发式合并

例如计算 \(\sum_{d(x)=d(y),1\le x<y\le n}d(y)-d(lca(x,y))\)。

\(O(n\log n)\) 版：

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
vector<ll> e[N];
ll a[N], d[N], cnt[N], big[N], siz[N], ans;
ll dfn[N], L[N], R[N], index;
ll n, m;

ll dfs(ll root, ll dad) {
    ll curb = 0;
    d[root] = d[dad] + 1;
    siz[root]++;
    dfn[++index] = root;
    L[root] = index;
    for (auto son: e[root]) {
        if (son == dad)
            continue;
        siz[root] += dfs(son, root);
        if (siz[son] > curb) {
            curb = siz[son];
            big[root] = son;
        }
    }
    R[root] = index;
    return siz[root];
}

void dsu(ll root, ll dad, ll keep) {
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        dsu(son, root, 0);
    }
    if (big[root])
        dsu(big[root], root, 1);
    for (auto son: e[root]) {
        if (son == dad || son == big[root])
            continue;
        for (ll i = L[son]; i <= R[son]; i++) {
            ans += cnt[d[dfn[i]]] * (d[dfn[i]] - d[root]);
        }
        for (ll i = L[son]; i <= R[son]; i++) {
            cnt[d[dfn[i]]]++;
        }
    }
    cnt[d[root]]++;
    if (keep == 0) {
        for (ll i = L[root]; i <= R[root]; i++) {
            cnt[d[dfn[i]]]--;
        }
    }
}

Kruskal 重构树

原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

也就是说，到点 x 的简单路径上最大边权的最小值 \(\leq val\) 的所有点 y 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点。

注意重构树新建了节点，初始化范围为 \(n+m\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sort(h + 1, h + 1 + m, cmp);//按照边权排序
for (ll i = 1; i <= m; i++) {
    ll u = s.find(h[i].u), v = s.find(h[i].v);//并查集
    if (u != v) {
        cnt++;
        s.merge(u, cnt);
        s.merge(v, cnt);
        high[cnt] = h[i].len;//点权为边权
        e[u].push_back(cnt);
        e[cnt].push_back(u);
        e[v].push_back(cnt);
        e[cnt].push_back(v);
    }
}
dfs(cnt, cnt);

Bitset

一定要注意！！！bitset 不要和整数进行运算！！！而且整数没有 bitset 存的那么大！！！

头文件

1
#include <bitset>

指定大小

1
std::bitset<1000> bs;  // a bitset with 1000 bits

构造函数

  • bitset(): 每一位都是 false．
  • bitset(unsigned long val): 设为 val 的二进制形式．
  • bitset(const string& str): 设为 \(01\) 串 str．

运算符

  • operator []: 访问其特定的一位．

  • operator ==/operator !=: 比较两个 bitset 内容是否完全一样．

  • operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: 进行按位与/或/异或/取反操作．

    注意：bitset 只能与 bitset 进行位运算，若要和整型进行位运算，要先将整型转换为 bitset．

  • operator <</operator >>/operator <<=/operator >>=: 进行二进制左移/右移．

此外，bitset 还提供了 C++ 流式 IO 的支持，这意味着你可以通过 cin/cout 进行输入输出．

成员函数

  • count(): 返回 true 的数量．
  • size(): 返回 bitset 的大小．
  • test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查．
  • any(): 若存在某一位是 true 则返回 true，否则返回 false．
  • none(): 若所有位都是 false 则返回 true，否则返回 false．
  • all(): 若所有位都是 true 则返回 true，否则返回 false．
    1. set(): 将整个 bitset 设置成 true．
    2. set(pos, val = true): 将某一位设置成 true/false．
    1. reset(): 将整个 bitset 设置成 false．
    2. reset(pos): 将某一位设置成 false．相当于 set(pos, false)．
    1. flip(): 翻转每一位．（\(0\leftrightarrow1\)，相当于异或一个全是 \(1\) 的 bitset）
    2. flip(pos): 翻转某一位．
  • to_string(): 返回转换成的字符串表达．
  • to_ulong(): 返回转换成的 unsigned long 表达（long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）．
  • to_ullong():（C++11 起）返回转换成的 unsigned long long 表达．

另外，libstdc++ 中有一些较为实用的内部成员函数：

  • _Find_first(): 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小．
  • _Find_next(pos): 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小．

线性基

贪心法构造

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
const ll N = 1e5 + 10, M = 52;
ll n, p[M + 10], d[M + 10], dcnt;

void insert(ll x) {
    for (ll i = M; i >= 0; i--) {
        if ((x >> i) & 1ll) {
            if (!p[i]) {
                p[i] = x;
                return;
            }
            x ^= p[i];
        }
    }
    // 运行到这里说明可以表示 0
}

ll queryMax(ll ret = 0) {
    for (ll i = M; i >= 0; i--) {
        ret = max(ret, ret ^ p[i]);
    }
    return ret;
}

//最小值就是线性基最小的元素

void rebuild() { // 重建为行简化，其中 d[] 去除 0 位，必须在排名相关操作前进行一次
    dcnt = 0;
    for (ll i = M; i >= 0; i--)
        for (ll j = i - 1; j >= 0; j--)
            if (p[i] & (1ll << j)) {
                p[i] ^= p[j];
            }
    for (ll i = 0; i <= M; i++)
        if (p[i]) {
            d[dcnt++] = p[i];
        }
}

ll kthMin(int k) {
    if (k >= (1ll << dcnt)) {
        return -1;
    }
    ll ans = 0;
    for (ll i = M; i >= 0; i--)
        if (k & (1ll << i)) {
            ans ^= d[i];
        }
    return ans;
}

ll rankMin(ll x) {
    ll ans = 0;
    for (ll i = dcnt - 1; i >= 0; i--)
        if (x >= d[i])
            ans += (1 << i), x ^= d[i];
    return ans;
}

void solve() {
    cin >> n;
    for (ll i = 1, a; i <= n; i++) {
        cin >> a;
        insert(a);
    }
    cout << queryMax() << endl;
}

高斯消元法构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ull deg(ull num, int deg) { return num & (1ull << deg); }

	cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int row = 1;
    for (int col = 52; ~col && row <= n; --col) {
        for (int i = row; i <= n; ++i) {
            if (deg(a[i], col)) {
                swap(a[row], a[i]);
                break;
            }
        }
        if (!deg(a[row], col))
            continue;
        for (int i = 1; i <= n; ++i) {
            if (i == row)
                continue;
            if (deg(a[i], col)) {
                a[i] ^= a[row];
            }
        }
        ++row;
    }

高斯消元后的矩阵是一个行简化阶梯形矩阵。

链表

1
2
3
4
list<int> l;//空的双向链表
list<int> l2(5);//初始化5个元素，默认值为类型的默认值
list<int> l3(5, 111);//初始化5个元素，每个元素初始值为111
list<int> l4(l3);//拷贝构造
1
2
3
4
5
6
7
8
9
10
11
12
13
14
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置前插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置前插入n个elem数据。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
//以上复杂度为常数或与元素个数有关。

remove(elem);//删除容器中所有与elem值匹配的元素。
remove_if(p);//删除bool p(T v);返回true的元素。
//复杂度O(n)。
1
2
3
4
5
6
7
size();//返回容器中元素的个数 
empty();//判断容器是否为空 

front();//返回第一个元素。 
back();//返回最后一个元素。
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。 O(n)
sort(); //list排序 O(nlogn)

可以使用 map<int, list<T>::iterator> 表示 ID - 迭代器 的关系，实现增、删、ID 随机访问 \(O(\log n)\) 的数组。