模板-数据结构

发表于 更新于 分类于

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 不带权并查集
const int N;

int p[N];

//merge
p[find(a)] = find(b);

int find(int x)
{
    if (x == p[x])
        return x;
    return p[x] = find(p[x]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 带权并查集
const int N;

int p[N];
int d[N];
int l[N];

void merge(int a, int b) // add a to end of b
{
    int ra = find(a), rb = find(b);
    p[ra] = rb;
    d[ra] = l[rb];
    l[rb] += l[ra];
}

int find(int x)
{
    if (x == p[x])
        return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    p[x] = root;
}

二叉堆

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
// 以小根堆为例
const int N = 10010;

int heap[N], size = 0;

void up(int p)
{
    if (p == 1)
        return;
    if (heap[p] < heap[p / 2])
    {
        swap(heap[p], heap[p / 2]);
        up(p / 2);
    }
}

void down(int p)
{
    int s = p * 2;
    if (s > size)
        return;
    if (heap[s + 1] < heap[s])
        s++;
    if (heap[s] < heap[p])
    {
        swap(heap[p], heap[s]);
        down(s);
    }
}

void insert(int val)
{
    heap[++size] = val;
    up(size);
}

void pop()
{
    heap[1] = heap[size--];
    down(1);
}

树状数组

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
const int N;
int n;
int a[N];
int p[N];
int tr[N];

inline int lowbit(int x) {return x & -x;}

void build()
{
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        tr[i] = p[i] - p[i - lowbit(i)];
}

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}

void sum(int x)
{
    int res;
    for (int i = x; i >= 1; i -= lowbit(i))
        sum += tr[i];
    return res;
}

线段树

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
// 无 lazy tag （以存储最大值为例）
const int N;

int a[N];

struct TreeNode
{
    int l;
    int r;
    int v;
} tr[N << 2];

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r)
        tr[u].v = a[l];
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x)
        tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            modify(u << 1, x, v);
        else
            modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid)
            res = query(u << 1, l, r);
        if (r > mid)
            res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
}
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
// 含lazy tag （以存储区间和为例）
using ll = long long;
const int N;

ll a[N];

struct TreeNode
{
    ll l, r;
    ll sum;
    ll add;
} tr[N << 2];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    if (!tr[u].add)
        return;
    auto &root = tr[u],
         &left = tr[u << 1],
         &right = tr[u << 1 | 1];
    left.add += root.add;
    left.sum += (left.r - left.l + 1) * root.add;
    right.add += root.add;
    right.sum += (right.r - right.l + 1) * root.add;
    root.add = 0;
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, r, a[l], 0};
        return;
    }
    tr[u] = {l, r, 0, 0};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int x)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
        tr[u].add += x;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, x);
    if (r > mid)
        modify(u << 1 | 1, l, r, x);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    ll res = 0;
    if (l <= mid)
        res += query(u << 1, l, r);
    if (r > mid)
        res += query(u << 1 | 1, l, r);
    return res;
}

AC自动机

1