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 std::{
8    collections::VecDeque,
9    ops::{Add, Mul, Sub},
10};
11
12/// 最大値クエリか最小値クエリかを表す
13#[derive(PartialEq, Eq, Copy, Clone, Debug, Hash)]
14pub enum Mode {
15    /// 最大値クエリ
16    Max,
17    /// 最小値クエリ
18    Min,
19}
20
21impl Mode {
22    fn cmp<T: Ord + Copy>(self, a: T, b: T) -> bool {
23        match self {
24            Self::Max => a <= b,
25            Self::Min => a >= b,
26        }
27    }
28}
29
30fn is_needless<T>(a: &Linear<T>, b: &Linear<T>, c: &Linear<T>) -> bool
31where
32    T: Copy + Ord + Sub<Output = T> + Mul<Output = T>,
33{
34    (a.b - b.b) * (a.a - c.a) >= (a.b - c.b) * (a.a - b.a)
35}
36
37/// Convex hull trick
38#[derive(Clone, Debug)]
39pub struct ConvexHullTrick<T> {
40    lines: VecDeque<Linear<T>>,
41    mode: Mode,
42    last_query: Option<T>,
43    last_slope: Option<T>,
44}
45
46impl<T> ConvexHullTrick<T>
47where
48    T: Copy + Ord + Sub<Output = T> + Mul<Output = T> + Add<Output = T>,
49{
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    ///
64    /// 最大値を求めたいならば、傾きは単調増加でなければならない。
65    pub fn add(&mut self, line @ Linear { a, b }: Linear<T>) {
66        if let Some(p) = self.last_slope {
67            if !self.mode.cmp(p, a) {
68                panic!("`mode`が`Max`/`Min`ならば、`a`は単調増加/減少でなければならない。");
69            }
70        }
71        self.last_slope = Some(a);
72
73        if let Some(l) = self.lines.back() {
74            if l.a == a {
75                if !self.mode.cmp(l.b, b) {
76                    return;
77                }
78                self.lines.pop_back();
79            }
80        }
81        while self.lines.len() >= 2
82            && is_needless(
83                &line,
84                self.lines.back().unwrap(),
85                self.lines.get(self.lines.len() - 2).unwrap(),
86            )
87        {
88            self.lines.pop_back();
89        }
90
91        self.lines.push_back(line);
92    }
93
94    /// `x`での最小値/最大値を求める。
95    ///
96    /// クエリの座標は単調増加でなければならない。
97    pub fn query(&mut self, x: T) -> T {
98        if let Some(p) = self.last_query {
99            if x < p {
100                panic!("`x`はクエリ全体を通して単調増加でなければならない。");
101            }
102        }
103        self.last_query = Some(x);
104
105        while self.lines.len() >= 2
106            && self
107                .mode
108                .cmp(self.lines[0].apply(x), self.lines[1].apply(x))
109        {
110            self.lines.pop_front();
111        }
112
113        self.lines[0].apply(x)
114    }
115}
haar_lib/ds/cht.rs

haar_lib/ds/
cht.rs
