【烫科技】区间 LIS 查询超简单做法
ftiasch
·
·
算法·理论
「再见海草」
无修、带正权区间 LIS 查询的 O(n \, \log^2 n) 预处理,O(\log n) 查询简单做法。
Source: Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence QuerieIs https://arxiv.org/html/2610.20983
假设排列 合理a_0, \dots, a_{n - 1}, 权值是 w_0, \dots, w_{n - 1}. 目标是给定 [l, r), 查询区间内的权值之和最大的上升子序列(下面简称 LIS)。普通 LIS 查询是 w_i = 1 的特殊情况。
定义 D_i(l) 表示以 a_i 为终点,起点在 [l, \infty) (即起点在 a_l, a_{l + 1}, \dots 中) 的 LIS。特别地,当 i < l 时,定义 D_i(l) = 0.
在这基础上,定义 H_E(l) 是以 e \in E 为终点,起点在 [l, \infty) 中的 LIS,即 H_E(l) = \max_{e \in E} D_e(l). 我们最终要查询 H_{[0, r)}(l).
算法的中心思想是用主席树维护 H_E(\cdot) 。并注意到以下性质(最后证明):
如果 E = \mathrm{lower} \cup \mathrm{higher}, 同时对于 i \in \mathrm{lower}, j \in \mathrm{higher} 有 a_i < a_j, 那么存在一个 c,使得 H_E(l) = \begin{cases}H_{\mathrm{higher}}(l) & l < c \\ H_{\mathrm{lower}}(l) & c \leq l\end{cases}.
说人话就是,先把 H_E(\cdot) 想成一条折线,很明显它是单调不增的。把终点集合 E 按照值域分成小的一半 \mathrm{lower} 和大的一半 \mathrm{higher}. 这两条折线只会相交一次。因为 H_E(l) = \max\{H_{\mathrm{lower}}(l), H_{\mathrm{higher}}(l)\}, 所以 H_E(\cdot) 是由 H_{\mathrm{higher}}(\cdot) 的一段前缀和 H_{\mathrm{lower}}(\cdot) 的一段后缀组成的。
因为 H 是主席树,所以很容易通过 H_{\mathrm{lower}} 和 H_{\mathrm{higher}} 的主席树在 O(\log n) 内合并出 H_E 的主席树.
基于上面的性质,最终的算法流程是:
按照 i = 0, 1, \dots 插入每个终点。全局维护一个值域线段树 T,线段树中的节点 [l, h) 维护的是,已经插入的 i 中,值域在 [l, h)的终点组成的折线。即 H_{\{i \mid l \leq a_i < u\}}(\cdot).
当插入 i 时,要算 D_i(l),插入到 T 的叶子位置,然后一路往上更新.
固定 l 来想,经典的 DP 就是 D_i(l) = (\max_{j < i \wedge a_j < a_i} D_j(l)) + w_i = H_{\{i | j < i \wedge a_j < a_i\}}(l). 在 T 上把需要的值域前缀分解成 O(\log n) 段,合并起来就行。
更新和查询都是 O(\log^2 n) 的。
结束了?
最后的证明:
(还没学会传图, 证明先咕了)