haar_lib/ds/
li_chao.rs

1//! Li-Chao tree
2//!
3//! # Problems
4//!
5//! - [Line Add Get Min](https://judge.yosupo.jp/submission/217829)
6//! - [Segment Add Get Min](https://judge.yosupo.jp/submission/217834)
7
8use crate::algo::bsearch_slice::BinarySearch;
9use crate::math::linear::*;
10use crate::trait_alias;
11use std::{
12    cmp::{max, min},
13    mem::swap,
14    ops::{Add, Mul, RangeInclusive},
15};
16
17trait_alias!(
18    /// [`LiChaoTree<T>`]が扱える型
19    Elem: Copy + Ord + Add<Output = Self> + Mul<Output = Self>
20);
21
22/// 最大値クエリか最小値クエリかを表す
23#[derive(PartialEq, Eq, Copy, Clone, Debug)]
24pub enum Mode {
25    /// 最大値クエリ
26    Max,
27    /// 最小値クエリ
28    Min,
29}
30
31impl Mode {
32    fn op<T: Elem>(self, a: T, b: T) -> T {
33        match self {
34            Mode::Max => max(a, b),
35            Mode::Min => min(a, b),
36        }
37    }
38
39    fn cmp<T: Elem>(self, a: T, b: T) -> bool {
40        match self {
41            Mode::Max => a > b,
42            Mode::Min => a < b,
43        }
44    }
45}
46
47/// 直線や線分を追加して、事前指定した点での最大値(/最小値)を得る。
48pub struct LiChaoTree<T> {
49    xs: Vec<T>,
50    size: usize,
51    data: Vec<Option<Linear<T>>>,
52    range: Vec<(usize, usize)>,
53    mode: Mode,
54}
55
56impl<T: Elem> LiChaoTree<T> {
57    fn init_range(
58        range: &mut Vec<(usize, usize)>,
59        size: usize,
60        i: usize,
61        left: usize,
62        right: usize,
63    ) {
64        if i < size * 2 {
65            range[i] = (left, right);
66            let mid = (left + right) / 2;
67            Self::init_range(range, size, i << 1, left, mid);
68            Self::init_range(range, size, (i << 1) | 1, mid, right);
69        }
70    }
71
72    /// `query`で使用する点列`xs`と最大値クエリ/最小値クエリを指定して[`LiChaoTree`]を構築する。
73    pub fn new(mut xs: Vec<T>, mode: Mode) -> Result<Self, &'static str> {
74        if xs.is_empty() {
75            Err("`xs`が空なので、`LiChaoTree`は構築されない。")
76        } else {
77            xs.sort();
78            xs.dedup();
79
80            let size = xs.len().next_power_of_two();
81
82            xs.resize(size, *xs.last().unwrap());
83
84            let data = vec![None; size * 2];
85            let mut range = vec![(0, 0); size * 2];
86            Self::init_range(&mut range, size, 1, 0, size);
87
88            Ok(Self {
89                xs,
90                size,
91                data,
92                range,
93                mode,
94            })
95        }
96    }
97
98    fn update(&mut self, i: usize, mut new_line: Linear<T>, l: usize, r: usize) {
99        if let Some(line) = &self.data[i] {
100            let m = (l + r) / 2;
101            let lx = self.xs[l];
102            let mx = self.xs[m];
103            let rx = self.xs[r - 1];
104
105            let left = self.mode.cmp(new_line.apply(lx), line.apply(lx));
106            let mid = self.mode.cmp(new_line.apply(mx), line.apply(mx));
107            let right = self.mode.cmp(new_line.apply(rx), line.apply(rx));
108
109            if left && right {
110                self.data[i] = Some(new_line);
111                return;
112            }
113
114            if !left && !right {
115                return;
116            }
117
118            if mid {
119                swap(self.data[i].as_mut().unwrap(), &mut new_line);
120            }
121
122            if left != mid {
123                self.update(i << 1, new_line, l, m);
124            } else {
125                self.update((i << 1) | 1, new_line, m, r);
126            }
127        } else {
128            self.data[i] = Some(new_line);
129        }
130    }
131
132    /// 直線を追加する。
133    pub fn add_line(&mut self, line: Linear<T>) {
134        self.update(1, line, 0, self.size);
135    }
136
137    /// 線分を追加する。
138    pub fn add_segment(&mut self, segment: Linear<T>, range: RangeInclusive<T>) {
139        let mut l = self.xs.lower_bound(range.start()) + self.size;
140        let mut r = self.xs.lower_bound(range.end()) + self.size;
141
142        while l < r {
143            if r & 1 == 1 {
144                r -= 1;
145                self.update(r, segment.clone(), self.range[r].0, self.range[r].1);
146            }
147            if l & 1 == 1 {
148                self.update(l, segment.clone(), self.range[l].0, self.range[l].1);
149                l += 1;
150            }
151
152            r >>= 1;
153            l >>= 1;
154        }
155    }
156
157    /// `x`での最大値/最小値を返す。
158    pub fn query(&self, x: T) -> Option<T> {
159        let i = self.xs.binary_search(&x).expect("`x` must be in `xs`");
160        let mut k = i + self.size;
161        let mut ret = None;
162
163        while k > 0 {
164            if let Some(line) = &self.data[k] {
165                let a = line.apply(self.xs[i]);
166                ret = Some(ret.map_or(a, |y| self.mode.op(y, a)));
167            }
168
169            k >>= 1;
170        }
171
172        ret
173    }
174}
haar_lib/ds/li_chao.rs

haar_lib/ds/
li_chao.rs
