Trie三战含板子
title: Trie三战含板子
categories:
- ICPC
tags:
- null
abbrlink: 756ed5
date: 2023-05-25 00:00:00
Trie三战含板子
字典:一个字符串的集合称为字典。
字典串:在字典里的串称为字典串。
在处理字符串的时候,常会遇到这样的简单问题:给出一个字典,然后回答大量询问:输入一个字符串,判断它是否在字典中。
Trie 是一棵有根树,每个点至多有 |Σ| 个后继边,每条边上有一个字符。
每个点表示一个前缀:从跟到这个点的边上的字符顺次连接形成的字符串。
每个点还有一个终止标记:是否这个点代表的字符串是一个字典串。可以支持向 Trie 插入新字典串,删除字典串,查询某字符串是否是字典串,以及一些稍微复杂的查询。作为一个数据结构,它理所应当的还可以进行持久化。
这是一份处理小写字母字符串
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字典树
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]$区间内的某一个前缀异或和,异或起来的最大值
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} $的前缀,即路径上不能有其他串的的终止节点。因为无论怎么定于字典序,前缀会比它的字典序小
bool iscycle_direct(vector<vector<int>> &e, vector<int> °) {
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个整数$A_1,A_2 \dots A_N$中选出两个进行xor运算,得到的结果最大是多少?
- 由于相同宽度的两个二进制数字的大小关系等价于字典序关系。
从高到低考虑 x 的每一个二进制位 bit:如果 y 的这一位也是 bit,则异或结果的这一位为 0;如果 y 的这一位是 !bit,则异或结果的这一位为1。将所有数字插入到 01Trie 中,枚举 x,在 01Trie 上寻找 y:从根出发,如果有 !bit 边,则走 !bit 边,否则只能走 bit 边。
实现的时候采用边查询边插入的办法
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。定义区间异或和为区间所有数字异或起来的结果。求最大区间异或和。多个最大区间,取右端点小的。多个最大区间且存在右端点相等的,取区间长度最小的。
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博客
#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);
}