P2580 于是他错误的点名开始了

#include <bits/stdc++.h>
using namespace std;
const int MAXNODE = 50 * 10000; // 长度*单词数：最坏节点个数

string s;
int n, m, son[MAXNODE + 5][26], tag[MAXNODE + 5], tot = 1;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> s;
        int u = 1; // 1号节点: ''
        for (int j = 0; j < s.length(); j++)
        {
            int c = s[j] - 'a';
            if (!son[u][c])
                son[u][c] = ++tot;
            u = son[u][c];
        }
        tag[u] = 1;
    }
    cin >> m;
    while (m--)
    {
        cin >> s;
        int u = 1;
        for (int j = 0; j < s.length(); ++j)
        {
            int c = s[j] - 'a';
            u = son[u][c];
            if (!u)
                break;
        }
        if (tag[u] == 1)
        {
            tag[u] = 2;
            cout << "OK\n";
        }
        else if (tag[u] == 2)
            cout << "REPEAT\n";
        else
            cout << "WROMAXNODEG\n";
    }

    return 0;
}

P2536 [AHOI2005] 病毒检测

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123456;
int n, ans;
string s;
string p;
queue<int> qt; // 在 tr 上走到的位置
queue<int> qp; // 在 p 上走到的位置

int c2i[256];
bitset<1005> vis[MAXN];

int son[MAXN][5], tot; // 根节点为 0
int tag[MAXN];
void insert(string &s)
{
    int u = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (!son[u][c2i[s[i]]])
            son[u][c2i[s[i]]] = ++tot;
        u = son[u][c2i[s[i]]];
    }
    tag[u]++;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    c2i['A'] = 0, c2i['C'] = 1, c2i['T'] = 2, c2i['G'] = 3;
    cin >> p;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        insert(s);
    }
    qt.push(0);
    qp.push(0);
    while (!qt.empty())
    {
        int nowT = qt.front();
        qt.pop();
        int nowP = qp.front();
        qp.pop();
        if (nowP == p.length())
        {
            ans += tag[nowT];
            tag[nowT] = 0;
            continue;
        }
        if (p[nowP] == 'A' || p[nowP] == 'C' || p[nowP] == 'T' || p[nowP] == 'G')
        {
            if (son[nowT][c2i[p[nowP]]] && !vis[son[nowT][c2i[p[nowP]]]][nowP + 1])
            {
                vis[son[nowT][c2i[p[nowP]]]][nowP + 1] = true;
                qt.push(son[nowT][c2i[p[nowP]]]);
                qp.push(nowP + 1);
            }
        }
        else if (p[nowP] == '?')
        {
            for (int i = 0; i < 4; i++)
                if (son[nowT][i] && !vis[son[nowT][i]][nowP + 1])
                {
                    vis[son[nowT][i]][nowP + 1] = true;
                    qt.push(son[nowT][i]);
                    qp.push(nowP + 1);
                }
        }
        else if (p[nowP] == '*')
        {
            for (int i = 0; i < 4; i++)
                if (son[nowT][i] && !vis[son[nowT][i]][nowP])
                {
                    vis[son[nowT][i]][nowP] = true;
                    qt.push(son[nowT][i]);
                    qp.push(nowP);
                }
            if (p[nowP] == '*' && !vis[nowT][nowP + 1])
            {
                vis[nowT][nowP + 1] = true;
                qt.push(nowT);
                qp.push(nowP + 1);
            }
        }
    }
    cout << n - ans << "\n";
    return 0;
}

P4735 最大异或和

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 600000;
const int MAXNODE = 600000 * 33;
int n, q, a[MAXN + 5], s[MAXN + 5], l, r, x;
char op;
int tot, rt[MAXN + 5], son[MAXNODE + 5][2], tag[MAXNODE];
// 基于编号为 pre 的字典树，新加了 val 这个数，建立一个编号为 now 的字典树。
void insert(int now, int pre, int val)
{
    for (int i = 30; i >= 0; i--)
    {
        tag[now] = tag[pre] + 1; // 在原版本的基础上更新
        int j = ((val >> i) & 1);
        if (j == 0)
        {
            son[now][0] = ++tot;
            son[now][1] = son[pre][1];
            now = son[now][0];
            pre = son[pre][0];
        }
        else
        {
            son[now][0] = son[pre][0];
            son[now][1] = ++tot;
            now = son[now][1];
            pre = son[pre][1];
        }
    }
    tag[now] = tag[pre] + 1;
}

// 编号为 now 的树与编号为 pre 的树，作差后得到的新树上查找与 val 的最大异或和
int query(int now, int pre, int val)
{
    int res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int j = ((val >> i) & 1);
        // 尽量向不同的地方跳
        if (tag[son[now][1 - j]] - tag[son[pre][1 - j]])
        {
            res += (1 << i);
            now = son[now][1 - j];
            pre = son[pre][1 - j];
        }
        else
        {
            now = son[now][j];
            pre = son[pre][j];
        }
    }
    return res;
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        rt[i] = ++tot;
        insert(rt[i], rt[i - 1], s[i]);
    }
    while (q--)
    {
        cin >> op;
        if (op == 'A')
        {
            n++;
            cin >> a[n];
            s[n] = s[n - 1] ^ a[n];
            rt[n] = ++tot;
            insert(rt[n], rt[n - 1], s[n]);
        }
        if (op == 'Q')
        {
            cin >> l >> r >> x;
            l--;
            r--;
            if (l == 0)
                cout << max(s[n] ^ x,
                            query(rt[r], rt[max(l - 1, 0)], s[n] ^ x))
                     << endl;
            else
                cout << query(rt[r], rt[max(l - 1, 0)], s[n] ^ x) << endl;
        }
    }
    return 0;
}

P4592 [TJOI2018]异或

• 子树询问：按照dfs序建可持久化字典树，rtD[]
• 路径询问：每个点依赖父节点建可持久化字典树，rtT[]

#include <bits/stdc++.h>
using namespace std;

namespace Trie
{
    const int MAXNODE = 100000 * 33 * 2; // 最多总节点数
    int tot, son[MAXNODE + 5][2], tag[MAXNODE + 5];
    // 基于编号为 pre 的字典树，新加了 val 这个数，建立一个编号为 now 的字典树。
    void insert(int now, int pre, int val)
    {
        for (int i = 30; i >= 0; i--)
        {
            tag[now] = tag[pre] + 1; // 在原版本的基础上更新
            int j = ((val >> i) & 1);
            if (j == 0)
            {
                son[now][0] = ++tot;
                son[now][1] = son[pre][1];
                now = son[now][0];
                pre = son[pre][0];
            }
            else
            {
                son[now][0] = son[pre][0];
                son[now][1] = ++tot;
                now = son[now][1];
                pre = son[pre][1];
            }
        }
        tag[now] = tag[pre] + 1;
    }
    // 编号为 now 的树与编号为 pre 的树，作差后得到的新树上查找与 val 的最大异或和
    int query(int now, int pre, int val)
    {
        int res = 0;
        for (int i = 30; i >= 0; i--)
        {
            int j = ((val >> i) & 1);
            // 尽量向不同的地方跳
            if (tag[son[now][1 - j]] - tag[son[pre][1 - j]])
            {
                res += (1 << i);
                now = son[now][1 - j];
                pre = son[pre][1 - j];
            }
            else
            {
                now = son[now][j];
                pre = son[pre][j];
            }
        }
        return res;
    }
}

const int MAXN = 100000;

int rtT[MAXN + 5];       // 根节点到当前节点的字典树
int rtD[MAXN + 5];       // dfs序从 1 到 i 的节点对应的字典树

int n, q;
int val[MAXN + 5];
vector<int> e[MAXN + 5]; 

void dfsT(int u, int fa)
{
    rtT[u] = ++Trie::tot;
    Trie::insert(rtT[u], rtT[fa], val[u]);
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfsT(v, u);
    }
}

int dfsCnt;
int dfn[MAXN + 5]; // dfn[i]：节点i的dfs序
int dfx[MAXN + 5]; // dfx[i]：dfs序为i的节点
int siz[MAXN + 5];
int dep[MAXN + 5];
int lg[MAXN + 5];
int f[MAXN + 5][32];
void dfsD(int u, int fa)
{
    dfn[u] = ++dfsCnt;
    dfx[dfsCnt] = u;
    dep[u] = dep[fa] + 1;
    siz[u] = 1;
    // lca的预处理
    f[u][0] = fa;
    for (int i = 1; i <= lg[dep[u]]; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfsD(v, u);
        siz[u] += siz[v];
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y])
        x = f[x][lg[dep[x] - dep[y]] - 1];
    if (x == y)
        return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 按到根节点路径建立可持久化字典树
    dfsT(1, 0);
    // 计算字典序、节点深度、子树大小、并预处理 lca
    dfsCnt = 0;
    dep[0] = 0;
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    dfsD(1, 0);
    // 按字典序建立可持久化字典树
    for (int i = 1; i <= dfsCnt; i++)
    {
        Trie::tot++;
        rtD[i] = Trie::tot;
        Trie::insert(rtD[i], rtD[i - 1], val[dfx[i]]);
    }
    // 处理询问
    while (q--)
    {
        int op, x, y, z;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> z;
            cout << Trie::query(rtD[dfn[x] + siz[x] - 1], rtD[dfn[x] - 1], z) << "\n";
        }
        else if (op == 2)
        {
            cin >> x >> y >> z;
            int xy = lca(x, y);
            int fa = f[xy][0];
            cout << max(Trie::query(rtT[x], rtT[fa], z),
                        Trie::query(rtT[y], rtT[fa], z))
                 << "\n";
        }
    }
    return 0;
}