haar_lib/ds/
cht.rs

1//! Convex Hull Trick
2//!
3//! # Problems
4//! - [EDPC Z - Frog 3](https://atcoder.jp/contests/dp/submissions/54932537)
5
6use crate::math::linear::*;
7use crate::trait_alias;
8use std::{
9    collections::VecDeque,
10    ops::{Add, Mul, Sub},
11};
12
13trait_alias!(
14    /// [`ConvexHullTrick<T>`]がt扱える型
15    Elem: Copy + PartialEq + PartialOrd + Sub<Output = Self> + Mul<Output = Self> + Add<Output = Self>
16);
17
18/// 最大値クエリか最小値クエリかを表す
19#[derive(PartialEq, Eq, Copy, Clone, Debug)]
20pub enum Mode {
21    /// 最大値クエリ
22    Max,
23    /// 最小値クエリ
24    Min,
25}
26
27impl Mode {
28    fn cmp<T: PartialOrd + Copy>(self, a: T, b: T) -> bool {
29        match self {
30            Mode::Max => a <= b,
31            Mode::Min => a >= b,
32        }
33    }
34}
35
36fn is_needless<T: Elem>(a: &Linear<T>, b: &Linear<T>, c: &Linear<T>) -> bool {
37    (a.b - b.b) * (a.a - c.a) >= (a.b - c.b) * (a.a - b.a)
38}
39
40/// Convex hull trick
41#[derive(Clone, Debug)]
42pub struct ConvexHullTrick<T> {
43    lines: VecDeque<Linear<T>>,
44    mode: Mode,
45    last_query: Option<T>,
46    last_slope: Option<T>,
47}
48
49impl<T: Elem> ConvexHullTrick<T> {
50    /// 最小値クエリ・最大値クエリを指定して空の[`ConvexHullTrick`]を用意する。
51    pub fn new(mode: Mode) -> Self {
52        Self {
53            lines: VecDeque::new(),
54            mode,
55            last_query: None,
56            last_slope: None,
57        }
58    }
59
60    /// 最小値を求めたいならば、傾きは単調減少でなければならない。
61    ///
62    /// 最大値を求めたいならば、傾きは単調増加でなければならない。
63    pub fn add(&mut self, line @ Linear { a, b }: Linear<T>) {
64        if let Some(p) = self.last_slope {
65            if !self.mode.cmp(p, a) {
66                panic!("`mode`が`Max`/`Min`ならば、`a`は単調増加/減少でなければならない。");
67            }
68        }
69        self.last_slope = Some(a);
70
71        if let Some(l) = self.lines.back() {
72            if l.a == a {
73                if !self.mode.cmp(l.b, b) {
74                    return;
75                }
76                self.lines.pop_back();
77            }
78        }
79        while self.lines.len() >= 2
80            && is_needless(
81                &line,
82                self.lines.back().unwrap(),
83                self.lines.get(self.lines.len() - 2).unwrap(),
84            )
85        {
86            self.lines.pop_back();
87        }
88
89        self.lines.push_back(line);
90    }
91
92    /// クエリの座標は単調増加でなければならない。
93    pub fn query(&mut self, x: T) -> T {
94        if let Some(p) = self.last_query {
95            if x < p {
96                panic!("`x`はクエリ全体を通して単調増加でなければならない。");
97            }
98        }
99        self.last_query = Some(x);
100
101        while self.lines.len() >= 2
102            && self
103                .mode
104                .cmp(self.lines[0].apply(x), self.lines[1].apply(x))
105        {
106            self.lines.pop_front();
107        }
108
109        self.lines[0].apply(x)
110    }
111}
haar_lib/ds/cht.rs

haar_lib/ds/
cht.rs
