haar_lib/algo/
cartesian_tree.rs

1//! Cartesian tree
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/cartesian_tree>
5
6/// CartesianTree
7pub struct CartesianTree {
8    /// Cartesian treeの根
9    pub root: usize,
10    /// 親の頂点
11    pub parent: Vec<Option<usize>>,
12    /// 右の子の頂点
13    pub left: Vec<Option<usize>>,
14    /// 左の子の頂点
15    pub right: Vec<Option<usize>>,
16}
17
18impl CartesianTree {
19    /// distinctな配列`a`から[`CartesianTree`]を構築する。
20    pub fn new<T>(a: &[T]) -> Self
21    where
22        T: PartialOrd,
23    {
24        let n = a.len();
25        let mut p = vec![None; n];
26        let mut l = vec![None; n];
27        let mut r = vec![None; n];
28        let mut root = 0;
29
30        for i in 1..n {
31            let mut j = i - 1;
32
33            loop {
34                if a[i] < a[j] {
35                    if let Some(p) = p[j] {
36                        j = p;
37                        continue;
38                    } else {
39                        p[j] = Some(i);
40                        l[i] = Some(j);
41                        root = i;
42                        break;
43                    }
44                }
45
46                let t = r[j];
47                r[j] = Some(i);
48                p[i] = Some(j);
49                l[i] = t;
50
51                if let Some(t) = t {
52                    p[t] = Some(i);
53                }
54
55                break;
56            }
57        }
58
59        CartesianTree {
60            root,
61            parent: p,
62            left: l,
63            right: r,
64        }
65    }
66}
haar_lib/algo/cartesian_tree.rs

haar_lib/algo/
cartesian_tree.rs
