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

// P2580 于是他错误的点名开始了 —— 正解：Trie，节点上挂一个**三态**
//
// ★ 这道题和 [P8306](/sol/p8306/) 的骨架一模一样，可**挂在节点上的东西换了**：
//   P8306 挂的是「路过的有几个」（一个计数），这道题挂的是一个**状态**：
//
//       0 = 这儿不是任何一个名字的结尾
//       1 = 是名字，还没被点到过
//       2 = 是名字，而且已经点过了
//
//   查询 = 顺着走到底，读那个状态，然后**把 1 改成 2**。
//   ⇒ 本章那两个计数（cntPass / cntEnd）在这道题上一个都用不上 ——
//     用得上的是「cntEnd 是不是 0」这半句，再加一位「点过没有」。
//
// ⚠ 两处最容易漏：
//   ① 走不下去要立刻 WRONG（不然 u 掉回根，答的是某个后缀的状态）；
//   ② 走到了，但那个节点的状态是 0（它只是别人的**前缀**）⇒ 也是 WRONG。
//      ★ 官方样例里名单有 `a`、`ad`、`acd`，而问的正好是 `a` —— **它测不出第 ② 条**。

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

/* 名单总长上限 = n × 50 = 10⁴ × 50 = 5×10⁵，再加一个根 */
const int MAXN = 500005;

int ch[MAXN][26];        // 26 × 5×10⁵ × 4 字节 = 49.6 MiB（题面给 128 MiB）
int st[MAXN];            // 0 / 1 / 2 三态
int tot;

void insertName(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];
    }
    st[u] = 1;                                  // ★ 只在结尾那个节点上做记号
}

/** 返回 0 = WRONG，1 = OK，2 = REPEAT */
int askName(const string& s) {
    int u = 0;
    for (char c : s) {
        int k = c - 'a';
        if (!ch[u][k]) return 0;                // ⚠ ① 走不下去 ⇒ 名单里没有
        u = ch[u][k];
    }
    if (st[u] == 0) return 0;                   // ⚠ ② 走到了，但它只是别人的前缀
    if (st[u] == 1) { st[u] = 2; return 1; }    // 第一次点到
    return 2;                                   // 点过了
}

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

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) { string s; cin >> s; insertName(s); }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s; cin >> s;
        int r = askName(s);
        cout << (r == 0 ? "WRONG" : r == 1 ? "OK" : "REPEAT") << '\n';
    }
    return 0;
}

// P2580 换一把尺子：三条路各**摸了多少个字符**（机器无关，换台机器一个数不变）
//
// 用法：./p2580Count <csv|table> < 一份输入
//
// 三条路摸字符的方式完全不同：
//   ✗ 逐个比：对每次点名，从头扫名单，`==` 先比长度、长度相同再逐字节比，第一个不同就停；
//   ★ map  ：红黑树里 O(log n) 次字符串比较，每次同样是「比到第一个不同为止」；
//   ★ Trie ：**建树时每个名字的每个字符走一步，查询时点名的每个字符走一步**，仅此而已。
//
// ⚠ 而这三个数**和秒表指向的赢家不一样**（解析页第 ③ 步那张表）——
//   Trie 摸的字符最少，可它要碰一片 49.6 MiB 的数组，而另外两条路只碰几 MB。

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

static long long mapChars = 0;

/** 一个会数「比了多少个字符」的字符串比较器 */
struct CountingLess {
    bool operator()(const string& a, const string& b) const {
        size_t i = 0;
        while (i < a.size() && i < b.size() && a[i] == b[i]) i++;
        mapChars += (long long)i + 1;                  // 比到第一个不同（或到头）为止
        if (i == a.size() || i == b.size()) return a.size() < b.size();
        return a[i] < b[i];
    }
};

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";

    int n;
    if (!(scanf("%d", &n) == 1)) return 0;
    vector<string> name(n);
    static char buf[105];
    for (int i = 0; i < n; i++) { if (scanf("%104s", buf) != 1) return 0; name[i] = buf; }
    int m;
    if (scanf("%d", &m) != 1) return 0;
    vector<string> call(m);
    for (int i = 0; i < m; i++) { if (scanf("%104s", buf) != 1) return 0; call[i] = buf; }

    long long nameLen = 0, callLen = 0;
    for (const string& s : name) nameLen += (long long)s.size();
    for (const string& s : call) callLen += (long long)s.size();

    /* ① 逐个比：数「看了多少个名字」和「摸了多少个字符」 */
    long long bruteVisits = 0, bruteChars = 0;
    {
        vector<int> used(n, 0);
        for (const string& q : call) {
            for (int j = 0; j < n; j++) {
                bruteVisits++;
                if (name[j].size() != q.size()) { bruteChars += 1; continue; }
                size_t i = 0;
                while (i < q.size() && name[j][i] == q[i]) i++;
                bruteChars += (long long)i + 1;
                if (i == q.size()) { used[j] = used[j] ? 2 : 1; break; }
            }
        }
    }

    /* ② map：拿会计数的比较器跑一遍 */
    long long mapInsert = 0;
    {
        mapChars = 0;
        map<string, int, CountingLess> st;
        for (const string& s : name) st[s] = 1;
        mapInsert = mapChars;
        for (const string& q : call) {
            map<string, int, CountingLess>::iterator it = st.find(q);
            if (it != st.end() && it->second == 1) it->second = 2;
        }
    }
    long long mapTotal = mapChars;

    /* ③ Trie：建树 + 查询，每个字符正好一步（查询走不下去就提前停） */
    long long trieSteps = nameLen;
    {
        /* 只为数步数，用 map 存边就够了 —— 数出来的步数和真 Trie 一模一样 */
        vector<map<char, int> > ch(1);
        vector<char> isEnd(1, 0);
        for (const string& s : name) {
            int u = 0;
            for (char c : s) {
                map<char, int>::iterator it = ch[u].find(c);
                if (it == ch[u].end()) { ch.push_back(map<char, int>()); isEnd.push_back(0); ch[u][c] = (int)ch.size() - 1; u = (int)ch.size() - 1; }
                else u = it->second;
            }
            isEnd[u] = 1;
        }
        for (const string& q : call) {
            int u = 0;
            for (char c : q) {
                map<char, int>::iterator it = ch[u].find(c);
                if (it == ch[u].end()) break;
                u = it->second;
                trieSteps++;
            }
        }
        (void)isEnd;
    }

    vector<pair<string, long long> > out;
    out.push_back(make_pair("n", n));
    out.push_back(make_pair("m", m));
    out.push_back(make_pair("name_len", nameLen));
    out.push_back(make_pair("call_len", callLen));
    out.push_back(make_pair("brute_visits", bruteVisits));
    out.push_back(make_pair("brute_chars", bruteChars));
    out.push_back(make_pair("map_insert", mapInsert));
    out.push_back(make_pair("map_chars", mapTotal));
    out.push_back(make_pair("trie_steps", trieSteps));

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%lld\n", out[i].first.c_str(), out[i].second);
    else for (size_t i = 0; i < out.size(); i++) printf("  %-14s %lld\n", out[i].first.c_str(), out[i].second);
    return 0;
}