Trie（字典树）：一堆字符串摆成一棵树

// 标准答案：一棵树都不建，每次询问把 n 个单词挨个比一遍 —— O(qnL)
//
// 它是这道题最直白的翻译，也是对拍的标准答案：
//   · 「以 p 为前缀」就是 `s.compare(0, p.size(), p) == 0`（先确认 s 够长）；
//   · 「恰好等于 p」就是 `s == p`。
//
// ★ 它和正解**没有任何共同的想法**：正解那边一次字符串比较都不做，只是顺着树走 |p| 步。
//   而且它天然没有「多测不清空」这个问题（每组自己的 vector 各存各的）——
//   ⇒ 于是 wrongClear.cpp 那个坑，它抓得到。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        vector<string> w(n);
        for (int i = 0; i < n; i++) cin >> w[i];
        for (int i = 0; i < q; i++) {
            string p;
            cin >> p;
            int pre = 0, same = 0;
            for (int j = 0; j < n; j++) {
                if (w[j].size() >= p.size() && w[j].compare(0, p.size(), p) == 0) {
                    pre++;
                    if (w[j].size() == p.size()) same++;
                }
            }
            cout << pre << ' ' << same << '\n';
        }
    }
    return 0;
}

// 正解：Trie（字典树），O(总长)
//
// ★ 关键的一步只有一句话：**把一堆字符串摆成一棵「每条边是一个字符」的树**。
//   于是「以 p 为前缀的有几个」不再需要去看那 n 个单词长什么样 ——
//   只要顺着 p 的每个字符往下走 |p| 步，读出那个节点上的计数就行。
//   ⇒ 查一次是 O(|p|)，**和单词的数量 n 一点关系都没有**。
//
// ⚠⚠ 两个计数一定要分开，这是这一章第一个、也是最容易犯的错：
//     cntPass[u] = 有多少个单词**路过**了 u        —— 回答「以它为前缀的有几个」
//     cntEnd[u]  = 有多少个单词**正好在 u 结束**   —— 回答「恰好等于它的有几个」
//   混起来的话，只要数据里没有「一个串是另一个串的前缀」就一模一样，测不出来（wrongEnd.cpp）。
//
// ⚠ 这一份是多组数据，于是有第二个坑：**组与组之间要清空**。
//   而清空的写法本身就是一课：`memset` 整个 ch[MAXN][26] 是 104 MB 的活，
//   T 组就是 T 遍 —— 答案全对，但会 TLE（wrongMemset.cpp）。
//   ⇒ 正确做法在下面 clearUsed()：**只清用过的那 tot + 1 个节点**。

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

/* 节点数上限 = 所有单词的总长 + 1（每个字符最多新开一个节点，再加一个根） */
const int MAXN = 1000005;

int ch[MAXN][26];        // ⚠ 26 × 10⁶ × 4 字节 = 104 MB，这一章第 9 步专门算这笔账
int cntPass[MAXN];       // 有多少个单词路过这个节点
int cntEnd[MAXN];        // 有多少个单词正好在这个节点结束
int tot;                 // 已经用掉的最大节点编号（0 号是根，代表空前缀）

void insertWord(const string& s) {
    int u = 0;                                  // 从根出发
    for (char c : s) {
        int k = c - 'a';
        if (!ch[u][k]) ch[u][k] = ++tot;        // 这条边还没有，就新开一个节点
        u = ch[u][k];
        cntPass[u]++;                           // ★ 路过就加（⚠ 根不加）
    }
    cntEnd[u]++;                                // ★ 只有走到头的那个节点才加
}

/** 返回 {以 s 为前缀的单词数, 恰好等于 s 的单词数} */
pair<int, int> ask(const string& s) {
    int u = 0;
    for (char c : s) {
        int k = c - 'a';
        if (!ch[u][k]) return make_pair(0, 0);  // ⚠ 走不下去 ⇒ 一个都没有，必须立刻返回
        u = ch[u][k];
    }
    return make_pair(cntPass[u], cntEnd[u]);
}

/** ★ 只清用过的那 tot + 1 个节点 —— 不是 memset 整个数组 */
void clearUsed() {
    for (int i = 0; i <= tot; i++) {
        memset(ch[i], 0, sizeof(ch[i]));
        cntPass[i] = cntEnd[i] = 0;
    }
    tot = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            insertWord(s);
        }
        for (int i = 0; i < q; i++) {
            string p;
            cin >> p;
            pair<int, int> r = ask(p);
            cout << r.first << ' ' << r.second << '\n';
        }
        clearUsed();
    }
    return 0;
}

// ★★ 这一章的第二个考点：Trie 到底占多少内存 —— 而且它取决于数据长什么样
//
// 账很好算：`ch[节点数][26]`，一个 int 4 字节 ⇒ **26 × 节点数 × 4 字节**。
// 可「节点数」不是常数：**Trie 的节点数 = 所有单词的不同前缀的个数**。
//   · 随机 26 字母的单词几乎不共享前缀 ⇒ 节点数几乎等于总长，内存顶满；
//   · 字母表一小、或者大家有共同的开头 ⇒ 一大片前缀被合并掉，能小几十倍。
// ⇒ **同样的总长，内存能差一个数量级** —— 这就是 Trie 真实的取舍点。
//
// 用法：
//   ./mem table [总长] [seed]    三种形状各建一次，打表（节点数 / 字节数）
//   ./mem <形状> [总长] [seed]   只做一种，并且打印本进程的峰值内存
//   ./mem csv   [总长] [seed]    同一张表，只打 `键,值`，给 check:viz 用
//   形状：long（长单词，随机 26 字母，前缀几乎不共享）/ rand26（短单词，随机 26 字母）
//         / rand3（只有 3 个字母）/ share（都以同一段开头）
//
// ⚠ 峰值内存那一行要单独跑一种形状才准 —— 一个进程里连做三种，量到的是最费的那一种。

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

const int MAXN = 1000005;
static int ch[MAXN][26];
static int tot;

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

/** 造一批单词：总长约 total，形状由 shape 定 */
static vector<string> makeWords(const string& shape, int total, unsigned seed) {
    mt19937 rng(seed);
    vector<string> w;
    const int LEN = (shape == "long") ? 40 : 8;
    int K = (shape == "rand3") ? 3 : 26;
    string common;
    if (shape == "share") for (int i = 0; i < 6; i++) common += (char)('a' + rng() % 26);
    int used = 0;
    while (used < total) {
        string s = common;
        int rest = LEN - (int)common.size();
        if (rest < 1) rest = 1;
        for (int i = 0; i < rest; i++) s += (char)('a' + rng() % (unsigned)K);
        used += (int)s.size();
        w.push_back(s);
    }
    return w;
}

/** 建一棵 Trie，返回 {节点数（含根）, 总长} */
static pair<long long, long long> build(const vector<string>& w) {
    for (int i = 0; i <= tot; i++) memset(ch[i], 0, sizeof(ch[i]));
    tot = 0;
    long long len = 0;
    for (const string& s : w) {
        int u = 0;
        len += (long long)s.size();
        for (char c : s) {
            int k = c - 'a';
            if (!ch[u][k]) ch[u][k] = ++tot;
            u = ch[u][k];
        }
    }
    return make_pair((long long)tot + 1, len);
}

int main(int argc, char** argv) {
    string cmd = (argc > 1) ? argv[1] : "table";
    bool csv = (cmd == "csv");
    bool table = (cmd == "table" || csv);
    int total = (argc > 2) ? atoi(argv[2]) : 1000000;
    unsigned seed = (unsigned)((argc > 3) ? atoi(argv[3]) : 1);
    const char* SHAPES[4] = {"long", "rand26", "rand3", "share"};

    if (!table) {
        vector<string> w = makeWords(cmd, total, seed);
        pair<long long, long long> r = build(w);
        struct rusage ru;
        getrusage(RUSAGE_SELF, &ru);
        printf("形状 %s：%zu 个单词，总长 %lld\n", cmd.c_str(), w.size(), r.second);
        printf("  Trie 节点数        %lld\n", r.first);
        printf("  26 x 节点数 x 4    %.1f MiB\n", 26.0 * (double)r.first * 4.0 / 1048576.0);
        printf("  本进程峰值内存     %.1f MiB\n", (double)ru.ru_maxrss / 1024.0);
        return 0;
    }

    if (!csv) {
        printf("总长都是 %d，只有「形状」不一样：\n\n", total);
        cout << "  " << padDisp("形状", 10) << padDisp("单词数", 10) << padDisp("Trie 节点数", 14)
             << padDisp("节点/总长", 12) << "26 x 节点 x 4\n";
        cout << "  " << padDisp(string(8, '-'), 10) << padDisp(string(8, '-'), 10)
             << padDisp(string(12, '-'), 14) << padDisp(string(10, '-'), 12) << "-------------\n";
    }
    for (int i = 0; i < 4; i++) {
        vector<string> w = makeWords(SHAPES[i], total, seed);
        pair<long long, long long> r = build(w);
        double mib = 26.0 * (double)r.first * 4.0 / 1048576.0;
        if (csv) {
            printf("%s_nodes,%lld\n%s_words,%zu\n%s_len,%lld\n", SHAPES[i], r.first,
                   SHAPES[i], w.size(), SHAPES[i], r.second);
        } else {
            char buf[64];
            cout << "  " << padDisp(SHAPES[i], 10) << padDisp(to_string(w.size()), 10)
                 << padDisp(to_string(r.first), 14);
            snprintf(buf, sizeof(buf), "%.3f", (double)r.first / (double)r.second);
            cout << padDisp(buf, 12);
            snprintf(buf, sizeof(buf), "%.1f MiB", mib);
            cout << buf << "\n";
        }
    }
    if (!csv) {
        printf("\n  => 同样的总长，节点数差着三个数量级 —— Trie 省不省内存，全看前缀共享得多不多。\n");
        printf("  => 第一行已经贴着 256 MiB 的空间限制了，而它只是「单词长一点」而已。\n");
    }
    return 0;
}

// 换一把尺子：多组数据之间「清空」到底碰了多少格
//
// ★ 为什么需要它：wrongMemset.cpp 的**答案一个字节都不错**，对拍原理上看不见它
//   （第 36 章第四盲区：只影响复杂度、不影响答案的写法）。
//   秒表在小数据上也全是 0.00 秒。⇒ 只剩一把尺子好使：**数动作**。
//
// 数的是同一个动作：**往 ch / cntPass / cntEnd 里写一个 int**。
//   · 正解 clearUsed()：只清用过的那 tot + 1 个节点 ⇒ Σ(tot_i + 1) × 28 格
//     （28 = 26 个孩子 + cntPass + cntEnd）
//   · wrongMemset()：每组都抹掉整个数组     ⇒ T × MAXN × 28 格
//
// 用法：./clear < 输入      （和主程序同一份输入）
//       ./clear csv < 输入  只打 `键,值`，给 check:viz 用

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

const int MAXN = 1000005;
static int ch[MAXN][26];
static int tot;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    int T;
    cin >> T;
    long long usedNodes = 0;
    long long totalLen = 0;
    for (int t = 0; t < T; t++) {
        int n, q;
        cin >> n >> q;
        tot = 0;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            totalLen += (long long)s.size();
            int u = 0;
            for (char c : s) {
                int k = c - 'a';
                if (!ch[u][k]) ch[u][k] = ++tot;
                u = ch[u][k];
            }
        }
        for (int i = 0; i < q; i++) { string p; cin >> p; }
        usedNodes += tot + 1;
        for (int i = 0; i <= tot; i++) memset(ch[i], 0, sizeof(ch[i]));   // 真的清一遍，下一组才干净
    }

    const long long PER = 28;                       // 26 个孩子 + cntPass + cntEnd
    long long good = usedNodes * PER;
    long long bad = (long long)T * MAXN * PER;
    if (csv) {
        printf("T,%d\nnodes,%lld\nlen,%lld\ngood,%lld\nbad,%lld\nratio,%lld\n",
               T, usedNodes, totalLen, good, bad, bad / max(1LL, good));
        return 0;
    }
    printf("%d 组数据，单词总长 %lld，一共用到 %lld 个节点\n\n", T, totalLen, usedNodes);
    printf("  只清用过的（正解）      碰 %14lld 格\n", good);
    printf("  memset 整个数组         碰 %14lld 格\n", bad);
    printf("\n  ★ 差 %lld 倍 —— 而两份代码打出来的答案一个字节都不差。\n", bad / max(1LL, good));
    printf("  ⚠ 组数越多差得越狠：memset 那一列是 T x %d x 28，和数据多大毫无关系。\n", MAXN);
    return 0;
}

// 正解：Trie（字典树），O(总长)
//
// ★ 关键的一步只有一句话：**把一堆字符串摆成一棵「每条边是一个字符」的树**。
//   于是「以 p 为前缀的有几个」不再需要去看那 n 个单词长什么样 ——
//   只要顺着 p 的每个字符往下走 |p| 步，读出那个节点上的计数就行。
//   ⇒ 查一次是 O(|p|)，**和单词的数量 n 一点关系都没有**。
//
// ⚠⚠ 两个计数一定要分开，这是这一章第一个、也是最容易犯的错：
//     cntPass[u] = 有多少个单词**路过**了 u        —— 回答「以它为前缀的有几个」
//     cntEnd[u]  = 有多少个单词**正好在 u 结束**   —— 回答「恰好等于它的有几个」
//   混起来的话，只要数据里没有「一个串是另一个串的前缀」就一模一样，测不出来（wrongEnd.cpp）。
//
// ⚠ 这一份是多组数据，于是有第二个坑：**组与组之间要清空**。
//   而清空的写法本身就是一课：`memset` 整个 ch[MAXN][26] 是 104 MB 的活，
//   T 组就是 T 遍 —— 答案全对，但会 TLE（wrongMemset.cpp）。
//   ⇒ 正确做法在下面 clearUsed()：**只清用过的那 tot + 1 个节点**。

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

/* 节点数上限 = 所有单词的总长 + 1（每个字符最多新开一个节点，再加一个根） */
const int MAXN = 1000005;

int ch[MAXN][26];        // ⚠ 26 × 10⁶ × 4 字节 = 104 MB，这一章第 9 步专门算这笔账
int cntPass[MAXN];       // 有多少个单词路过这个节点
int cntEnd[MAXN];        // 有多少个单词正好在这个节点结束
int tot;                 // 已经用掉的最大节点编号（0 号是根，代表空前缀）

void insertWord(const string& s) {
    int u = 0;                                  // 从根出发
    for (char c : s) {
        int k = c - 'a';
        if (!ch[u][k]) ch[u][k] = ++tot;        // 这条边还没有，就新开一个节点
        u = ch[u][k];
        cntPass[u]++;                           // ★ 路过就加（⚠ 根不加）
    }
    cntEnd[u]++;                                // ★ 只有走到头的那个节点才加
}

/** 返回 {以 s 为前缀的单词数, 恰好等于 s 的单词数} */
pair<int, int> ask(const string& s) {
    int u = 0;
    for (char c : s) {
        int k = c - 'a';
        if (!ch[u][k]) return make_pair(0, 0);  // ⚠ 走不下去 ⇒ 一个都没有，必须立刻返回
        u = ch[u][k];
    }
    return make_pair(cntPass[u], cntEnd[u]);
}

/** ★ 只清用过的那 tot + 1 个节点 —— 不是 memset 整个数组 */
void clearUsed() {
    for (int i = 0; i <= tot; i++) {
        memset(ch[i], 0, sizeof(ch[i]));
        cntPass[i] = cntEnd[i] = 0;
    }
    tot = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            insertWord(s);
        }
        for (int i = 0; i < q; i++) {
            string p;
            cin >> p;
            pair<int, int> r = ask(p);
            cout << r.first << ' ' << r.second << '\n';
        }
        clearUsed();
    }
    return 0;
}

// 01-Trie 那一节的标准答案：两两枚举，O(n²)
//
// 题面（章末那道小题）：给 n 个非负整数（都小于 2³⁰），求任意两个数异或起来最大是多少。
// 输入：第一行 n，第二行 n 个整数。输出：一个数。
//
// ★ 它就是「把所有可能都试一遍」，n = 3 万时是 4.5 亿对 —— 慢，但绝对不会错。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<unsigned> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    unsigned best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            best = max(best, a[i] ^ a[j]);
    cout << best << '\n';
    return 0;
}

// 01-Trie：把整数按二进制位插进一棵 Trie，求最大异或对 —— O(n × 位数)
//
// ★ 这一节接的是第 46 章那句话：**一个整数就是一排开关**。
//   既然是一排 0/1，那它就是一个只有两个字母的字符串 —— 于是它能进 Trie。
//   ⚠ 而且**必须从最高位开始**插、从最高位开始查：异或的结果哪一位是 1 更值钱，
//     完全由位号决定（第 30 位的一个 1，比后面 30 位全是 1 还大）。
//
// ★ 关键的一步：拿一个数 x 去树上找「和它异或最大的那个」时，
//   **每一位都贪心地往相反的那边走** —— 那一位能凑出 1 就凑。
//   ⚠ 但相反的那边可能空着（树上没有这样的数），那就只能走同边，这一位只好是 0。
//   这两句话缺一不可：漏了前一句就成了乱走（xorWrongOrder），漏了后一句会走到空节点（xorWrongGreedy）。

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

const int BITS = 30;                       // 题面保证 a[i] < 2^30
const int MAXN = 100005 * (BITS + 1);      // 每个数最多新开 BITS 个节点

int ch[MAXN][2];
int tot;

void insertNum(unsigned x) {
    int u = 0;
    for (int b = BITS - 1; b >= 0; b--) {  // ★ 从最高位开始
        int k = (x >> b) & 1;
        if (!ch[u][k]) ch[u][k] = ++tot;
        u = ch[u][k];
    }
}

/** 树上已有的数里，和 x 异或最大是多少 */
unsigned askMax(unsigned x) {
    int u = 0;
    unsigned res = 0;
    for (int b = BITS - 1; b >= 0; b--) {
        int k = (x >> b) & 1;
        if (ch[u][k ^ 1]) {                // ★ 相反的那边有路 ⇒ 这一位能凑出 1
            res |= 1u << b;
            u = ch[u][k ^ 1];
        } else {                           // ⚠ 没路，只能走同边，这一位只好是 0
            u = ch[u][k];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    unsigned best = 0;
    /* ★ 边插边查：第 i 个数只和「前面已经进树的那些」配对 ——
       这样既不会拿自己和自己异或（那永远是 0，不影响最大值，但意思不对），
       也不用先把所有数都读进来。 */
    for (int i = 0; i < n; i++) {
        unsigned x;
        cin >> x;
        if (i > 0) best = max(best, askMax(x));   // 只和「前面已经进树的那些」配对
        insertNum(x);
    }
    cout << best << '\n';
    return 0;
}