题解：Milano C.le

题目分析

问题核心

给定 (n) 列火车的到达顺序（第一天）和离开顺序（第二天），所有火车需停靠站台，且满足约束：若火车 (x) 先进入某站台，火车 (y) 后进入同一站台，则 (x) 不能在 (y) 离开前离开。求最少需要的站台数量。

关键约束与建模

1. 调度规则转化：

   • 到达顺序：第 (i) 列火车的到达排名为 (a_i)（排列，无重复）。
   • 离开顺序：第 (i) 列火车的离开排名为 (b_i)（排列，无重复）。
   • 约束本质：若火车 (x) 的到达时间早于火车 (y)（(a_x < a_y)），且离开时间晚于 (y)（(b_x > b_y)），则 (x) 和 (y) 不能共用一个站台（否则 (y) 会被 (x) 阻塞无法按时离开）。

2. 问题转化： 最少站台数 = 满足 (a_x < a_y) 且 (b_x > b_y) 的“冲突火车对”所构成的序列中，最长反链的长度（ Dilworth 定理）。进一步观察可发现，该问题等价于求特定序列的 最长递增子序列（LIS）长度。

转化逻辑

• 按到达顺序排序：由于到达顺序是排列，我们可以重新定义火车的“编号”为到达排名。设火车 (k) 的到达排名为 (k)（即 (a_i = k) 对应第 (k) 个到达的火车），其对应的离开排名为 (c_k = b_i)（即 (c[k]) 表示第 (k) 个到达的火车的离开排名）。
• 冲突关系转化：第 (k) 个到达的火车（早到）与第 (m) 个到达的火车（晚到，(k < m)）冲突，当且仅当 (c[k] > c[m])（早到的火车晚离开）。
• 最少站台数 = 序列 (c[1..n]) 的 最长递减子序列长度（根据 Dilworth 定理，偏序集的最小链覆盖数等于最长反链长度；而最长递减子序列长度与最长递增子序列长度可通过取反转化，此处直接求最长递减子序列长度即可）。

数据范围挑战

• (n \leq 2 \times 10^5)，需 (O(n \log n)) 复杂度的算法，不能使用 (O(n^2)) 的暴力DP。

算法设计

核心思路

1. 序列转化：将原始输入转化为“到达顺序对应的离开排名序列 (c)”。
2. 最长递减子序列（LDS）求解：利用树状数组（Fenwick Tree）优化，将 LDS 问题转化为 LIS 问题（通过取反），实现 (O(n \log n)) 求解。

具体步骤

1. 序列转化

• 输入的 (a) 数组是“第 (i) 列火车的到达排名”，(b) 数组是“第 (i) 列火车的离开排名”。
• 定义 (c[k]) 表示“第 (k) 个到达的火车的离开排名”：对于第 (i) 列火车，其到达排名为 (a_i = k)，因此 (c[k] = b_i)。
• 代码实现：a[p[i]] = read() 中，(p[i]) 存储到达排名为 (i) 的火车的原始索引，后续通过 (a[p[i]] = b[i]) 完成 (c) 序列的构建（代码中 (a) 数组实际存储的是 (c) 序列）。

2. 树状数组优化 LDS 求解

• 最长递减子序列长度 = 序列 (c[1..n]) 中，每个元素 (c[k]) 对应的“以 (c[k]) 结尾的最长递减子序列长度”的最大值。
• 转化为 LIS 问题：由于 (c[k]) 是排列（(b) 是排列），所有元素互不重复。最长递减子序列长度 = 序列 (d[k] = n - c[k] + 1) 的最长递增子序列长度（将每个元素取反，递减变递增）。
• 树状数组作用：维护当前元素对应的最长递增子序列长度，支持高效查询和更新：
  • 对于每个 (d[k])，查询树状数组中 (d[k]-1) 之前的最大值（即所有比 (d[k]) 小的元素对应的最长 LIS 长度），该值 +1 即为以 (d[k]) 结尾的 LIS 长度。
  • 更新树状数组，将 (d[k]) 位置的值更新为当前最长 LIS 长度。
  • 最终树状数组中的最大值即为 LIS 长度，也就是原序列的 LDS 长度，即最少站台数。

树状数组的选择理由

• 树状数组支持区间最大值查询和单点更新，时间复杂度均为 (O(\log M))（(M) 为序列元素的最大值，此处 (M = n)）。
• 适配 (O(n \log n)) 复杂度要求，适合大规模数据。

代码关键模块解析

1. 快速读入（read 函数）

int read() {
    int w = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -f : f, c = getchar();
    while (c >= '0' && c <= '9') w = w * 10 + c - 48, c = getchar();
    return w * f;
}

• 用于快速读取输入数据，适配大规模输入（(n \leq 2 \times 10^5)），提升效率。

2. 序列转化

for (int i = 1; i <= n; i++) p[i] = read(); // p[i] 是第 i 列火车的到达排名 a_i
for (int i = 1; i <= n; i++) a[p[i]] = read(); // a[k] = b_i，即第 k 个到达的火车的离开排名（c[k] = a[k]）

• 示例：若第 3 列火车的到达排名为 (a_3 = 2)，离开排名为 (b_3 = 5)，则 (p[3] = 2)，(a[2] = 5)，表示第 2 个到达的火车离开排名为 5。

3. 树状数组操作（update + query）

int t[N]; // 树状数组，维护区间最大值
void update(int x, int v) {
    for (; x <= n; x += x & -x)
        t[x] = max(t[x], v); // 单点更新，将 x 位置的最大值更新为 v
}
int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res = max(res, t[x]); // 查询 [1, x] 区间的最大值
    return res;
}

• query(x)：查询树状数组中前 (x) 个元素的最大值，对应“比 (d[k] = x) 小的元素的最长 LIS 长度”。
• update(x, v)：将 (x) 位置的元素更新为 (v)，对应“以 (d[k] = x) 结尾的最长 LIS 长度为 (v)”。

4. 主逻辑：求解 LIS 长度

for (int i = 1; i <= n; i++) {
    int d = n - a[i] + 1; // 将 c[k] = a[i] 取反，转化为 LIS 问题
    int len = query(d - 1) + 1; // 以 d 结尾的 LIS 长度
    update(d, len); // 更新树状数组
}
printf("%d\n", query(n)); // 树状数组的最大值即为 LIS 长度，即最少站台数

• 示例：若 (a[i] = 3)（离开排名），(n = 5)，则 (d = 5 - 3 + 1 = 3)，查询所有小于 3 的 (d) 对应的最长 LIS 长度，加 1 即为当前元素的 LIS 长度。

时间复杂度与空间复杂度

• 时间复杂度：(O(n \log n))。序列转化为 (O(n))，树状数组的每次查询和更新均为 (O(\log n))，共 (n) 次操作。
• 空间复杂度：(O(n))。存储 (p)、(a)、树状数组 (t)，均为线性空间。

关键结论

1. 问题转化是核心：将火车调度的站台数问题，通过到达/离开顺序的映射，转化为最长递减子序列长度问题，再通过取反转化为最长递增子序列，适配高效算法。
2. 树状数组的应用：树状数组高效支持区间最大值查询和单点更新，是 (O(n \log n)) 求解 LIS/LDS 的最优选择之一。
3. Dilworth 定理的应用：最少站台数（最小链覆盖数）等于最长反链长度（最长冲突火车序列长度），直接指导问题转化方向。