55 · 回顾九：数据结构与字符串

处理第 i 个数时，窗口是 [max(1, i−m), i−1]。

队列里存下标，对应的值单调递增，队头就是当前窗口最小值。

三步固定：① 输出队头（队列空则输出 0）；② 插入 i，插入前把队尾所有 ≥ a[i] 的弹掉；③ 把下标 ≤ i−m 的队头弹掉。

为什么被弹掉的不会回来：它下标更小、值又不更小，在它过期之前全面劣于新元素，之后也不会重新进入窗口。

复杂度 O(n)：每个下标最多进队一次、出队一次。n = 2×10⁶ 时约 4×10⁶ 次操作。

对照：每个位置向前重扫 m 个是 O(nm)，m = n 时 4×10¹² → TLE；multiset 是 O(n log n)，常数大 3~5 倍。

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

const int MAXN = 2000005;
int a[MAXN], q[MAXN];          // q 存下标：手写队列，比 deque 快一倍

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    int head = 1, tail = 0;     // 队列区间 [head, tail]，head > tail 表示空
    for (int i = 1; i <= n; ++i) {
        if (head > tail) printf("0\n");          // 只有 i = 1 会走到这里
        else printf("%d\n", a[q[head]]);         // 队头就是前 m 个数的最小值

        while (head <= tail && a[q[tail]] >= a[i]) --tail;  // 又大又早的队尾没用了
        q[++tail] = i;                           // 存下标，才能判过期

        while (head <= tail && q[head] <= i - m) ++head;    // 窗口左端是 i-m+1
    }
    return 0;
}

用一个大根堆 small 存较小的一半，一个小根堆 large 存较大的一半。

不变式：small.size() = large.size() 或 large.size() + 1，并且 small 里所有元素 ≤ large 里所有元素。

插入 x：x ≤ small.top() 就进 small，否则进 large。

调整：small 比 large 多出 2 个或更多，就把 small 的堆顶（小半部分的最大值）搬给 large；small 比 large 少，就把 large 的堆顶（大半部分的最小值）搬回 small。

长度为 2k−1 时，small 恰好 k 个、large 恰好 k−1 个，中位数 = small.top()。

复杂度 O(n log n)：每个数至多进堆一次、跨堆搬一次。

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

int main() {
    int n;
    scanf("%d", &n);
    priority_queue<int> small;                                  // 大根堆：较小的一半
    priority_queue<int, vector<int>, greater<int> > large;      // 小根堆：较大的一半

    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        if (small.empty() || x <= small.top()) small.push(x);
        else large.push(x);

        // 插入后立刻恢复不变式，别等到输出前才调
        if ((int)small.size() > (int)large.size() + 1) {
            large.push(small.top()); small.pop();
        } else if ((int)small.size() < (int)large.size()) {
            small.push(large.top()); large.pop();
        }

        if (i & 1) printf("%d\n", small.top());   // 长度 2k-1 时，中位数是 small 的堆顶
    }
    return 0;
}

建 Trie：0 号是根，边表示字符，ch[p][c] 是节点 p 走字符 c 的儿子。

插入：沿字符往下走，没有儿子就新建，最后在结尾节点上标 1。

查询：沿字符往下走，中途没有儿子 → WRONG（断链）；走到底但结尾没标记 → WRONG（它只是别人的前缀）；标记为 1 → 改成 2 并输出 OK；标记为 2 → REPEAT。

节点数上界 = 所有名字长度之和 + 1 ≤ 10⁴ × 50 + 1 ≈ 5×10⁵。

空间 26 × 5×10⁵ × 4 字节 ≈ 52 MB，在 128 MB 限制内，但不能再多开一倍。

复杂度 O(总字符数) ≈ 5×10⁵ + 5×10⁶（查询串总长），比 map 的每行一次 log 快得多。

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

const int MAXNODE = 500005;      // 所有名字的总长度 + 1
int ch[MAXNODE][26];             // ch[p][c]：节点 p 走字符 c 的儿子，0 表示没有
int vis[MAXNODE];                // 0 不是单词；1 是单词且没点过；2 点过了
int tot;                         // 已用节点数，新节点编号 = ++tot

void insert(const string &s) {
    int p = 0;                                       // 0 号是根
    for (char c : s) {
        int x = c - 'a';
        if (!ch[p][x]) ch[p][x] = ++tot;             // 没有这条边就新建
        p = ch[p][x];
    }
    vis[p] = 1;                                      // 只在单词结尾打标记
}

int query(const string &s) {
    int p = 0;
    for (char c : s) {
        int x = c - 'a';
        if (!ch[p][x]) return 0;                     // 断链：名单里没有
        p = ch[p][x];
    }
    if (vis[p] == 0) return 0;                       // 走到底却没标记：只是别人的前缀
    if (vis[p] == 1) { vis[p] = 2; return 1; }       // 第一次点到
    return 2;                                        // 之前点过
}

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

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) { string s; cin >> s; insert(s); }

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        int r = query(s);
        if (r == 0) cout << "WRONG\n";
        else if (r == 1) cout << "OK\n";
        else cout << "REPEAT\n";
    }
    return 0;
}

nxt[i] = p[0..i−1] 的最长 border 长度，nxt[1] = 0。

递推：已知 nxt[i]，令 j = nxt[i]；若 p[i] == p[j] 则 nxt[i+1] = j + 1，否则 j = nxt[j] 继续退到 0。

匹配：i 扫主串，j 是已匹配长度；s[i] == p[j] 则 ++j，否则 j = nxt[j]；j == m 时记录起点。

起点换成 1-based：i 是 0-based 的结尾，起点 = i − m + 1（0-based）= i − m + 2（1-based）。

找到一次后令 j = nxt[m]，才能继续找重叠的出现（如 s1 = aaa、s2 = aa 有两个位置）。

复杂度 O(n + m)：i 只增不减；j 每次失配至少减 1，总减少量不超过总增加量。

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

const int MAXN = 1000005;
int nxt[MAXN];                  // nxt[i]：p[0..i-1] 的最长 border 长度

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

    string s, p;
    cin >> s >> p;
    int n = s.size(), m = p.size();

    nxt[1] = 0;                                       // 单字符前缀没有非空真 border
    for (int i = 1, j = 0; i < m; ++i) {              // 循环开始时 j 恒等于 nxt[i]
        while (j && p[i] != p[j]) j = nxt[j];         // 失配就退到更短的 border
        if (p[i] == p[j]) ++j;                        // 接得上就延长一位
        nxt[i + 1] = j;                               // 记的是「长度 i+1 的前缀」
    }

    for (int i = 0, j = 0; i < n; ++i) {
        while (j && s[i] != p[j]) j = nxt[j];         // 主串指针 i 从不后退
        if (s[i] == p[j]) ++j;
        if (j == m) {                                 // 找到一个完整匹配
            printf("%d\n", i - m + 2);                // 换成 1-based 起点
            j = nxt[j];                               // 退一步，继续找重叠的出现
        }
    }

    for (int i = 1; i <= m; ++i) printf("%d ", nxt[i]);
    printf("\n");
    return 0;
}

依次给每个左部点 u 找匹配，用 dfs 找一条增广路。

dfs(u)：枚举 u 的每条边 (u, v)。若 v 本轮没试过，标记它；v 空闲则 match[v] = u 直接成功；否则递归 dfs(match[v])，若能给 match[v] 找到新位置，就让 v 归 u。

成功一次，匹配数 +1。匈牙利算法的正确性来自「不存在增广路 ⇔ 当前匹配已是最大匹配」。

vis 用时间戳：每轮 ++stamp，vis[v] == stamp 表示本轮试过，省掉每组 O(m) 的 memset。

复杂度 O(V·E)：500 × 5×10⁴ = 2.5×10⁷，1 秒内可过。

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

const int MAXN = 505;
vector<int> g[MAXN];             // 只存左部 → 右部的边
int match[MAXN];                 // match[v]：右部点 v 的搭档，0 表示空闲
int vis[MAXN], stamp;            // vis[v] == stamp 表示「本轮 dfs 试过 v」

bool dfs(int u) {
    for (int v : g[u]) {
        if (vis[v] == stamp) continue;      // 本轮试过就跳过，否则会绕圈
        vis[v] = stamp;
        if (!match[v] || dfs(match[v])) {   // v 空闲，或 v 的搭档能换走
            match[v] = u;                   // 让位成功，v 归 u
            return true;
        }
    }
    return false;
}

int main() {
    int n, m, e;
    scanf("%d%d%d", &n, &m, &e);
    for (int i = 0; i < e; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
    }

    int ans = 0;
    for (int u = 1; u <= n; ++u) {
        ++stamp;                            // 等价于 memset(vis)，但只花 O(1)
        if (dfs(u)) ++ans;
    }
    printf("%d\n", ans);
    return 0;
}