XCPC板子 - ゆき

线性结构#

KMP#

1
class KMP2 {
2
private:
3
    std::vector<std::vector<int>> dp;
4
    std::string pat;
5

6
public:
7
    KMP2(std::string pat) : pat(pat) {
8
        // dp[状态][字符] = 下个状态
9
        dp = std::vector<std::vector<int>>(pat.length(), std::vector<int>(256, 0));
10
        // base case
11
        dp[0][pat[0]] = 1;
12
        // 影子状态 X 初始为 0
13
        int X = 0;
14
        // 构建状态转移图
15
        for (size_t j = 1; j < pat.length(); j++) {
16
            for (size_t c = 0; c < 256; c++)
17
                dp[j][c] = dp[X][c];
18
            dp[j][pat[j]] = j + 1;
19
            // 更新影子状态
20
            X = dp[X][pat[j]];
21
        }
22
    }
23

24
    int search(std::string txt, size_t pos = 0) {
25
        // pat 的初始态为 0
26
        int j = 0;
27
        for (size_t i = pos; i < txt.length(); i++) {
28
            // 计算 pat 的下一个状态
29
            j = dp[j][txt[i]];
30
            // 到达终止态，返回结果
31
            if (j == pat.length()) return i - pat.length() + 1;
32
        }
33
        // 没到达终止态，匹配失败
34
        return -1;
35
    };
36
};
37

38
class KMP {
39
    std::string pattern;
40
    vector<int> next;
41

42
    void buildNext() {
43
        for (int i = 1, j = 0; i < pattern.size(); i++) {
44
            while (j && pattern[i] != pattern[j]) j = next[j - 1];
45
            if (pattern[i] == pattern[j]) j++;
46
            next[i] = j;
47
        }
48
    }
49

50
public:
51
    auto searchAll(std::string txt) {
52
        std::vector<size_t> p;
53
        for (size_t i = 0, j = 0; i < txt.size(); i++) {
54
            while (j && txt[i] != pattern[j]) j = next[j - 1];
55
            if (txt[i] == pattern[j]) j++;
56
            if (j == pattern.size()) {
57
                p.emplace_back(i - pattern.size() + 1);
58
                j = next[j - 1];
59
            }
60
        }
61
        return p;
62
    }
63

64
    size_t search(std::string txt, size_t pos = 0) {
65
        for (size_t i = pos, j = 0; i < txt.size(); i++) {
66
            while (j && txt[i] != pattern[j]) j = next[j - 1];
67
            if (txt[i] == pattern[j]) j++;
68
            if (j == pattern.size()) {
69
                return i - pattern.size() + 1;
70
            }
71
        }
72
        return -1;
73
    }
74

75
    KMP(std::string pattern) : pattern(pattern) {
76
        next.resize(pattern.size() + 1);
77
        buildNext();
78
    }
79
};

Manacher 求回文串#

1
struct Manacher {
2

3
    // 求奇数回文串
4
    std::vector<int> static getOddPalindrome(const std::string &s) {
5
        std::vector<int> d1(s.size());
6
        for (int i = 0, l = 0, r = -1; i < s.size(); i++) {
7
            int k = (i > r) ? 1 : std::min(d1[l + r - i], r - i + 1);
8
            while (0 <= i - k && i + k < s.size() && s[i - k] == s[i + k]) {
9
                k++;
10
            }
11
            d1[i] = k--;
12
            if (i + k > r) {
13
                l = i - k;
14
                r = i + k;
15
            }
16
        }
17
        return d1;
18
    }
19

20
    // 求偶数回文串
21
    std::vector<int> static getEvenPalindrome(const std::string &s) {
22
        std::vector<int> d2(s.size());
23
        for (int i = 0, l = 0, r = -1; i < s.size(); i++) {
24
            int k = (i > r) ? 0 : std::min(d2[l + r - i + 1], r - i + 1);
25
            while (0 <= i - k - 1 && i + k < s.size() &&
26
                    s[i - k - 1] == s[i + k]) {
27
                k++;
28
            }
29
            d2[i] = k--;
30
            if (i + k > r) {
31
                l = i - k - 1;
32
                r = i + k;
33
            }
34
        }
35
        return d2;
36
    }
37
};

字符串哈希(1-based)#

1
template<size_t HashBase = 233>
2
class StringHash {
3
    std::vector<size_t> hash;
4
    std::vector<size_t> hashPow;
5

6
public:
7
    std::string str;
8

9
    explicit StringHash() = default;
10

11
    explicit StringHash(const std::string &str) :
12
            str(str),
13
            hash(std::vector<size_t>(str.size())),
14
            hashPow(std::vector<size_t>(str.size())) {
15
        hashPow[0] = 1;
16
        hash[0] = 0;
17
        for (size_t i = 1; i < str.size(); i++) {
18
            hash[i] = (hash[i - 1] * HashBase + str[i]);
19
            hashPow[i] = hashPow[i - 1] * HashBase;
20
        }
21
    }
22

23
    constexpr size_t getHash(size_t l, size_t r) const {
24
        assert(r >= l);
25
        assert(l > 0);
26
        assert(r < str.size());
27
        return hash[r] - hash[l - 1] * hashPow[r - l + 1];
28
    }
29

30
    int compare(size_t l1, size_t r1, size_t l2, size_t r2) const {
31
        assert(r1 >= l1 && r2 >= l2);
32
        assert(l1 > 0 && l2 > 0);
33
        assert(r1 < str.size() && r2 < str.size());
34
        size_t l = 0, r = std::min(r1 - l1, r2 - l2) + 1;
35
        size_t ans;
36
        while (l <= r) {
37
            size_t mid = (l + r) / 2;
38
            if (getHash(l1, l1 + mid - 1) == getHash(l2, l2 + mid - 1)) {
39
                l = mid + 1;
40
                ans = mid;
41
            } else {
42
                r = mid - 1;
43
            }
44
        }
45
        if (ans == std::min(r1 - l1, r2 - l2) + 1) {
46
            if (r1 - l1 == r2 - l2) {
47
                return 0;
48
            } else if (r1 - l1 > r2 - l2) {
49
                return 1;
50
            } else {
51
                return -1;
52
            }
53
        } else {
54
            return (str[l1 + ans] > str[l2 + ans]) ? 1 : -1;
55
        }
56
    }
57
};

最小表示法#

1
int k = 0, i = 0, j = 1;
2
while (k < n && i < n && j < n) {
3
  if (sec[(i + k) % n] == sec[(j + k) % n]) {
4
    k++;
5
  } else {
6
    sec[(i + k) % n] > sec[(j + k) % n] ? i = i + k + 1 : j = j + k + 1;
7
    if (i == j) i++;
8
    k = 0;
9
  }
10
}
11
i = min(i, j);

后缀数组#

$sa[i]$ 表示将所有后缀排序后第 $i$ 小的后缀的编号
$rank[i]$ 表示后缀 $i$ 的排名
$height[i]$ 第 $i$ 名的后缀与它前一名的后缀的最长公共前缀
$lcp(s[i], s[j]) = \min\{height[i+1...j]\}$

1
class SuffixArray {
2
public:
3
    std::vector<size_t> sa;
4
    std::vector<size_t> rank;
5
    std::vector<size_t> height;
6
    explicit SuffixArray() = default;
7

8
    explicit SuffixArray(const std::string &str) :
9
            sa(std::vector<size_t>(str.size())),
10
            rank(std::vector<size_t>(str.size())),
11
            height(std::vector<size_t>(str.size())) {
12
        StringHash<233> sh = StringHash<233>(str);
13
        for (size_t i = 1; i < str.size(); i++) {
14
            sa[i] = i;
15
        }
16
        std::sort(sa.begin() + 1, sa.end(), [&](size_t a, size_t b) -> bool {
17
            return sh.compare(a, str.size() - 1, b, str.size() - 1) == -1;
18
        });
19
        for (size_t i = 1; i < str.size(); i++) {
20
            rank[sa[i]] = i;
21
        }
22
        for (size_t i = 1, k = 0; i < str.size(); i++) {
23
            if (rank[i] == 1) {
24
                k = 0;
25
            } else {
26
                if (k) {
27
                    k--;
28
                }
29
                while (str[i + k] == str[sa[rank[i] - 1] + k]) {
30
                    k++;
31
                }
32
            }
33
            height[rank[i]] = k;
34
        }
35
    }
36
};

ST表#

1
#ifndef __SPARSE_TABLE_HPP
2
#define __SPARSE_TABLE_HPP
3

4
// SpareTable<ElemType, CompareType> ElemType: 元素类型 CompareType: 比较函数,
5
// 默认为greater<>
6
template <class T = long long, class Cmp = std::greater<T> >
7
struct SparseTable {
8
   private:
9
    std::vector<std::vector<T> > st;
10

11
   public:
12
    explicit SparseTable() = default;
13
    explicit SparseTable(const std::vector<T> &&a) {
14
        st.resize(a.size(), std::vector<T>(32));
15
        for (int i = 0; i < a.size(); i++) {
16
            st[i][0] = a[i];
17
        }
18
        for (int j = 1; 1 << j <= a.size(); j++) {
19
            for (int i = 0; i + (1 << j) - 1 < a.size(); i++) {
20
                st[i][j] = Cmp(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])
21
                               ? st[i][j - 1]
22
                               : st[i + (1 << (j - 1))][j - 1];
23
            }
24
        }
25
    }
26

27
    T get(int l, int r) {
28
        assert(r >= l);
29
        assert(l >= 0);
30
        assert(r < st.size());
31
        int k = std::__lg(r - l + 1);
32
        return Cmp(st[l][k], st[r - (1 << k) + 1][k]) ? st[l][k]
33
                                                      : st[r - (1 << k) + 1][k];
34
    }
35
};
36

37
#endif

AC自动机#

1
template<size_t base = 26>
2
class Automaton {
3
private:
4
    std::array<std::vector<int>, base> tr;
5
    std::vector<int> count;
6
    std::vector<int> fail;
7
    int tot = 0;
8
public:
9
    // MAXSIZE 模式串的总长
10
    Automaton(int maxsize) : count(maxsize), fail(maxsize) {
11
        for (int i = 0; i < base; ++i) tr[i].resize(maxsize);
12
    }
13

14
    void insert(const std::string &s, int id) {
15
        int u = 0;
16
        for (int i = 0; i < s.size(); i++) {
17
            int c = s[i] - 'a';
18
            if (!tr[c][u]) tr[c][u] = ++tot;
19
            u = tr[c][u];
20
        }
21
        count[u] = id;
22
    }
23

24
    void build() {
25
        std::queue<int> q;
26
        for (int i = 0; i < base; i++) if (tr[i][0]) q.push(tr[i][0]);
27
        while (!q.empty()) {
28
            int u = q.front();
29
            q.pop();
30
            for (int i = 0; i < base; i++) {
31
                if (tr[i][u]) {
32
                    fail[tr[i][u]] = tr[i][fail[u]];
33
                    q.push(tr[i][u]);
34
                } else tr[i][u] = tr[i][fail[u]];
35
            }
36
        }
37
    }
38

39
    std::unordered_map<int, int> query(const std::string &t) {
40
        int u = 0;
41
        std::unordered_map<int, int> ans;
42
        for (int i = 0; i < t.size(); i++) {
43
            u = tr[t[i] - 'a'][u];
44
            for (int j = u; j; j = fail[j]) {
45
                if (count[j]) ans[count[j]]++;
46
            }
47
        }
48
        return ans;
49
    }
50
};

树状结构#

Trie树#

1
#ifndef __TRIE_HPP
2
#define __TRIE_HPP
3

4
template<class T = char>
5
class Trie {
6
private:
7
    typedef T element_type;
8

9
    struct TrieNode {
10
        size_t wordCount;
11
        std::map<element_type, std::unique_ptr<TrieNode> > next;
12

13
        TrieNode() : wordCount(0), next(std::map<element_type, std::unique_ptr<TrieNode> >()) {}
14

15
    };
16

17
    std::unique_ptr<TrieNode> _root;
18

19
public:
20

21
    explicit Trie() { _root = std::make_unique<TrieNode>(); }
22

23
    TrieNode* root() { return _root.get(); }
24

25
    void clear() { _root = std::make_unique<TrieNode>(); }
26

27
    TrieNode* insert(const std::basic_string<element_type> &word, TrieNode* pos = nullptr) {
28
        auto location = (pos == nullptr) ? _root.get() : pos;
29
        for (char const &i: word) {
30
            if (location->next[i] == nullptr) {
31
                location->next[i] = std::make_unique<TrieNode>();
32
            }
33
            location = location->next[i].get();
34
        }
35
        location->wordCount++;
36
        return location;
37
    }
38

39
    TrieNode* insert(element_type character, TrieNode* pos = nullptr) {
40
        auto location = (pos == nullptr) ? _root.get() : pos;
41
        if (location->next[character] == nullptr) {
42
            location->next[character] = std::make_unique<TrieNode>();
43
        }
44
        location = location->next[character].get();
45
        location->wordCount++;
46
        return location;
47
    }
48

49
    TrieNode* find(const std::basic_string<element_type> &word, TrieNode* pos = nullptr) {
50
        auto location = (pos == nullptr) ? _root.get() : pos;
51
        for (int i = 0; i < word.length() && location; i++)
52
            location = location->next[word[i]].get();
53
        return location;
54
    }
55

56
    TrieNode* find(element_type character, TrieNode* pos = nullptr) {
57
        auto location = (pos == nullptr) ? _root.get() : pos;
58
        return location->next[character].get();
59
    }
60

61
    size_t count(const std::basic_string<element_type> &word, TrieNode* pos = nullptr) {
62
        auto location = (pos == nullptr) ? _root.get() : pos;
63
        for (int i = 0; i < word.length() && location; i++)
64
            location = location->next[word[i]].get();
65
        return location == nullptr ? 0 : location->wordCount;
66
    }
67

68
    size_t count(element_type character, TrieNode* pos = nullptr) {
69
        auto location = (pos == nullptr) ? _root.get() : pos;
70
        return location->next[character] == nullptr ? 0 : location->next[character]->wordCount;
71
    }
72

73
    TrieNode* erase(const std::basic_string<element_type> &word, TrieNode* pos = nullptr, size_t count = 1) {
74
        auto location = (pos == nullptr) ? _root.get() : pos;
75
        for (int i = 0; i < word.length() && location; i++)
76
            location = location->next[word[i]].get();
77
        if (location == nullptr) return nullptr;
78
        location->wordCount -= min(count, location->wordCount);
79
        return location;
80
    }
81

82
    TrieNode* erase(element_type character, TrieNode* pos = nullptr, size_t count = 1) {
83
        auto location = (pos == nullptr) ? _root.get() : pos;
84
        if (location->next[character] == nullptr) return nullptr;
85
        location->next[character]->wordCount -= min(count, location->next[character]->wordCount);
86
        return location;
87
    }
88

89
};
90

91
#endif

线段树#

1
template<class T = long long, class V = long long>
2
class ISegmentTree {
3
protected:
4
    typedef T element_type;
5
    typedef V value_type;
6

7
    struct node {
8
        value_type value;
9
        element_type add;
10
        element_type change;
11
        bool isChange{false};
12
        size_t id{0};
13
        size_t l{0}, r{0};
14

15
        constexpr bool inRange(int l, int r) {
16
            return this->l >= l && this->r <= r;
17
        }
18

19
        constexpr bool outOfRange(int l, int r) {
20
            return this->l > r || this->r < l;
21
        }
22

23
        constexpr size_t size() { return r - l + 1; }
24
    };
25

26
    constexpr static size_t ls(size_t x) { return 2 * x; }
27

28
    constexpr static size_t rs(size_t x) { return 2 * x + 1; }
29

30
    std::vector<node> tree;
31

32
    // you should modify these functions
33
    virtual value_type assign_value(const std::vector<element_type> &arr,
34
                                    size_t x) = 0;
35

36
    virtual value_type merge_value(value_type x, value_type y) = 0;
37

38
    virtual void add_value(size_t x, element_type add) = 0;
39

40
    virtual void change_value(size_t x, element_type change) = 0;
41

42
    void add_tag(size_t x, element_type add) {
43
        add_value(x, add);
44
        tree[x].add += add;
45
    }
46

47
    void change_tag(size_t x, element_type change) {
48
        change_value(x, change);
49
        tree[x].change = change;
50
        tree[x].isChange = true;
51
        tree[x].add = 0;
52
    }
53

54
    void push_down(size_t x) {
55
        if (tree[x].isChange) {
56
            change_tag(ls(x), tree[x].change);
57
            change_tag(rs(x), tree[x].change);
58
            tree[x].isChange = false;
59
            tree[x].change = 0;
60
        }
61
        if (tree[x].add) {
62
            add_tag(ls(x), tree[x].add);
63
            add_tag(rs(x), tree[x].add);
64
            tree[x].add = 0;
65
        }
66
    }
67

68
    void push_up(size_t x) {
69
        tree[x].value = merge_value(tree[ls(x)].value, tree[rs(x)].value);
70
    }
71

72
    void build(const std::vector<element_type> &arr, size_t x, size_t l,
73
               size_t r) {
74
        tree[x].id = x;
75
        tree[x].l = l, tree[x].r = r;
76
        if (l == r) {
77
            // how to assign value
78
            tree[x].value = assign_value(arr, l);
79
            return;
80
        }
81
        size_t m = (l + r) >> 1;
82
        build(arr, ls(x), l, m);
83
        build(arr, rs(x), m + 1, r);
84
        push_up(x);
85
    }
86

87
    // 区间加
88
    void _add(size_t l, size_t r, T val, size_t x = 1) {
89
        if (tree[x].inRange(l, r)) {
90
            add_tag(x, val);
91
            return;
92
        }
93
        push_down(x);
94
        if (!tree[ls(x)].outOfRange(l, r)) _add(l, r, val, ls(x));
95
        if (!tree[rs(x)].outOfRange(l, r)) _add(l, r, val, rs(x));
96
        push_up(x);
97
    }
98

99
    // 区间修改
100
    void _change(size_t l, size_t r, T val, size_t x = 1) {
101
        if (tree[x].inRange(l, r)) {
102
            change_tag(x, val);
103
            return;
104
        }
105
        push_down(x);
106
        if (!tree[ls(x)].outOfRange(l, r)) _change(l, r, val, ls(x));
107
        if (!tree[rs(x)].outOfRange(l, r)) _change(l, r, val, rs(x));
108
        push_up(x);
109
    }
110

111
    // 区间查询
112
    value_type _query(size_t l, size_t r, size_t x = 1) {
113
        if (tree[x].inRange(l, r)) {
114
            return tree[x].value;
115
        }
116
        push_down(x);
117
        if (tree[ls(x)].outOfRange(l, r)) return _query(l, r, rs(x));
118
        if (tree[rs(x)].outOfRange(l, r)) return _query(l, r, ls(x));
119
        return merge_value(_query(l, r, ls(x)), _query(l, r, rs(x)));
120
    }
121

122
public:
123
    // 区间加
124
    void add(size_t l, size_t r, element_type val) {
125
        assert(l <= r);
126
        _add(l, r, val, 1);
127
    }
128

129
    // 区间修改
130
    void change(size_t l, size_t r, element_type val) {
131
        assert(l <= r);
132
        _change(l, r, val, 1);
133
    }
134

135
    // 区间查询
136
    value_type query(size_t l, size_t r) {
137
        assert(l <= r);
138
        return _query(l, r, 1);
139
    }
140
};
141

142
class SegmentSumTree : public ISegmentTree<> {
143
private:
144
    value_type assign_value(const std::vector<element_type> &arr,
145
                            size_t x) override {
146
        return arr[x];
147
    }
148

149
    value_type merge_value(value_type x, value_type y) override {
150
        return x + y;
151
    }
152

153
    void add_value(size_t x, element_type val) override {
154
        tree[x].value += val * tree[x].size();
155
    }
156

157
    void change_value(size_t x, element_type val) override {
158
        tree[x].value = val * tree[x].size();
159
    }
160

161
public:
162
    explicit SegmentSumTree(const std::vector<element_type> &arr) {
163
        tree.resize(arr.size() * 4 + 1);
164
        build(arr, 1, 1, arr.size() - 1);
165
    }
166
};
167

168
class SegmentMaxTree : public ISegmentTree<> {
169
private:
170
    value_type assign_value(const std::vector<element_type> &arr,
171
                            size_t x) override {
172
        return arr[x];
173
    }
174

175
    value_type merge_value(value_type x, value_type y) override {
176
        return std::max(x, y);
177
    }
178

179
    void add_value(size_t x, element_type val) override { tree[x].value += val; }
180

181
    void change_value(size_t x, element_type val) override {
182
        tree[x].value = val;
183
    }
184

185
public:
186
    explicit SegmentMaxTree(const std::vector<element_type> &arr) {
187
        tree.resize(arr.size() * 4 + 1);
188
        build(arr, 1, 1, arr.size() - 1);
189
    }
190
};
191

192
class SegmentMinTree : public ISegmentTree<> {
193
private:
194
    value_type assign_value(const std::vector<element_type> &arr,
195
                            size_t x) override {
196
        return arr[x];
197
    }
198

199
    value_type merge_value(value_type x, value_type y) override {
200
        return std::min(x, y);
201
    }
202

203
    void add_value(size_t x, element_type val) override { tree[x].value += val; }
204

205
    void change_value(size_t x, element_type val) override {
206
        tree[x].value = val;
207
    }
208

209
public:
210
    explicit SegmentMinTree(const std::vector<element_type> &arr) {
211
        tree.resize(arr.size() * 4 + 1);
212
        build(arr, 1, 1, arr.size() - 1);
213
    }
214
};

可持久化线段树#

$dir[i]$ 保存的第 $i$ 个版本，初始版本为 $dir[0]$

函数接口

value_type assign_value(const std::vector<element_type> &arr， size_t x)：数组元素初始化为线段树的值
value_type merge_value(value_type x, value_type y)：定义值的合并操作

1
namespace pst {
2

3
    using namespace std;
4
    constexpr int MAXN = 1e6 + 10;
5

6
    template<class T, class V>
7
    class IPersistentSegmentTree {
8
    protected:
9
        typedef T element_type;
10
        typedef V value_type;
11

12
        struct node {
13
            size_t ls, rs;
14
            value_type value;
15
        };
16

17
        size_t length;
18
        size_t total = 0;
19
        vector<node> tree;
20

21
        virtual value_type assign_value(const std::vector<element_type> &arr,
22
                                        size_t x) = 0;
23

24
        virtual value_type merge_value(value_type x, value_type y) = 0;
25

26
        void push_up(int node) {
27
            tree[node].value =
28
                    merge_value(tree[tree[node].ls].value, tree[tree[node].rs].value);
29
        }
30

31
        void build(const std::vector<element_type> &arr, size_t &node, size_t l,
32
                   size_t r) {
33
            node = ++total;
34
            if (l == r) {
35
                tree[node].value = assign_value(arr, l);
36
                return;
37
            }
38
            int mid = (l + r) >> 1;
39
            build(arr, tree[node].ls, l, mid);
40
            build(arr, tree[node].rs, mid + 1, r);
41
            push_up(node);
42
        }
43

44
        size_t _update(size_t &node, size_t last, size_t pos, element_type val,
45
                       size_t l, size_t r) {
46
            node = ++total;
47
            tree[node] = tree[last];
48
            if (l == r) {
49
                tree[node].value = val;
50
                return node;
51
            }
52
            int mid = (l + r) >> 1;
53
            if (pos <= mid)
54
                _update(tree[node].ls, tree[last].ls, pos, val, l, mid);
55
            else
56
                _update(tree[node].rs, tree[last].rs, pos, val, mid + 1, r);
57
            push_up(node);
58
            return node;
59
        }
60

61
        value_type _get(size_t node, size_t pos, size_t l, size_t r) {
62
            if (l == r) return tree[node].value;
63
            int mid = (l + r) >> 1;
64
            if (pos <= mid)
65
                return _get(tree[node].ls, pos, l, mid);
66
            else
67
                return _get(tree[node].rs, pos, mid + 1, r);
68
        }
69

70
    public:
71
        // 保存版本信息
72
        vector<size_t> dir;
73

74
        size_t update(size_t &node, size_t last, size_t pos, element_type val) {
75
            return _update(node, last, pos, val, 1, length);
76
        }
77

78
        value_type get(size_t node, size_t pos) {
79
            return _get(node, pos, 1, length);
80
        }
81
    };
82

83
    class PersistentSegmentTree
84
            : public IPersistentSegmentTree<long long, long long> {
85
    private:
86
        value_type assign_value(const std::vector<element_type> &arr, size_t x) {
87
            return arr[x];
88
        }
89

90
        value_type merge_value(value_type x, value_type y) { return x + y; }
91

92
    public:
93
        explicit PersistentSegmentTree(const std::vector<element_type> &arr) {
94
            length = arr.size() - 1;
95
            dir.resize(MAXN);
96
            tree.resize(MAXN << 5);
97
            build(arr, dir[0], 1, length);
98
        }
99
    };
100

101
    class KthMinTree : public IPersistentSegmentTree<int, int> {
102
    private:
103
        value_type assign_value(const std::vector<element_type> &arr, size_t x) {
104
            return arr[x];
105
        }
106

107
        value_type merge_value(value_type x, value_type y) { return x + y; }
108

109
        value_type _kthMin(size_t prev, size_t now, size_t l, size_t r, size_t k) {
110
            if (l == r) return l;
111
            int mid = (l + r) >> 1;
112
            int x = tree[tree[now].ls].value - tree[tree[prev].ls].value;
113
            if (k <= x)
114
                return _kthMin(tree[prev].ls, tree[now].ls, l, mid, k);
115
            else
116
                return _kthMin(tree[prev].rs, tree[now].rs, mid + 1, r, k - x);
117
        }
118

119
        value_type _lessOrEqual(size_t prev, size_t now, size_t l, size_t r, element_type k) {
120
            if (l == r) {
121
                return tree[now].value - tree[prev].value;
122
            }
123
            int mid = (l + r) >> 1;
124
            int ans = 0;
125
            if (k <= mid) {
126
                ans += _lessOrEqual(tree[prev].ls, tree[now].ls, l, mid, k);
127
            } else {
128
                ans += tree[tree[now].ls].value - tree[tree[prev].ls].value;
129
                ans += _lessOrEqual(tree[prev].rs, tree[now].rs, mid + 1, r, k);
130
            }
131
            return ans;
132
        }
133

134
    public:
135

136
        KthMinTree() {
137
            tree.resize(MAXN << 5);
138
            dir.resize(MAXN);
139
        }
140

141
        explicit KthMinTree(const std::vector<element_type> &arr) {
142
            length = arr.size() - 1;
143
            dir.resize(MAXN);
144
            tree.resize(MAXN << 5);
145
            unordered_map<element_type, value_type> cnt;
146
            for (int i = 1; i <= length; i++) {
147
                update(dir[i], dir[i - 1], arr[i], cnt[arr[i]] + 1);
148
                cnt[arr[i]] += 1;
149
            }
150
        }
151

152
        void resize(const std::vector<element_type> &arr) {
153
            total = 0;
154
            length = arr.size() - 1;
155
            unordered_map<element_type, int> cnt;
156
            for (int i = 1; i <= length; i++) {
157
                update(dir[i], dir[i - 1], arr[i], cnt[arr[i]] + 1);
158
                cnt[arr[i]] += 1;
159
            }
160
        }
161

162
        value_type kthMin(size_t l, size_t r, size_t k) {
163
            return _kthMin(dir[l - 1], dir[r], 1, length, k);
164
        }
165

166
        value_type lessOrEqual(size_t l, size_t r, element_type k) {
167
            return _lessOrEqual(dir[l - 1], dir[r], 1, length, k);
168
        }
169
    };
170
}  // namespace pst

可撤销并查集#

1
struct RollingDsu {
2
    std::vector<int> f, siz, tag, st;
3

4
    RollingDsu() = default;
5

6
    explicit RollingDsu(int n) : f(n + 1), siz(n + 1, 1), tag(n + 1, 0) { std::iota(f.begin(), f.end(), 0); }
7

8
    int find(int x) {
9
        while (x != f[x]) x = f[x];
10
        return x;
11
    }
12

13
    constexpr bool same(int x, int y) { return find(x) == find(y); }
14

15
    bool merge(int x, int y) {
16
        x = find(x);
17
        y = find(y);
18
        if (x == y) return false;
19
        if (siz[x] < siz[y]) {
20
            std::swap(x, y);
21
        }
22
        tag[y] -= tag[x];
23
        siz[x] += siz[y];
24
        f[y] = x;
25
        st.emplace_back(y);
26
        return true;
27
    }
28

29
    constexpr int size() {
30
        return st.size();
31
    }
32

33
    int size(int x) {
34
        return siz[find(x)];
35
    }
36

37
    void rollBack(int lastSize = 0) {
38
        assert(lastSize <= st.size());
39
        while (st.size() != lastSize) {
40
            int y = st.back();
41
            int x = f[y];
42
            siz[x] -= siz[y];
43
            tag[y] += tag[x];
44
            f[y] = y;
45
            st.pop_back();
46
        }
47
    }
48

49
    void add(int x, int v) { tag[find(x)] += v; }
50

51
};

时间线段树分治#

1
struct TimeSegTree {
2

3
    RollingDsu dsu;
4

5
    struct node {
6
        int l{0}, r{0};
7
        std::vector<std::pair<int, int> > op;
8
        bool exist{false};
9

10
        constexpr bool inRange(int l, int r) {
11
            return this->l >= l && this->r <= r;
12
        }
13

14
        constexpr bool outOfRange(int l, int r) {
15
            return this->l > r || this->r < l;
16
        }
17

18
        constexpr int length() { return this->r - this->l + 1; }
19

20
        constexpr int size() { return length(); }
21

22
        void add(int u, int v) { op.emplace_back(u, v); }
23

24
        void clear() { op.clear(); }
25
    };
26

27
    std::vector<node> tree;
28

29
    TimeSegTree() = default;
30

31
    // time:时间长度, size:图上节点个数
32
    explicit TimeSegTree(int time, int size) {
33
        dsu = RollingDsu(size);
34
        tree.resize(time * 4 + 5);
35
        build(time, 1, 1, time);
36
    }
37

38
    void build(int time, int u, int l, int r) {
39
        tree[u].l = l;
40
        tree[u].r = r;
41
        if (l == r) return;
42
        int mid = (l + r) >> 1;
43
        build(time, u << 1, l, mid);
44
        build(time, u << 1 | 1, mid + 1, r);
45
    }
46

47
    // 在[l, r]时间段上,连接x, y
48
    void modify(int l, int r, int x, int y, int u = 1) {
49
        if (x == y) return;
50
        assert(l <= r);
51
        if (tree[u].inRange(l, r)) {
52
            tree[u].add(x, y);
53
            return;
54
        }
55
        if (tree[u].outOfRange(l, r)) return;
56
        tree[u].exist = true;
57
        modify(l, r, x, y, u << 1);
58
        modify(l, r, x, y, u << 1 | 1);
59
    }
60

61
    void solve(int u = 1) {
62
        int lastSize = dsu.size();
63
        for (auto &[x, y]: tree[u].op) {
64
            dsu.merge(x, y);
65
        }
66
        if (!tree[u].exist) {
67
            // to do sth at this time
68
            execute(u);
69
            dsu.rollBack(lastSize);
70
            return;
71
        }
72
        solve(u << 1);
73
        solve(u << 1 | 1);
74
        dsu.rollBack(lastSize);
75
    }
76

77
    void execute(int u) {
78
        // how to do
79
    }
80
};

最近公共祖先(LCA)#

1
class LCA {
2
private:
3
    std::vector<std::vector<int> > f;
4
    std::vector<int> depth;
5

6
    void dfs(int root, int father, const std::vector<std::vector<int> > &g) {
7
        f[root][0] = father;
8
        depth[root] = depth[father] + 1;
9
        for (int i = 1; (1 << i) <= depth[root]; i++) {
10
            f[root][i] = f[f[root][i - 1]][i - 1];
11
        }
12
        for (auto const &v: g[root]) {
13
            if (v == father) {
14
                continue;
15
            }
16
            dfs(v, root, g);
17
        }
18
    }
19

20
public:
21

22
    // g: 无向边构成的树, root: 根节点, 默认为1
23
    explicit LCA(int n, const std::vector<std::vector<int>> &g, int root = 1) {
24
        f.resize(n + 1, std::vector<int>(32));
25
        depth.resize(n + 1);
26
        dfs(root, 0, g);
27
    }
28

29
    // 返回u和v的最近公共祖先
30
    int query(int u, int v) {
31
        if (depth[u] < depth[v]) {
32
            std::swap(u, v);
33
        }
34
        while (depth[u] > depth[v]) {
35
            u = f[u][std::__lg(depth[u] - depth[v])];
36
        }
37
        if (u == v) {
38
            return u;
39
        }
40
        for (int i = std::__lg(depth[u]); i >= 0; i--) {
41
            if (f[u][i] != f[v][i]) {
42
                u = f[u][i];
43
                v = f[v][i];
44
            }
45
        }
46
        return f[u][0];
47
    }
48

49
    // 返回u和v之间的距离
50
    int distance(int u, int v) {
51
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
52
    }
53

54
};

图结构#

2-SAT#

1
struct TwoSat {
2
    int n;
3
    std::vector<std::vector<int>> e;
4
    std::vector<bool> ans;
5
    TwoSat(int n) : n(n), e(2 * n), ans(n) {}
6
    void addClause(int u, bool f, int v, bool g) {
7
        e[2 * u + !f].push_back(2 * v + g);
8
        e[2 * v + !g].push_back(2 * u + f);
9
    }
10
    bool satisfiable() {
11
        std::vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);
12
        std::vector<int> stk;
13
        int now = 0, cnt = 0;
14
        std::function<void(int)> tarjan = [&](int u) {
15
            stk.push_back(u);
16
            dfn[u] = low[u] = now++;
17
            for (auto v : e[u]) {
18
                if (dfn[v] == -1) {
19
                    tarjan(v);
20
                    low[u] = std::min(low[u], low[v]);
21
                } else if (id[v] == -1) {
22
                    low[u] = std::min(low[u], dfn[v]);
23
                }
24
            }
25
            if (dfn[u] == low[u]) {
26
                int v;
27
                do {
28
                    v = stk.back();
29
                    stk.pop_back();
30
                    id[v] = cnt;
31
                } while (v != u);
32
                ++cnt;
33
            }
34
        };
35
        for (int i = 0; i < 2 * n; ++i) if (dfn[i] == -1) tarjan(i);
36
        for (int i = 0; i < n; ++i) {
37
            if (id[2 * i] == id[2 * i + 1]) return false;
38
            ans[i] = id[2 * i] > id[2 * i + 1];
39
        }
40
        return true;
41
    }
42
    std::vector<bool> answer() { return ans; }
43
};

Tarjan求强连通分量#

1
const int maxn = 1e5 + 5;
2
stack<int> stk;
3
// instk:是否在栈中  scc:每个点所属的强连通分量编号  cscc:强连通分量的数量 sz:强连通分量的大小
4
int dfsn[maxn], low[maxn], instk[maxn], scc[maxn], dfsncnt = 0, cscc = 0, sz[maxn];
5
vector<vector<int>> e(maxn);
6
void tarjan(int p) {
7
    low[p] = dfsn[p] = ++dfsncnt;
8
    instk[p] = 1;
9
    stk.push(p);
10
    for (auto q: e[p]) {
11
        if (!dfsn[q]) {
12
            tarjan(q);
13
            low[p] = min(low[p], low[q]);
14
        } else if (instk[q]) {
15
            low[p] = min(low[p], dfsn[q]);
16
        }
17
    }
18
    if (low[p] == dfsn[p]) {
19
        int top;
20
        cscc++;
21
        do {
22
            top = stk.top();
23
            stk.pop();
24
            instk[top] = 0;
25
            scc[top] = cscc;
26
            sz[cscc]++;
27
        } while (top != p);
28
    }
29
}
30

31
for (int i = 1; i <= n; i++) {
32
    if (!dfsn[i]) {
33
        tarjan(i);
34
    }
35
}

Tarjan求割点#

1
const int N = 1e5 + 5;
2
vector<int> edge[N];
3
int dfn[N], root[N];
4
int ct;
5
vector<int> cut_points;
6

7
void tarjan(int u, bool isroot)
8
{
9
    int tot = 0;
10
    root[u] = dfn[u] = ++ct;
11
    for (auto v : edge[u])
12
    {
13
        if (!dfn[v])
14
        {
15
            tarjan(v, 0);
16
            root[u] = min(root[u], root[v]);
17
            tot += root[v] >= dfn[u];
18
        }
19
        else
20
            root[u] = min(root[u], dfn[v]);
21
    }
22
    if ((isroot && tot >= 2) || (!isroot && tot >= 1))
23
        cut_points.emplace_back(u);
24
}
25

26
tarjan(1, 1);

Tarjan求割边#

1
const int N = 1e5 + 5;
2
vector<int> edge[N];
3
int dfn[N], root[N], fa[N], ct;
4
struct node
5
{
6
    int u, v;
7
};
8
vector<node> cut_edge;
9
void tarjan(int u)
10
{
11
    int tot = 0;
12
    root[u] = dfn[u] = ++ct;
13
    for (auto v : edge[u])
14
    {
15
        if (!dfn[v])
16
        {
17
            fa[v] = u;
18
            tarjan(v);
19
            root[u] = min(root[u], root[v]);
20
            if (root[v] > dfn[u])
21
                cut_edge.emplace_back(node{u, v});
22
        }
23
        else if (v != fa[u])
24
            root[u] = min(root[u], dfn[v]);
25
    }
26
}
27
tarjan(1);

费用流#

1
#include<bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
struct MCFGraph {
5
    struct Edge {
6
        int v, c, f;
7
        Edge(int v, int c, int f) : v(v), c(c), f(f) {}
8
    };
9
    const int n;
10
    vector<Edge> e;
11
    vector<vector<int>> g;
12
    vector<i64> h, dis;
13
    vector<int> pre;
14
    bool dijkstra(int s, int t) {
15
        dis.assign(n, numeric_limits<i64>::max());
16
        pre.assign(n, -1);
17
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> que;
18
        dis[s] = 0;
19
        que.emplace(0, s);
20
        while (!que.empty()) {
21
            i64 d = que.top().first;
22
            int u = que.top().second;
23
            que.pop();
24
            if (dis[u] < d) continue;
25
            for (int i : g[u]) {
26
                int v = e[i].v;
27
                int c = e[i].c;
28
                int f = e[i].f;
29
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
30
                    dis[v] = d + h[u] - h[v] + f;
31
                    pre[v] = i;
32
                    que.emplace(dis[v], v);
33
                }
34
            }
35
        }
36
        return dis[t] != numeric_limits<i64>::max();
37
    }
38
    MCFGraph(int n) : n(n), g(n) {}
39
    void addEdge(int u, int v, int c, int f) {//c是流量,f是费用.
40
        if (f < 0) {
41
            g[u].push_back(e.size());
42
            e.emplace_back(v, 0, f);
43
            g[v].push_back(e.size());
44
            e.emplace_back(u, c, -f);
45
        } else {
46
            g[u].push_back(e.size());
47
            e.emplace_back(v, c, f);
48
            g[v].push_back(e.size());
49
            e.emplace_back(u, 0, -f);
50
        }
51
    }
52
    pair<int, i64> flow(int s, int t) {
53
        int flow = 0;
54
        i64 cost = 0;
55
        h.assign(n, 0);
56
        while (dijkstra(s, t)) {
57
            for (int i = 0; i < n; ++i) h[i] += dis[i];//更新势能
58
            int aug = numeric_limits<int>::max();//流量
59
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = min(aug, e[pre[i]].c);
60
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
61
                e[pre[i]].c -= aug;
62
                e[pre[i] ^ 1].c += aug;
63
            }
64
            flow += aug;
65
            cost += i64(aug) * h[t];
66
        }
67
        return make_pair(flow, cost);
68
    }
69
};

杂项#

MODINT#

1
#if __cplusplus < 201703L
2
#define constexpr inline
3
#endif
4

5
template<long long T = 998244353>
6
struct ModInt {
7
    long long x;
8

9
    constexpr ModInt(const long long x = 0) : x(x % T) {
10
    }
11

12
    [[nodiscard]] constexpr long long val() const { return x; }
13

14
    constexpr ModInt &operator=(const ModInt &a) {
15
        x = a.x;
16
        return *this;
17
    }
18

19
    constexpr ModInt &operator=(const long long y) {
20
        x = y % T;
21
        return *this;
22
    }
23

24
    constexpr ModInt operator+(const ModInt &a) const {
25
        int x0 = x + a.x;
26
        return ModInt(x0 < T ? x0 : x0 - T);
27
    }
28

29
    constexpr ModInt operator-(const ModInt &a) const {
30
        int x0 = x - a.x;
31
        return ModInt(x0 < 0 ? x0 + T : x0);
32
    }
33

34
    constexpr ModInt operator*(const ModInt &a) const {
35
        return ModInt(1LL * x * a.x % T);
36
    }
37

38
    constexpr ModInt operator/(const ModInt &a) const {
39
        return *this * a.inv();
40
    }
41

42
    constexpr bool operator==(const ModInt &a) const { return x == a.x; };
43

44
    constexpr bool operator!=(const ModInt &a) const { return x != a.x; };
45

46
    constexpr void operator+=(const ModInt &a) {
47
        x += a.x;
48
        if (x >= T) x -= T;
49
    }
50

51
    constexpr void operator-=(const ModInt &a) {
52
        x -= a.x;
53
        if (x < 0) x += T;
54
    }
55

56
    constexpr void operator*=(const ModInt &a) { x = 1LL * x * a.x % T; }
57

58
    constexpr void operator/=(const ModInt &a) { *this = *this / a; }
59

60
    constexpr friend ModInt operator+(int y, const ModInt &a) {
61
        int x0 = y + a.x;
62
        return ModInt(x0 < T ? x0 : x0 - T);
63
    }
64

65
    constexpr friend ModInt operator-(int y, const ModInt &a) {
66
        int x0 = y - a.x;
67
        return ModInt(x0 < 0 ? x0 + T : x0);
68
    }
69

70
    constexpr friend ModInt operator*(int y, const ModInt &a) {
71
        return ModInt(1LL * y * a.x % T);
72
    }
73

74
    constexpr friend ModInt operator/(int y, const ModInt &a) {
75
        return ModInt(y) / a;
76
    }
77

78
    constexpr friend std::ostream &operator<<(std::ostream &os, const ModInt &a) {
79
        return os << a.x;
80
    }
81

82
    constexpr friend std::istream &operator>>(std::istream &is, ModInt &t) {
83
        return is >> t.x;
84
    }
85

86
    constexpr ModInt pow(int n) const {
87
        ModInt res(1), mul(x);
88
        while (n) {
89
            if (n & 1) res *= mul;
90
            mul *= mul;
91
            n >>= 1;
92
        }
93
        return res;
94
    }
95

96
    constexpr ModInt operator^(const int n) const { return pow(n); }
97

98
    constexpr ModInt inv() const {
99
        int a = x, b = T, u = 1, v = 0;
100
        while (b) {
101
            int t = a / b;
102
            a -= t * b;
103
            std::swap(a, b);
104
            u -= t * v;
105
            std::swap(u, v);
106
        }
107
        if (u < 0) u += T;
108
        return u;
109
    }
110

111
    constexpr ModInt operator~() const { return inv(); }
112
};

Random#

1
std::mt19937 sd(std::random_device{}());
2
std::uniform_int_distribution<unsigned> rd1(min,max);
3
std::uniform_real_distribution<double> rd2(min,max); //均匀分布
4
std::normal_distribution<double> rd3(min,max); //正态分布

pbds#

1
#include <ext/pb_ds/assoc_container.hpp>
2
#include <ext/pb_ds/hash_policy.hpp>
3
#include <ext/pb_ds/priority_queue.hpp>
4
#include <ext/pb_ds/tree_policy.hpp>
5
#include <ext/pb_ds/trie_policy.hpp>
6
#include <ext/rope>
7
using namespace __gnu_pbds;
8
using namespace __gnu_cxx;
9
template <typename T, class P = std::less<T>>
10
using ordered_set =
11
    tree<T, null_type, P, rb_tree_tag, tree_order_statistics_node_update>;
12
/*
13
定义一颗红黑树
14
int 关键字类型
15
null_type无映射(低版本g++为null_mapped_type)
16
less<int>从小到大排序
17
rb_tree_tag 红黑树（splay_tree_tag）
18
tree_order_statistics_node_update结点更新
19
插入t.insert();
20
删除t.erase();
21
求k在树中是第几大:t.order_of_key();
22
求树中的第k大:t.find_by_order();
23
前驱:t.lower_bound();
24
后继t.upper_bound();
25
a.join(b)b并入a 前提是两棵树的key的取值范围不相交
26
a.split(v,b)key小于等于v的元素属于a，其余的属于b
27
T.lower_bound(x)   >=x的min的迭代器
28
T.upper_bound((x)  >x的min的迭代器
29
T.find_by_order(k) 第k个数比它小的数
30
*/
31

32
template <typename T, class P = std::less<T>>
33
using heap = __gnu_pbds::priority_queue<T, P, pairing_heap_tag>;
34
/*
35
push()  //会返回一个迭代器
36
top()  //同 stl
37
size()  //同 stl
38
empty() //同 stl
39
clear()  //同 stl
40
pop()  //同 stl
41
join(priority_queue &other)  //合并两个堆,other会被清空
42
split(Pred prd,priority_queue &other)  //分离出两个堆
43
modify(point_iterator it,const key)  //修改一个节点的值
44
erase(point_iterator it) //删除一个节点
45
*/
46

47
template <typename T, typename P = std::less<T>>
48
using cmap = cc_hash_table<T, P>; // 拉链法(内存小)
49
template <typename T, typename P = std::less<T>>
50
using gmap = gp_hash_table<T, P>; // 查探法(速度快)
51

52
using trie =
53
    __gnu_pbds::trie<std::string, null_type, trie_string_access_traits<>,
54
                     pat_trie_tag, trie_prefix_search_node_update>;
55

56
/*
57
tr.insert(string s); //插入s
58
tr.erase(string s); //删除s
59
tr.join(trie b); //将b并入tr
60
pair//pair的使用如下：
61
pair<tr::iterator,tr::iterator> range=base.prefix_range(string x);
62
for(tr::iterator it=range.first;it!=range.second;it++)
63
        cout<<*it<<' '<<endl;
64
//pair中第一个是起始迭代器，第二个是终止迭代器，遍历过去就可以找到所有字符串了。
65
*/
66

67
rope<int> *r[100000];
68

69
/*
70
push_back(type x): 在末尾插入x
71
insert(int pos, type *s,int n):
72
将字符串s的前n位插入rope的下标pos处，如没有参数n则将字符串s的所有位都插入rope的下标pos处
73
append(type *s,int pos,int n):
74
把字符串s中从下标pos开始的n个字符连接到rope的结尾，如没有参数n则把字符串s中下标pos后的所有字符连接到rope的结尾，如没有参数pos则把整个字符串s连接到rope的结尾
75
erase(int pos, int x): 在pos处删除x个元素
76
length(): 返回数组长度
77
size(): 返回数组长度
78
replace(pos, type *s):
79
从rope的下标pos开始替换成字符串x，x的长度为从pos开始替换的位数，如果pos后的位数不够就补足
80
substr(int pos, int len): 从pos处开始提取len个元素
81
copy(int pos, int x, type *s):
82
从rope的下标pos开始的len个字符用s代替，如果pos后的位数不够就补足
83
at(int x):
84
访问第x个元素，同rp[x]
85
拷贝历史版本: r[i] = new rope(*r[i - 1]);
86
*/