BZOJ 3439 Kpm 的 MC 密碼：Trie 樹 + 可持久化線段樹

題目大意

定義「kpm 串」：若字串 A 是字串 B 的後綴，則 A 稱為 B 的 kpm 串。給定一組字串，對每個字串詢問其第 k 大的 kpm 串（按編號排序）。

核心思路

1. 字串翻轉：將後綴問題轉為前綴問題，所有字串反轉後插入 Trie 樹。
2. Trie 節點維護可持久化線段樹：每個 Trie 節點保存一個 last 指標，指向該節點對應的可持久化線段樹版本。插入字串時，沿路徑更新 last，將字串編號加入線段樹。
3. 查詢：對第 i 個字串，其終點節點的 last 線段樹包含所有以該字串為後綴的字串編號。直接在線段樹上查詢第 k 小即可。

資料結構設計

• 可持久化線段樹節點：左/右子節點指標、計數 cnt。
• Trie 節點：26 個子節點指標、last 指向線段樹根。
• 空節點共用：用全域 nil 節點簡化邊界處理。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 300010
using namespace std;

#define P(c) ((c) - 'a')

struct SegTree {
    SegTree *son[2];
    int cnt;
    SegTree(SegTree* l, SegTree* r, int c) : son{l, r}, cnt(c) {}
    SegTree() : son{nullptr, nullptr}, cnt(0) {}
} none, *nil = &none;

SegTree* build(SegTree* last, int l, int r, int x) {
    if (l == r) return new SegTree(nullptr, nullptr, last->cnt + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) return new SegTree(build(last->son[0], l, mid, x), last->son[1], last->cnt + 1);
    return new SegTree(last->son[0], build(last->son[1], mid+1, r, x), last->cnt + 1);
}

struct Trie {
    Trie *son[26];
    SegTree *last;
    Trie() { memset(son, 0, sizeof(son)); last = nil; }
} *root = new Trie(), *end_pos[MAX];

int cnt;
char s[MAX];

void insert(char *s, int id) {
    Trie *now = root;
    while (*s) {
        int c = P(*s);
        if (!now->son[c]) now->son[c] = new Trie();
        now = now->son[c];
        now->last = build(now->last, 1, MAX, id);
        ++s;
    }
    end_pos[id] = now;
}

int ask(SegTree* now, int l, int r, int k) {
    if (now->cnt < k) return -1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (k <= now->son[0]->cnt) return ask(now->son[0], l, mid, k);
    return ask(now->son[1], mid+1, r, k - now->son[0]->cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> cnt;
    nil->son[0] = nil->son[1] = nil;
    for (int i = 1; i <= cnt; ++i) {
        scanf("%s", s);
        reverse(s, s + strlen(s));
        insert(s, i);
    }
    for (int i = 1, k; i <= cnt; ++i) {
        scanf("%d", &k);
        printf("%d\n", ask(end_pos[i]->last, 1, MAX, k));
    }
    return 0;
}

複雜度分析

• 插入：字串總長度 L，每字元 O(log N) 更新線段樹，總 O(L log N)
• 查詢：O(log N)
• 空間：O(L log N) 線段樹節點 + O(L) Trie 節點