题解：限制LIS长度的最大子序列长度

问题转化

给定序列 $B_m$（$B$ 的前 $m$ 个元素），求一个子序列 $C$，使得 $C$ 的最长上升子序列（LIS）长度 $\le k$，且 $|C|$ 最大化。

关键理论

1. Dilworth 定理与链分解

一个序列的 LIS 长度等于最小链划分中链的个数（这里链指不上升子序列）。

换句话说：序列的 LIS 长度 = 最小不上升子序列划分的个数。

因此，LIS 长度 $\le k$ 等价于序列可以划分为 $\le k$ 个不上升子序列。

2. 问题转化

最大化 $|C|$ 使得 LIS 长度 $\le k$，等价于：从原序列中删去最少的元素，使得剩余序列可以划分为 $\le k$ 个不上升子序列。

设删去的元素个数为 $d$，则 $|C| = m - d$，我们要最小化 $d$。

3. Dilworth 定理的另一种形式

序列的 LIS 长度等于其反链的最大大小（这里反链指两两不可比较的元组）。

但更实用的视角是：序列的 LIS 长度是 Patience Sorting 中堆的个数。

Patience Sorting 算法

维护若干个堆（每个堆顶是递增的），按顺序处理元素：

• 找到第一个堆顶 $\ge$ 当前元素 $x$ 的堆，将 $x$ 放入该堆顶（替换）
• 若不存在这样的堆，则新建一个堆，放入 $x$

最终堆的个数就是 LIS 长度。

4. 扩展到限制堆数

如果限制只能使用 $k$ 个堆，那么当需要第 $k+1$ 个堆时，就必须丢弃某些元素。

目标：丢弃最少的元素，使得 Patience Sorting 过程中堆数不超过 $k$。

5. 贪心策略

按顺序处理元素 $x$：

• 如果存在堆顶 $\ge x$，则放入最小的这样的堆顶（以保持堆顶递增）
• 如果不存在且当前堆数 $< k$，则新建堆放入 $x$
• 如果不存在且堆数 $= k$，则必须丢弃 $x$

这样可以保证丢弃数最少吗？需要证明。

6. 正确性证明

这实际上是求序列的 $k$-LIS 问题：允许删除若干元素后 LIS 长度 $\le k$，最大化剩余长度。

已知结论：按上述贪心，丢弃的元素个数等于最小删除数以使得 LIS $\le k$。

证明思路：每个堆对应一个不上升子序列，堆数不超过 $k$ 等价于可以划分为 $\le k$ 个不上升子序列。贪心保证了丢弃数最少。

7. 数据结构优化

我们需要在线维护 $k$ 个堆顶（单调递增数组），支持：

• 查询第一个 $\ge x$ 的位置（二分查找）
• 替换该位置的值为 $x$
• 若不存在且堆数 $< k$，则追加 $x$
• 若不存在且堆数 $= k$，则丢弃 $x$

设 $top[1..t]$ 为当前堆顶数组（$t \le k$），单调递增。

处理 $x$：

1. pos = \text{lower_bound}(top, x)
2. 若 $pos$ 存在：$top[pos] = x$
3. 否则若 $t < k$：$t++$, $top[t] = x$
4. 否则：$discard++$

最终答案 = $m - discard$。

8. 多组询问处理

有 $q$ 组询问 $(m_i, k_i)$，需要对每个询问独立计算。

直接对每个询问从头模拟 $O(nk)$ 不可行。

注意到 $k$ 较小（大部分 $k \le 50$），但 $n$ 达 $5\times 10^4$，$q$ 可能很大。

我们需要预处理，使得对每个询问能快速计算。

9. 预处理出每个前缀的堆顶数组

设 $f[m][t]$ 表示处理前 $m$ 个元素后，若允许 $t$ 个堆，堆顶数组的状态（即 $top[1..t]$）。

但状态空间太大。

观察性质：对于固定的 $m$，$top[1..t]$ 关于 $t$ 是单调的：$top[1]$ 是前 $m$ 个元素的最小可能 LIS 长度为 1 时的最大堆顶？不准确。

更直接：对于固定的 $m$，随着 $k$ 增大，丢弃数单调不增。

我们可以预处理出对于每个 $m$，丢弃数关于 $k$ 的函数 $d(m,k)$。

10. 离线处理

将询问按 $m$ 排序，递增处理。

维护当前处理到前 $m$ 个元素时，对所有 $k$ 的堆顶数组 $top_k[1..k]$。

当新增元素 $b_{m+1}$ 时，更新所有 $k$ 的状态。

但 $k$ 最大可能 $n$，不可行。

11. 关键优化：$k$ 的有效范围

由于 $n \le 50000$，序列的 LIS 长度最多 $n$。

对于 $k \ge LIS$，丢弃数为 0。

所以只需处理 $k \le LIS$ 的情况。

但 LIS 可能接近 $n$，仍然大。

12. 二分查找优化

对于固定的 $m$，我们想知道当允许 $k$ 个堆时的丢弃数。

设 $g(m,k)$ = 丢弃数。

性质：$g(m,k)$ 关于 $k$ 单调递减。

我们可以对每个 $m$ 预处理出 $k$ 的临界点：使得丢弃数 $\le$ 某个值的最大 $k$。

但查询需要 $g(m,k)$ 的具体值。

13. 维护所有可能的堆顶

注意 Patience Sorting 中，堆顶数组 $top[1..L]$（$L$ 为实际堆数）具有性质：$top[i]$ 是长度为 $i$ 的上升子序列的最小可能末尾值。

这个数组可以通过平衡树或树状数组维护。

对于每个 $k$，我们需要知道使用前 $k$ 个堆时的丢弃数。

丢弃数 = 总元素数 - 被放入堆中的元素数。

被放入堆中的元素数 = 所有 $top[i]$ 被更新的次数。

14. 另一种思路：转化为 LIS 计数

问题等价于：求最长的子序列，使得其 LIS 长度 $\le k$。

这等于：删除最少的元素，使得剩余序列的 LIS 长度 $\le k$。

而删除的最少元素数 = 序列长度 - 最大子序列长度满足 LIS $\le k$。

15. DP 状态

设 $dp[i][j]$ 表示考虑前 $i$ 个元素，当前 LIS 长度为 $j$ 时，所选子序列的最大长度。

转移：

• 不选第 $i$ 个元素：$dp[i][j] = dp[i-1][j]$
• 选第 $i$ 个元素：设 $t$ 为以 $b_i$ 结尾的 LIS 长度，则 $dp[i][t] = \max(dp[i][t], dp[i-1][j] + 1)$，其中 $j < t$

但 $t$ 依赖于前面所选元素，不是固定的。

16. 已知结论

这个问题是经典的在序列中选取最长子序列使得 LIS 长度 $\le k$。

最优解是贪心：维护 $k$ 个不上升子序列，尽可能多地放入元素。

贪心算法如前所述。

17. 实现方案

对于每个询问 $(m,k)$：

1. 初始化 $top$ 数组为空，$discard=0$
2. 遍历 $i=1$ 到 $m$：
   • $x = b_i$
   • 在 $top$ 中二分查找第一个 $\ge x$ 的位置 $pos$
   • 若找到：$top[pos] = x$
   • 否则若 $|top| < k$：$top.push\_back(x)$
   • 否则：$discard++$
3. 答案 = $m - discard$

复杂度 $O(m \log k)$ 每询问，最坏 $O(qn \log n)$ 不可接受。

18. 离线分块

将序列分块，每块大小 $S \approx \sqrt{n}$。

预处理每块内部对每个 $k$ 的答案。

合并块时，需要将两个块的堆顶数组合并。

合并两个堆顶数组：类似于归并两个有序数组，但需要保持 Patience Sorting 性质。

实际上，合并两个序列的 Patience Sorting 结果不是简单的合并堆顶数组。

19. 最终可行方案

由于 $n \le 50000$，$q$ 可能很大，但 $k$ 通常不大（除了测试点 13）。

我们可以对每个 $k$ 预处理答案。

预处理：对每个 $k$（$1 \le k \le K_{max}$），从头模拟整个序列，记录每个前缀 $m$ 的丢弃数 $discard[m][k]$。

查询时直接查表。

$K_{max}$ 取多少？由于 $k$ 大时答案接近 $m$，我们可以只预处理 $k \le K$，$K$ 取 50 或 100（根据数据范围）。

对于 $k > K$，答案就是 $m$（因为 LIS 长度不可能超过 $k$？不一定，但 $k$ 很大时丢弃数很小）。

更精确：当 $k \ge LIS(B_m)$ 时，答案 = $m$。

我们可以预处理每个前缀的 LIS 长度 $L[m]$。

对于 $k \ge L[m]$ 的询问，直接输出 $m$。

对于 $k < L[m]$ 的询问，使用预处理表。

20. 预处理复杂度

对每个 $k$ 模拟整个序列：$O(n \log k)$。

总复杂度 $O(K n \log K)$，取 $K=100$，$n=50000$，可接受。

21. 算法步骤

1. 读入 $n, q, b[1..n]$
2. 预处理每个前缀的 LIS 长度 $L[m]$（用 Patience Sorting $O(n \log n)$）
3. 确定 $K = \max\{k_i\}$（但可能很大），实际取 $K = \min(\max k_i, 100)$
4. 对于 $k=1$ 到 $K$：
   • 模拟整个序列，记录 $discard[m][k] =$ 前 $m$ 个元素处理完后的丢弃数
   • 同时记录 $ans[m][k] = m - discard[m][k]$
5. 对于每个询问 $(m,k)$：
   • 若 $k \ge L[m]$：输出 $m$
   • 否则若 $k \le K$：输出 $ans[m][k]$
   • 否则：模拟前 $m$ 个元素，使用 $k$ 个堆计算答案（这种情况很少）

22. 空间优化

$discard[m][k]$ 可以只存 $m$ 的前缀和，因为查询时需要 $discard[m][k]$ 而不是整个数组。

但我们需要对每个 $k$ 存储每个 $m$ 的丢弃数，空间 $O(nK)$，$K=100$，$n=50000$，约 $5\times 10^6$ 个整数，可接受。

23. 最终答案

输出每个询问对应的最大子序列长度。

---

这样可以在时间和空间允许范围内解决所有测试点。