60 · 终极综合：60 题大回顾

把问题拆成两层：外层是对「路径上城市费用最大值」的二分，内层是普通的单源最短路。

判定问题：给定 lim，只保留费用 ≤ lim 的城市，跑 1 到 n 的最短路，若 dist[n] ≤ b 则 lim 可行。

单调性：lim 增大时可用城市集合只增不减，最短路只可能变短，所以可行 lim 构成一个后缀——可以二分。

候选集是所有城市费用排序去重后的数组。先判最大候选是否可行，不可行直接输出 AFK；否则二分出最小的可行下标。

细节：起点 1 和终点 n 也要交费，所以 f[1] > lim 或 f[n] > lim 时直接不可行。漏了这一句，当 lim 落在 f[1] 与 f[n] 之间时会输出一个实际上走不通的答案。

复杂度：离散化 O(n log n)；二分 log n ≈ 14 次，每次 Dijkstra O(m log n) ≈ 5×10⁴ × 14，总计约 10⁷ 次操作。最长简单路径不过 10⁴ 条边，每条 10⁹，最短路最大 10¹³，dist 必须 long long。

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

const int MAXN = 10005;
typedef long long ll;
typedef pair<ll, int> pli;

int n, m;
ll b;
ll f[MAXN];                              // 每个城市的费用
vector<pair<int,int>> g[MAXN];           // (终点, 生命值消耗)

ll dist[MAXN];

bool check(ll lim) {                     // 只允许走费用 <= lim 的城市
    if (f[1] > lim || f[n] > lim) return false;   // 起终点也要交费
    const ll INF = (ll)4e18;
    fill(dist, dist + n + 1, INF);
    dist[1] = 0;

    priority_queue<pli, vector<pli>, greater<pli>> pq;   // 小根堆：(距离, 编号)
    pq.push({0, 1});
    while (!pq.empty()) {
        pli cur = pq.top(); pq.pop();
        ll d = cur.first;
        int u = cur.second;
        if (d > dist[u]) continue;       // 过期版本
        if (d > b) continue;             // 已经超过血量，再走只会更贵
        for (auto &e : g[u]) {
            int v = e.first, w = e.second;
            if (f[v] > lim) continue;    // 这个城市太贵，不能进
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist[n] <= b;
}

int main() {
    scanf("%d%d%lld", &n, &m, &b);
    for (int i = 1; i <= n; ++i) scanf("%lld", &f[i]);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});          // 双向道路，两条边都要存
    }

    vector<ll> val(f + 1, f + n + 1);    // 候选集：所有城市费用
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    if (!check(val.back())) {            // 最宽松的上界也不行 → 无解
        puts("AFK");
        return 0;
    }

    int lo = 0, hi = (int)val.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(val[mid])) hi = mid;   // 可行：答案不右于 mid
        else                 lo = mid + 1;
    }
    printf("%lld\n", val[lo]);
    return 0;
}

逆序对 = Σ_i（i 右边比 a_i 小的个数）。把统计对象从「数对」换成「每个位置的一份贡献」。

从右往左扫，维护一个集合 = 已经扫过的数（也就是 i 右边的数）。查询「比 a_i 小的有几个」，就是一次前缀求和；把 a_i 加入集合，就是一次单点加 1。树状数组两个操作都是 O(log n)。

下标问题：a_i 到 10⁹，树状数组装不下。做离散化——把所有值排序去重，把 a_i 换成它的名次 rk（1…n）。名次之间的大小关系与原值完全一致，所以逆序对个数不变。

于是 rk − 1 就是「严格小于」的范围：query(rk − 1) 天然排除了相等的情况，题目要的正是严格大于。

复杂度 O(n log n)：n = 5×10⁵ 时约 5×10⁵ × 19 × 2 ≈ 2×10⁷ 次操作。

答案上界 n(n−1)/2 = 1.25×10¹¹，必须 long long。另一条路是归并排序：合并两个有序段时，右段每个元素被取走前，左段剩下的元素都与它构成逆序对（第 21、56 节的递归分治）。

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

const int MAXN = 500005;
int n, a[MAXN], bit[MAXN];       // bit 存的是「名次 <= i 的已出现个数」

void add(int i) {                // 名次 i 上出现了一个数
    for (; i <= n; i += i & -i) ++bit[i];
}

int query(int i) {               // 名次 <= i 的已出现个数，也就是前缀和
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

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

    vector<int> v(a + 1, a + n + 1);          // 复制一份用来离散化
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    long long ans = 0;                        // 最多 1.25e11，必须 long long
    for (int i = n; i >= 1; --i) {            // 从右往左：集合里全是「右边」的数
        int rk = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        ans += query(rk - 1);                 // 右边严格小于它的个数
        add(rk);
    }

    printf("%lld\n", ans);
    return 0;
}

先建映射：pos[x] = x 在 P₁ 中出现的位置（1…n，每个 x 恰好一个）。

把 P₂ 逐项换成 pos 值，得到序列 c：c_i = pos[P_2,i]。

关键等价：P₁ 与 P₂ 的公共子序列，与 c 的上升子序列一一对应。因为一个子序列同时是 P₁ 的子序列，意味着它的元素在 P₁ 中的位置按顺序递增——而 c 的下标顺序就是它在 P₂ 中的顺序，c 的值就是它在 P₁ 中的位置。两个顺序都对上，长度自然相等。

于是问题变成「求 c 的最长上升子序列」，用 tail 数组 + 二分做 O(n log n)：tail[len] 记录「长度为 len 的上升子序列的最小结尾」，每个 c_i 用 lower_bound 找到第一个 ≥ 它的位置替换掉。

为什么可以替换：结尾越小，后面能接的数越多，所以「最小结尾」这一状态足以代表全部长度为 len 的子序列。

c 是 1…n 的一个排列，元素互不相同，所以 lower_bound 与 upper_bound 结果一致；若换成有重复的序列求「不下降子序列」，就得用 upper_bound。复杂度 O(n log n)。

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

const int N = 100005;
int pos[N], c[N], tail[N];   // tail[len]：长度为 len 的上升子序列的最小结尾

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {      // 第一个排列：记下每个数在第几位
        int x;
        scanf("%d", &x);
        pos[x] = i;
    }
    for (int i = 1; i <= n; ++i) {      // 第二个排列：换成「在第一个排列里的位置」
        int y;
        scanf("%d", &y);
        c[i] = pos[y];
    }

    int len = 0;                         // 当前 LIS 长度
    for (int i = 1; i <= n; ++i) {
        // 找到第一个 tail >= c[i] 的位置；tail[1..len] 是单调不减的
        int p = (int)(lower_bound(tail + 1, tail + len + 1, c[i]) - tail);
        tail[p] = c[i];                  // 用更小的结尾替换，给后面留更多余地
        if (p == len + 1) ++len;         // 接到了末尾，长度加一
    }

    printf("%d\n", len);
    return 0;
}

两步走：先筛出 [2, √R] 的全部素数（埃氏筛，√R ≤ 46341，数组几万个就够了）；再用这些小素数去「筛掉」[L, R] 里的合数。

第二步：对每个小素数 p，把 [L, R] 中 p 的倍数标记为合数。起点取 max(p², ⌈L/p⌉·p)：从 p 开始是为了不划掉 p 本身，从 ⌈L/p⌉·p 开始是为了不划掉区间左边的数。

标记数组只需要 R − L + 1 个位置，用 x − L 当下标。这就是「区间筛」的全部内容。

为什么只筛到 √R：任何合数 x ≤ R 都有一个不超过 √x ≤ √R 的因子；这个因子对应的素数一定在筛出的表里。

边界：L = 1 时要把 1 单独标成非素数；L = R 时答案要么 1 要么 0。

溢出：p ≤ 46341，p × p 最大 46341² = 2147488281，比 INT_MAX（2147483647）还大 4634，用 int 算会变成负数，循环下标变负 → RE。所有涉及乘积的地方一律 long long。

复杂度：筛小素数 O(√R log log R)，标记区间 Σ (R−L)/p = O((R−L) log log R)，R = 2³¹ 时约 4.6×10⁴ + 10⁶ × 3 次操作。

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

const int MAXS = 1000005;
const int MAXP = 50005;         // sqrt(2^31 - 1) ≈ 46341
bool isp[MAXP];                 // 小素数表
bool mark[MAXS];                // mark[i] 表示 L + i 是合数

int main() {
    long long L, R;
    scanf("%lld%lld", &L, &R);

    int lim = (int)sqrt((double)R) + 1;     // 只需要筛到 sqrt(R)

    fill(isp, isp + lim + 1, true);
    isp[0] = isp[1] = false;
    for (int i = 2; i <= lim; ++i)
        if (isp[i])
            for (long long j = 1LL * i * i; j <= lim; j += i)  // i*i 用 long long 算
                isp[j] = false;

    long long len = R - L + 1;
    if (L == 1) mark[0] = true;             // 1 不是素数

    for (int i = 2; i <= lim; ++i) {
        if (!isp[i]) continue;
        long long p = i;
        // 从 p 的平方 或 第一个 >= L 的倍数 开始划；两者取大，避免划掉 p 自己
        long long st = max(p * p, (L + p - 1) / p * p);
        for (long long x = st; x <= R; x += p)
            mark[x - L] = true;
    }

    int ans = 0;
    for (long long i = 0; i < len; ++i)
        if (!mark[i]) ++ans;

    printf("%d\n", ans);
    return 0;
}

定义 nxt[i] = s₂[1..i] 的最长 border 长度（即最长的、既是前缀又是后缀、且不等于本身的长度）。

递推：假设 nxt[i−1] = j 已经算出。若 s₂[i] == s₂[j+1]，则 nxt[i] = j + 1；否则令 j = nxt[j] 继续试，直到 j = 0 或字符相等。这一步的依据是：i 位置的所有可行 border 长度，必然依次是 nxt[i−1]、nxt[nxt[i−1]]、…（border 链）。

匹配：在 s₁ 上维护 j = 「当前已匹配的长度」。s₁[i] 与 s₂[j+1] 相等则 ++j，否则 j = nxt[j] 回跳。j 达到 m 时输出起点 i − m + 1，然后令 j = nxt[j] 继续（允许重叠）。

复杂度：j 每次成功匹配加 1，总共只加 O(n) 次；每次回跳 j 至少减 1，所以回跳总次数也是 O(n)。均摊下来整个匹配 O(n + m)，10⁶ 的规模毫无压力。

为什么不能 j = 0 直接重来：那样已经匹配的那一段信息全丢了，退化成暴力。

输出注意：位置从 1 开始数，所以起点是 i − m + 1；最后一行才是 nxt 数组，nxt[1] = 0 也要输出。

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

const int MAXN = 1000005;
char s[MAXN], t[MAXN];
int nxt[MAXN];

int main() {
    scanf("%s", s + 1);              // 从下标 1 开始存：位置直接是 i - m + 1
    scanf("%s", t + 1);
    int n = (int)strlen(s + 1), m = (int)strlen(t + 1);

    // ① 求 t 的前缀函数：nxt[i] = t[1..i] 的最长 border 长度
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && t[i] != t[j + 1]) j = nxt[j];   // 失配：沿 border 链回退
        if (t[i] == t[j + 1]) ++j;                  // 接上一位，匹配长度加一
        nxt[i] = j;
    }

    // ② 在 s 上匹配：j 是「当前已经匹配的长度」
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && s[i] != t[j + 1]) j = nxt[j];
        if (s[i] == t[j + 1]) ++j;
        if (j == m) {                               // 完整出现一次
            printf("%d\n", i - m + 1);              // 起点（1 起）
            j = nxt[j];                             // 允许重叠，继续找下一处
        }
    }

    // ③ 最后一行：nxt[1..m]
    for (int i = 1; i <= m; ++i) {
        if (i > 1) putchar(' ');
        printf("%d", nxt[i]);
    }
    putchar('\n');
    return 0;
}