Trie三战含板子

字典：一个字符串的集合称为字典。

字典串：在字典里的串称为字典串。

  • 在处理字符串的时候，常会遇到这样的简单问题：给出一个字典，然后回答大量询问：输入一个字符串，判断它是否在字典中。

  • Trie 是一棵有根树，每个点至多有 |Σ| 个后继边，每条边上有一个字符。

  • 每个点表示一个前缀：从跟到这个点的边上的字符顺次连接形成的字符串。

  • 每个点还有一个终止标记：是否这个点代表的字符串是一个字典串。可以支持向 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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    int id(char c) {//给出现的字符集编码，记得改offset部分
        if (c >= 'a' && c <= 'z')
            return c - 'a';
        else if (c >= 'A' && c <= 'Z')
            return c - 'A' + 26;
        else
            return c - '0' + 52;
    }
    struct Trie {//正常字母字符串trie
        static constexpr int ALPHA = 26;
        struct Node {
            int cnt;
            bool ended;
            array<int, ALPHA> next;
            Node() : cnt{0}, ended{false}, next{} {}
        };
        vector<Node> t;
        Trie() { init(); }
        void init() {
            t.assign(2, {});
        }
        int newNode() {
            t.emplace_back();
            return t.size() - 1;
        }
        int add(const vector<int> &a) {
            int p = 1;
            for (auto x : a) {
                if (t[p].next[x] == 0) {
                    t[p].next[x] = newNode();
                }
                p = t[p].next[x];
                t[p].cnt++;
            }
            t[p].ended = true;
            return p;
        }
        int add(const string &s, char offset = 'a') {
            vector<int> a;
            for (auto c : s) {
                a.push_back(c - offset);
            }
            return add(a);
        }
        int cnt(int p) { return t[p].cnt; }
        bool ended(int p) { return t[p].ended; }
        int next(int p, int x) { return t[p].next[x]; }
        int next(int p, char c, char offset = 'a') { return next(p, c - offset); }
        int size() { return t.size(); }
    };
    Trie tr;

    01字典树

    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
    struct Trie_bin {//保证第一次一定是先插入，查询不能先做
        static constexpr int ALPHA = 2;
        struct Node {
            array<int, ALPHA> next;
            Node() : next{} {}
        };
        vector<Node> t;
        Trie_bin() { init(); }
        void init() {
            t.assign(2, {});

        }
        int newNode() {
            t.emplace_back();
            return t.size() - 1;
        }
        int add(const vector<int> &a) {
            int p = 1;
            for (auto x : a) {
                if (t[p].next[x] == 0) {
                    t[p].next[x] = newNode();
                }
                p = t[p].next[x];
            }

            return p;
        }
        // 数字转01串vector
        int add(int x, int width = 31) {//x必须小于2的width次方
            vector<int> a;
            for (int i = width - 1; i >= 0; i--) {
                a.push_back((x >> i) & 1);
            }
            return add(a);
        }
        int next(int p, int x) { return t[p].next[x]; }
        int size() { return t.size(); }
    };

可持久化字典树:每次查询s[n]^x和[l,r][l,r]区间内的某一个前缀异或和，异或起来的最大值

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
89
struct Trie_per {
    static constexpr int SIZE = 2;
    static constexpr int width = 24;  // 值域小于2的width次方
    struct Node {
        int cnt;
        array<int, SIZE> next;
        Node() : cnt{0}, next{} {}
    };
    vector<Node> t;
    vector<int> ver;
    Trie_per() { init(); }
    void init() {
        t.assign(2, {});
        ver.resize(1);
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int add(int pre, const vector<int> &a) {
        int cur = newNode();
        int p = pre, q = cur;
        t[q] = t[p];
        for (auto x : a) {
            t[q].next[x] = newNode();
            p = next(p, x);
            q = next(q, x);
            t[q] = t[p];
            t[q].cnt++;
        }
        return cur;
    }
    int add(int pre, int x) {  // 转成01vector
        vector<int> a;
        for (int i = width - 1; i >= 0; i--) {
            a.push_back((x >> i) & 1);
        }
        return add(pre, a);
    }
    void add(int x) {  // 外部接口
        int pos = add(ver.back(), x);
        ver.push_back(pos);
    }
    // 查询x在版本(l,r]中和哪个数异或最大
    int querymx(int l, int r, int x) {  // 传l-1进来
        int res = 0;
        int p = ver[l], q = ver[r];
        for (int i = width - 1; i >= 0; i--) {
            int u = (x >> i) & 1;
            int nxp = t[p].next[u ^ 1], nxq = t[q].next[u ^ 1];
            if (t[nxq].cnt - t[nxp].cnt > 0) {
                res |= 1 << i;
                u ^= 1;
            }
            p = t[p].next[u];
            q = t[q].next[u];
        }
        return res;
    }
    int size() { return t.size(); }
    int cnt(int p) { return t[p].cnt; }
    int next(int p, int x) { return t[p].next[x]; }
};
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i];
    Trie_per tr;
    tr.add(0);
    for (int i = 1; i <= n; i++) tr.add(sum[i]);
    for (int i = 1; i <= m; i++) {
        string op;
        cin >> op;
        if (op == "A") {
            int x;
            cin >> x;
            sum.push_back(sum.back() ^ x);
            tr.add(sum.back());
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            int res = tr.querymx(l - 1, r, sum.back() ^ x);
            cout << res << endl;
        }
    }
}

1.给定 n 个不同的字符串 你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串。(n <= 30000 , 字符串总长<= 300000 )

Sol:先构建出字典树，然后逐个字符串判定可行性。

考虑 $S_{i} 在字典树上的每个节点，如果有多于一个后继边，则使在字典树上的每个节点，如果有多于一个后继边，则使S_{i} $当前将要走的边上的字母必须小于其他字母，我们可以对偏序关系建有向图表示。这等价于判定 26 个点的有向图上是否有环（拓扑排序）。

  • 额外需要注意不能有任何其他串等于 $S_{i} $的前缀，即路径上不能有其他串的的终止节点。因为无论怎么定于字典序，前缀会比它的字典序小
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
bool iscycle_direct(vector<vector<int>> &e, vector<int> &deg) {
    queue<int> q;
    int n = deg.size() - 1;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
            q.push(i);
    while (q.size()) {
        auto u = q.front();
        q.pop();
        for (auto v : e[u]) {
            deg[v]--;
            if (deg[v] == 0)
                q.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
        if (deg[i]) {
            return true;
        }
    return false;
}
void solve() {
    int n;
    cin >> n;
    vector<string> s(n);

    auto check = [&](int id) {
        deb(s[id], "--------------------------");
        int p = 1;
        vector<vector<int>> e(27);
        vector<int> deg(27);
        for (auto ch : s[id]) {
            if (tr.ended(p)) {//除了终点其他点都不能是end
                return false;
            }
            for (int i = 0; i < 26; i++) {
                if (ch - 'a' == i || tr.next(p, i) == 0)
                    continue;
                e[(ch - 'a' + 1)].push_back(i + 1);//下标偏移1，小的指向大的
                deg[i + 1]++;
            }
            p = tr.next(p, ch);
        }
        bool flag = iscycle_direct(e, deg);
        if (flag)
            return false;
        return true;
    };
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        tr.add(s[i]);
    }
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (check(i))
            ans.push_back(i);
    }
    cout << ans.size() << endl;
    for (auto x : ans) cout << s[x] << endl;
}

2.在给定的N个整数A1,A2…ANA_1,A_2 \dots A_N中选出两个进行xor运算，得到的结果最大是多少？

  • 由于相同宽度的两个二进制数字的大小关系等价于字典序关系。

从高到低考虑 x 的每一个二进制位 bit：如果 y 的这一位也是 bit，则异或结果的这一位为 0；如果 y 的这一位是 !bit，则异或结果的这一位为1。将所有数字插入到 01Trie 中，枚举 x，在 01Trie 上寻找 y：从根出发，如果有 !bit 边，则走 !bit 边，否则只能走 bit 边。

实现的时候采用边查询边插入的办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Trie_bin tr;
void solve() {
    int n;cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (i == 1)tr.add(x);
        else {
            int p = 1;int res = 0;
            for (int i = 30; i >= 0; i--) {
                int u = (x >> i) & 1;
                if (tr.next(p, u ^ 1)) {p = tr.next(p, u ^ 1);res |= 1 << i;}
                else {p = tr.next(p, u);}
            }
            ans = max(ans, res);tr.add(x);
        }
    }
    cout << ans << endl;
}

3.给出一个正整数数组 A，长度不超过 100*,* 000。定义区间异或和为区间所有数字异或起来的结果。求最大区间异或和。多个最大区间，取右端点小的。多个最大区间且存在右端点相等的，取区间长度最小的。

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
Trie_bin tr;
void solve() {
    map<int, int> mp;
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) a[i] ^= a[i - 1];
    deb(a);
    array<int, 3> ans = {-1, -1, -1};
    deb(ans);
    tr.add(0, 21);//先插a[0]进去，重要！！！！！
    for (int i = 1; i <= n; i++) {
        int p = 1;
        int x = a[i];
        int res = 0;
        for (int j = 20; j >= 0; j--) {
            int u = (x >> j) & 1;
            if (tr.next(p, u ^ 1)) {
                deb(j, p, u ^ 1);
                p = tr.next(p, u ^ 1);
                res |= 1 << j;
            } else
                p = tr.next(p, u);
        }
        if (ans[0] < res) {
            ans[0] = res;
            ans[2] = i;
            ans[1] = mp[res ^ a[i]];
        }
            tr.add(a[i], 21);
        mp[a[i]] = i;
    }
    ans[1] += 1;// 考虑前缀和左端点偏移
    for (auto x : ans) cout << x << " ";
}

BZOJ - 2741 分块维护最大连续异或和 - Caturra - 博客园 (cnblogs.com)

BZOJ - 4260 01字典树+前后缀 - Caturra - 博客园 (cnblogs.com)

NKOJ8493 最大连续异或和 - Thermalrays - 博客园 (cnblogs.com)

Maximum Xor Secondary - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

牛客OI月赛12-提高组 C. 区间异或和异或区间最大值异或区间最小值（分治+字典树）_区间异或最值-CSDN博客

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
#define fo(i, x, y) for (int i = x, B = y; i <= B; i++)
#define ff(i, x, y) for (int i = x, B = y; i < B; i++)
#define fd(i, x, y) for (int i = x, B = y; i >= B; i--)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 1e5 + 5;

int n, a[N], ans;

int son[N * 31][2], cnt[N * 31], tot, rt;

void cl() {
    fo(i, 1, tot) son[i][0] = son[i][1] = cnt[i] = 0;
    tot = rt = 1;
}

const int w = 29;

void add(int v) {
    int x = rt;
    fd(i, w, 0) {
        int c = v >> i & 1;
        if (!son[x][c])
            son[x][c] = ++tot;
        x = son[x][c];
        cnt[x]++;
    }
}

void erase(int v) {
    int x = rt;
    fd(i, w, 0) {
        int c = v >> i & 1;
        x = son[x][c];
        cnt[x]--;
    }
}  // 可删除字典树的实现

void query(int v) {
    int s = 0, x = rt;
    fd(i, w, 0) {
        int c = v >> i & 1;
        if (cnt[son[x][!c]])
            x = son[x][!c], s |= (1 << i);
        else
            x = son[x][c];
        if ((ans >> i) > (s >> i))
            return;
    }
    ans = s;
}

const int inf = 2e9;

int sx[N];

int b[N];

int ky;

#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

void dg(int x, int y) {
    if (x == y) {
        ans = max(ans, a[x]);
        return;
    }
    int m = x + y >> 1;
    dg(x, m);
    dg(m + 1, y);

    sx[m] = 0;
    fo(i, m + 1, y) sx[i] = sx[i - 1] ^ a[i];
    b[m] = inf;
    fo(i, m + 1, y) b[i] = min(b[i - 1], a[i]);

    sx[m] = a[m];
    fd(i, m - 1, x) sx[i] = sx[i + 1] ^ a[i];

    int mi = inf, mx = 0, l = m + 1, r = m;
    cl();
    // 左边最大值，最小值
    fd(i, m, x) {  // 从mid开始向左拓展，
        mi = min(mi, a[i]);
        // 更新最大值最小值
        mx = max(mx, a[i]);
        while (r < y && a[r + 1] <= mx && a[r + 1] >= mi) r++, add(sx[r]);  // 维护右边边界
        query(sx[i] ^ mi ^ mx);
    }  // 双指针维护钦定的最大值，最小值在左边还是右边
    // 考虑为什么需要钦定？
    //  因为我们采用分治枚举子区间的手法，
    //  我们需要知道当前区间的最大值和最小值，
    //  这样才能确定左右指针怎么移动才能满足这个最大值最小值
    // ，拓展左边，更新最大最小值，按照我们当前分类讨论的四种情况，维护右边指针的移动，
    // 移动的同时不断加入或者删除贡献，贡献的具体形式时是更具钦定的最大值最小值所在位置决定的

    cl();
    // 左边最大值，右边最小值，维护右边前缀最小值数组b
    mi = inf, mx = 0, l = m + 1, r = m;
    fd(i, m, x) {
        mi = min(mi, a[i]);
        mx = max(mx, a[i]);                                      // 最大值单调变大
        while (r < y && a[r + 1] <= mx) r++, add(b[r] ^ sx[r]);  // r指针只能向右，因为之前的数都比之前的最大值还小
        while (l <= r && b[l] >= mi) erase(b[l] ^ sx[l]), l++;
        query(mx ^ sx[i]);  // add的右边的异或和以及最小，拼接的时mid的后缀和以及最大值
    }
}

int main() {
    //	freopen("c.in", "r", stdin);
    //	freopen("c.out", "w", stdout);
    scanf("%d", &n);
    fo(i, 1, n) scanf("%d", &a[i]);
    dg(1, n);
    reverse(a + 1, a + n + 1);  // 倒序再做一遍，少讨论两种情况
    ky = 1;
    dg(1, n);
    pp("%d\n", ans);
}

https://ac.nowcoder.com/discuss/287870?tdsourcetag=s_pctim_aiomsg#:~:text=【题解】牛客