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

haar_lib/ds/
li_chao.rs
