Sunglassman 的算法竞赛板子整理——数据结构篇

发表于 更新于 分类于 ， ，

Sunglassman 的算法竞赛板子整理——数据结构篇

懒标记线段树

P3372 【模板】线段树 1

题目描述

如题，已知一个数列 ${a_i}$，你需要进行下面两种操作：

  1. 将某区间每一个数加上 $k$。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数 $a_i$，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
  2. 2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

1
2
3
11
8
20

说明/提示

对于 $15%$ 的数据：$n \le 8$，$m \le 10$。
对于 $35%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100%$ 的数据：$1 \le n, m \le {10}^5$，$a_i,k$ 为正数，且任意时刻数列的和不超过 $2\times 10^{18}$。

【样例解释】

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
int n, m;

long long a[M];

class SegTree {
  private:
    long long tr[M << 2], laz[M << 2];
    void up(int u) {
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
    }
    void down(int u, int l, int r) {
        if (laz[u]) {
            int mid = l + r >> 1;
            tr[u << 1] += (mid - l + 1) * laz[u];
            tr[u << 1 | 1] += (r - mid) * laz[u];
            laz[u << 1] += laz[u], laz[u << 1 | 1] += laz[u];
            laz[u] = 0;
        }
    }
    void build(int u, int l, int r) {
        if (l == r) {
            tr[u] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        up(u);
    }
    void modify(int u, int l, int r, int ql, int qr, long long k) {
        if (ql <= l && qr >= r) {
            tr[u] += 1ll * (r - l + 1) * k;
            laz[u] += k;
            return;
        }
        down(u, l, r);
        int mid = l + r >> 1;
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, k);
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, k);
        up(u);
    }    
    long long query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && qr >= r) {
            return tr[u];
        }
        down(u, l, r);
        int mid = l + r >> 1;
        long long ans = 0;
        if (ql <= mid) ans += query(u << 1, l, mid, ql, qr);
        if (qr > mid) ans += query(u << 1 | 1, mid + 1, r, ql, qr);
        return ans;
    }     
  public:
    void build() {
        return build(1, 1, n);
    }
    void modify(int l, int r, long long k) {
        return modify(1, 1, n, l, r, k);
    }
    long long query(int l, int r) {
        return query(1, 1, n, l, r);
    }
} SGT;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    SGT.build();
    // exit(0);
    while (m--) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) {
            long long k; cin >> k;
            SGT.modify(x, y, k);
        }
        else {
            long long ans = SGT.query(x, y);
            cout << ans << '\n';
        }
    }
    return 0;
}

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int a[N];
stack<int> stk;
int res[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = n; i >= 1; i--) {
        while (!stk.empty() && a[i] >= a[stk.top()]) {
            stk.pop();
        }
        res[i] = (stk.empty()) ? 0 : stk.top();
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << " ";
    }
    return 0;
}

三维偏序

P3810 【模板】三维偏序（陌上花开）

题目描述

有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。

对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。

输入格式

第一行两个整数 $ n,k $，表示元素数量和最大属性值。

接下来 $ n $ 行，每行三个整数 $ a_i ,b_i,c_i $，分别表示三个属性值。

输出格式

$ n $ 行，第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出 #1

1
2
3
4
5
6
7
8
9
10
3
1
3
0
1
0
1
0
0
1

说明/提示

$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。

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
int n, k, m, t, res[N];

struct Node {
    int a, b, c;
    int cnt, res;
    bool operator != (const Node& t) const {
        return a != t.a || b != t.b || c != t.c;
    }
} e[N], ue[N];

bool cmpA (const Node& x, const Node& y) {
    if (x.a != y.a) return x.a < y.a;
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}

bool cmpB (const Node& x, const Node& y) {
    if (x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}

class BIT {
  private:
    int tr[M];
    int lowbit(int x) {
        return x & -x;
    }
  public:
    void add(int pos, int val) {
        for (; pos <= k; pos += lowbit(pos)) {
            tr[pos] += val;
        }
    }
    int qry(int pos) {
        int res = 0;
        for (; pos; pos -= lowbit(pos)) {
            res += tr[pos];
        }
        return res;
    }
} Bit;

void CDQ(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    CDQ(l, mid), CDQ(mid + 1, r);
    sort(ue + l, ue + mid + 1, cmpB);
    sort(ue + mid + 1, ue + r + 1, cmpB);
    int i = l, j = mid + 1;
    while (j <= r) {
        while (i <= mid && ue[i].b <= ue[j].b) {
            Bit.add(ue[i].c, ue[i].cnt);
            ++i;
        }
        ue[j].res += Bit.qry(ue[j].c);
        ++j;
    }
    for (int id = l; id < i; ++id) {
        Bit.add(ue[id].c, -ue[id].cnt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> e[i].a >> e[i].b >> e[i].c;
    }
    sort(e + 1, e + n + 1, cmpA);
    m = 0, t = 0;
    for (int i = 1; i <= n; ++i) {
        ++t;
        if (e[i] != e[i + 1]) {
            ue[++m].a = e[i].a, ue[m].b = e[i].b, ue[m].c = e[i].c;
            ue[m].cnt = t;
            t = 0;
        }
    }
    CDQ(1, m);
    for (int i = 1; i <= m; ++i) {
        res[ue[i].res + ue[i].cnt - 1] += ue[i].cnt;
    }
    for (int i = 0; i < n; ++i) {
        cout << res[i] << '\n';
    }

    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;
string str;

void insert(string str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        char op;
        cin >> op >> str;
        if (op == 'I') insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}

Trie树———最长异或路径

P4551 最长异或路径

题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。求树中所有异或路径的最大值。

异或路径指树上两个结点之间唯一路径上的所有边权的异或值。

输入格式

第一行一个整数 $n$，表示结点数。

接下来 $n-1$ 行，给出 $u,v,w$ ，分别表示树上的 $u$ 点和 $v$ 点有连边，边的权值是 $w$。

输出格式

一行，一个整数表示答案。

输入输出样例 #1

输入 #1

1
2
3
4
4
1 2 3
2 3 4
2 4 6

输出 #1

1
7

说明/提示

当两个结点分别是 $1,3$ 时，答案是 $7=3\oplus 4$，取最大值。

数据范围

$1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}$。

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
int n, x, y, z;
int vis[M], d[M];

vector<vector<int>> adj;

int tr[M * 32][2], id;

void insert(int x) {
    int p = 0;
    for (int i = 30; ~i; --i) {
        int &t = tr[p][x >> i & 1];
        if (!t) t = ++id;
        p = t;
    }
}

int query(int x) {
    int ans = 0;
    int p = 0;
    for (int i = 30; ~i; --i) {
        int t = x >> i & 1;
        if (tr[p][!t]) ans |= 1 << i, p = tr[p][!t];
        else p = tr[p][t];
    }
    return ans;
}

void solve() {
    cin >> n;
    adj.resize(n + 1);
    for (int i = 1; i < n; ++i) {
        cin >> x >> y >> z;
        adj[x].eb(y, z);
        adj[y].eb(x, z);
    }
    queue<int> q;
    q.push(1), d[1] = 0, vis[1] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (auto & [u, w] : adj[t]) {
            if (!vis[u]) q.push(u), d[u] = d[t] ^ w, vis[u] = 1;
        }
    }

    for (int i = 1; i <= n; ++i) {
        insert(d[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = max(res, query(d[i]));
    }
    cout << res << '\n';
}

P5854 笛卡尔树

题目描述

给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。

即构建一棵二叉树，满足：

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。

输入格式

第一行一个整数 $n$。

第二行一个排列 $p_{1 \dots n}$。

输出格式

设 $l_i,r_i$ 分别表示节点 $i$ 的左右儿子的编号（若不存在则为 $0$）。

一行两个整数，分别表示 $\operatorname{xor}{i = 1}^n i \times (l_i + 1)$ 和 $\operatorname{xor}{i = 1}^n i \times (r_i + 1)$。

输入输出样例 #1

输入 #1

1
2
5
4 1 3 2 5

输出 #1

1
19 21

说明/提示

【样例解释】

$i$ $l_i$ $r_i$
$1$ $0$ $0$
$2$ $1$ $4$
$3$ $0$ $0$
$4$ $3$ $5$
$5$ $0$ $0$

$1 \le n \le 10^7$。

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
#include <bits/stdc++.h>
using namespace std;

constexpr int M = 1e7 + 10;

int a[M], stk[M], top, pos, ls[M], rs[M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos = top;
        while (pos && a[stk[pos]] > a[i]) --pos;
        if (pos) rs[stk[pos]] = i;
        if (pos < top) ls[i] = stk[pos + 1];
        stk[top = ++pos] = i;
    }
    long long L = 0, R = 0;
    for (int i = 1; i <= n; ++i) {
        L ^= 1ll * i * (ls[i] + 1), R ^= 1ll * i * (rs[i] + 1);
    }
    cout << L << ' ' << R << '\n';
    return 0;
}