题解

思路

先在原序列上求：

• $L_i$：以 $i$ 结尾的最长严格上升子序列长度；
• $R_i$：以 $i$ 开始的最长严格上升子序列长度；
• 原序列 LIS 长度 $K$。

若 $L_i+R_i-1=K$，则 $i$ 位于某条最长上升子序列上。进一步按 $L_i$ 分层：若这一层只有 $i$ 一个满足条件的元素，那么所有原 LIS 都经过 $i$。修改该位置后，不使用新值的最好答案是 $K-1$；否则仍为 $K$。

使用新值 $b$ 的最好答案为

两个最大值分别是二维偏序查询。把所有高度离散化，按位置从左向右和从右向左各扫描一次，用树状数组维护高度前缀最大值。

做法

子任务 1：二次 LIS

对每个假设临时修改数组，用 $O(n^2)$ 动态规划重算 LIS，再恢复原值。复杂度 $O(mn^2)$。

子任务 2：耐心排序重算

每个假设用 lower_bound 维护最小结尾数组，在 $O(n\log n)$ 时间重算 LIS。总复杂度 $O(mn\log n)$。

子任务 3：离线二维偏序

先用树状数组求 $L_i,R_i$ 和必经点。再按查询位置离线：左扫时在处理位置 $a$ 前，结构中恰含所有 $j<a$；右扫同理维护所有 $j>a$。严格大小关系通过查询离散排名的开区间实现。

正确性证明

引理 1

修改位置 $a$ 后，不使用新元素的最长长度为 $K-c_a$，其中 $c_a$ 表示 $a$ 是否被所有原 LIS 经过。

证明。 若存在不经过 $a$ 的原 LIS，修改不影响它，长度仍为 $K$。否则删除 $a$ 可由任意原 LIS 得到长度 $K-1$，且不使用 $a$ 不可能仍达 $K$。分层计数恰好判定是否所有原 LIS 都经过 $a$。$\square$

引理 2

使用新元素 $(a,b)$ 的最长长度为 $1+\max_{j<a,h_j<b}L_j+\max_{j>a,h_j>b}R_j$。

证明。 新元素左侧必须接一个值小于 $b$ 的上升子序列，右侧必须接一个值大于 $b$ 的上升子序列；二者位置和值域互不冲突，可以与新元素拼接。任意包含新元素的 LIS 也必能如此拆分。$\square$

定理

算法对每个假设输出正确的 LIS 长度。

证明。 任意修改后的 LIS 要么不使用新元素，由引理 1 覆盖；要么使用新元素，由引理 2 覆盖。算法取两类最大值，因此得到全局最优。$\square$

复杂度

时间复杂度为 $O((n+m)\log(n+m))$，空间复杂度为 $O(n+m)$。