Struct nekolib::ds::IncrementalLineSet

pub struct IncrementalLineSet<I: Ord> { /* private fields */ }

直線の集合。

以下のクエリを処理する。

• 集合 $S \gets \emptyset$ で初期化する。
• 集合 $S$ に 1 次関数 $\lambda x.\; ax+b$ を追加する。
• 集合 $S$ 中の関数における、$x=x_0$ での最小値を返す。

言い換えると、直線の追加クエリと、特定の $x$ 座標での $y$ 座標の最小値を求めるクエリを捌く。いわゆる CHT。

Idea

次の二つの連想配列を管理する。

• $a$ を与えると、$\lambda x.\; ax+b \in S$ なる $b$ を返す。
• $a$ を与えると、$\lambda x.\; ax+b \in S$ が最小となる $x$ の最大値 $x_a$ を返す。
  • こちらは双方向で管理しておく。すなわち、$x_a\mapsto a$ の連想配列も持つ。

保持しておく必要がある直線を対応する区間の昇順に並べると、傾きの降順に並ぶことに気づく。 そこで、追加したい直線の傾きより小さい最大の傾きの直線と、大きい最小の直線と比較し、 新しい直線が必要かどうかをまず確かめる。 それが必要なら、追加する直線に近い方から順にすでにある直線を見ていき、 必要なものが見つかるまで削除する。

クエリを整数とすると、以下が成り立つ。

$$ \begin{aligned} f(\lambda x.\; a_l x+b_l, \lambda x.\; a_r x+b_r) &= \max\,\{k \mid a_l k+b_l \le a_r k+b_r \} \\ &= \left\lfloor\frac{b_r-b_l}{a_l-a_r}\right\rfloor. \end{aligned} $$

Complexity

演算	時間計算量
new	$O(1)$
push	$O(\log(|S'|))$
min	$O(\log(|S'|))$

ここで、$S'$ は $S$ から必要のない直線を除いたものからなる集合である。

Applications

次の形式の DP の高速化に使える。 $$ \mathrm{dp}[i] = \min_{0\le j\lt i} (p(j)+q(j)\cdot r(i)) +s(i). $$ $\min_{0\le j\lt i} (\bullet)$ の部分が、直線 $y=q(j)\cdot x+p(j)$ の $x=r(i)$ における最小値に相当するためである。$\mathrm{dp}[i]$ の値を求めた後、直線 $y=q(i)\cdot x+p(i)$ を追加していけばよい。ここで、$p(j)$ や $q(j)$ は $\mathrm{dp}[j]$ を含んでもよいし含まなくてもよい。どちらにも $\mathrm{dp}[j]$ が含まれない場合には、特に DP 配列のようなものを用意する必要はない。

たとえば、次のようなものが当てはまる。 $$ \begin{aligned} \mathrm{dp}[i] &= \min_{0\le j\lt i} (\mathrm{dp}[j]+(a_j-a_i)^2) \\ &= \min_{0\le j\lt i} ((\mathrm{dp}[j]+a_j^2) + (-2\cdot a_j)\cdot a_i)+a_i^2. \end{aligned} $$

お気に入りの例として、次のような問題 も解ける：

整数列 $a = (a_0, a_1, \dots, a_{n-1})$ が与えられる。 これの空でもよい区間 $(a_l, a_{l+1}, \dots, a_{r-1})$ に対し、次の値を考える。 $$ \sum_{i=l}^{r-1} (i-l+1)\cdot a_i = 1\cdot a_l+2\cdot a_{l+1} + \dots + (r-l)\cdot a_{r-1}. $$ 全ての区間の選び方におけるこの値の最大値を求めよ。

Sample

[5, -1000, 1, -3, 7, -8]
          [ ------ ] => 1 * 1 + (-3) * 2 + 7 * 3 = 16

$\sigma(r) = \sum_{i=0}^{r-1} a_i$、$\tau(r) = \sum_{i=0}^{r-1} (i+1)\cdot a_i$ とおくと、次のように変形できる。 $$ \begin{aligned} \sum_{i=l}^{r-1} (i-l+1)\cdot a_i &= \sum_{i=l}^{r-1} (i+1)\cdot a_i - \sum_{i=l}^{r-1} l\cdot a_i \\ &= (\tau(r)-\tau(l)) - l\cdot (\sigma(r) - \sigma(l)) . \end{aligned} $$

右端 $r$ を固定したときの最大値を $\mathrm{dp}[r]$ とおくと、 $$ \begin{aligned} \mathrm{dp}[r] &= \max_{0\le l\lt r} (\tau(r)-\tau(l)) - l\cdot(\sigma(r)-\sigma(l)) \\ &= \max_{0\le l\lt r} (l\cdot\sigma(l)-\tau(l) - l\cdot\sigma(r))+\tau(r) \\ &= -\min_{0\le l\lt r}(\tau(l)-l\cdot\sigma(l) + l\cdot\sigma(r))+\tau(r) \end{aligned} $$ とできる。よって、上記の枠組みで $p(j) = \tau(j)-j\cdot\sigma(j)$、$q(j)=j$、 $r(i)=\sigma(i)$、$s(i)=\tau(i)$ としたものと見なせ、$\sigma(\bullet)$ や $\tau(\bullet)$ の計算を適切に高速化すれば、$O(n\log(n))$ 時間で解ける。

Examples

use nekolib::ds::IncrementalLineSet;

let mut ls = IncrementalLineSet::new();
assert_eq!(ls.min(0), None);

ls.push((2, 2));
assert_eq!(ls.min(0), Some(2));
assert_eq!(ls.min(2), Some(6));

ls.push((1, 3));
assert_eq!(ls.min(0), Some(2));
assert_eq!(ls.min(2), Some(5));
assert_eq!(ls.min(5), Some(8));

ls.push((-1, 10));
assert_eq!(ls.min(2), Some(5));
assert_eq!(ls.min(5), Some(5));

assert_eq!(
    format!("{:?}", ls),
    r"{\x. 2x+2: ..=1, \x. x+3: ..=3, \x. -x+10: ..=2147483647}"
);

use nekolib::ds::IncrementalLineSet;

let a = vec![5, -1000, 1, -3, 7, -8];
let n = a.len();

let sigma = {
    let mut sigma = vec![0; n + 1];
    for i in 0..n {
        sigma[i + 1] = sigma[i] + a[i];
    }
    sigma
};
let tau = {
    let mut tau = vec![0; n + 1];
    for i in 0..n {
        tau[i + 1] = tau[i] + a[i] * (i + 1) as i64;
    }
    tau
};
let p = |j: usize| tau[j] - j as i64 * sigma[j];
let q = |j: usize| j as i64;
let r = |i: usize| sigma[i];
let s = |i: usize| tau[i];

let mut ls = IncrementalLineSet::new();
let mut dp = vec![0; n + 1];
ls.push((q(0), p(0)));
for i in 1..=n {
    dp[i] = -ls.min(r(i)).unwrap() + s(i);
    ls.push((q(i), p(i)));
}
let res = *dp.iter().max().unwrap();
assert_eq!(res, 1 * 1 + (-3) * 2 + 7 * 3);

References

• https://noshi91.hatenablog.com/entry/2021/03/23/200810

Implementations

impl<I: ChtInt> IncrementalLineSet<I>

pub fn new() -> Self

pub fn push(&mut self, (a, b): (I, I))

pub fn min(&self, x: I) -> Option<I>

pub fn inner_len(&self) -> usize

Trait Implementations

impl<I: Clone + Ord> Clone for IncrementalLineSet<I>

fn clone(&self) -> IncrementalLineSet<I>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: ChtInt> Debug for IncrementalLineSet<I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I: Default + Ord> Default for IncrementalLineSet<I>

fn default() -> IncrementalLineSet<I>

Returns the “default value” for a type.