#1145347 (Rust) No.2786 RMQ on Grid Path

• 問題: No.2786 RMQ on Grid Path
• ユーザー: urectanc
• 提出日時: 2026-01-22 19:47:03
• 言語: Rust (1.92.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 563 ms / 6,000 ms
• コード長: 13,288 bytes
• コンパイル時間: 2,947 ms
• コンパイル使用メモリ: 231,036 KB
• 実行使用メモリ: 51,720 KB
• 最終ジャッジ日時: 2026-01-22 19:47:23
• 合計ジャッジ時間: 19,689 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 35

ソースコード

use proconio::{fastout, input, marker::Usize1};

use crate::{
    dsu::Dsu,
    hld::HLD,
    segtree::{Operator, SegmentTree},
};

#[fastout]
fn main() {
    input! {
        h: usize, w: usize,
        a: [[usize; w]; h],
        q: usize,
        queries: [(Usize1, Usize1, Usize1, Usize1); q],
    }

    let idx = |i: usize, j: usize| i * w + j;
    let mut edges = vec![];
    for i in 0..h {
        for j in 0..w {
            if i + 1 < h {
                edges.push((idx(i, j), idx(i + 1, j), a[i][j].max(a[i + 1][j])));
            }
            if j + 1 < w {
                edges.push((idx(i, j), idx(i, j + 1), a[i][j].max(a[i][j + 1])));
            }
        }
    }
    edges.sort_unstable_by_key(|t| t.2);

    let mut dsu = Dsu::new(h * w);
    edges.retain(|&(u, v, _)| {
        !dsu.same(u, v) && {
            dsu.merge(u, v);
            true
        }
    });

    let hld = HLD::from_edges(0, edges.iter().map(|&(u, v, _)| (u, v)));
    let mut seg = SegmentTree::<RangeMax>::new(h * w);
    for &(u, v, w) in &edges {
        let i = hld.edge_index(u, v);
        seg.set(i, w);
    }

    for &(si, sj, ti, tj) in &queries {
        let s = idx(si, sj);
        let t = idx(ti, tj);
        let ans = hld
            .path_edges(s, t)
            .map(|(l, r)| seg.prod(l, r))
            .max()
            .unwrap();
        println!("{ans}");
    }
}

struct RangeMax;

impl Operator for RangeMax {
    type Value = usize;

    fn identity() -> Self::Value {
        0
    }

    fn op(a: &Self::Value, b: &Self::Value) -> Self::Value {
        *a.max(b)
    }
}

#[allow(unused)]
mod dsu {
    pub struct Dsu {
        parent_or_size: Vec<i32>,
    }

    impl Dsu {
        pub fn new(size: usize) -> Self {
            assert!(size <= i32::MAX as usize);
            Self {
                parent_or_size: vec![-1; size],
            }
        }

        pub fn clear(&mut self) {
            self.parent_or_size.fill(-1);
        }

        pub fn leader(&mut self, u: usize) -> usize {
            if self.parent_or_size[u] < 0 {
                return u;
            }
            self.parent_or_size[u] = self.leader(self.parent_or_size[u] as usize) as i32;
            self.parent_or_size[u] as usize
        }

        pub fn same(&mut self, u: usize, v: usize) -> bool {
            self.leader(u) == self.leader(v)
        }

        pub fn size(&mut self, u: usize) -> usize {
            let x = self.leader(u);
            -self.parent_or_size[x] as usize
        }

        pub fn merge(&mut self, u: usize, v: usize) -> usize {
            let (mut x, mut y) = (self.leader(u), self.leader(v));
            if x == y {
                return x;
            }
            if self.size(x) < self.size(y) {
                std::mem::swap(&mut x, &mut y);
            }
            self.parent_or_size[x] += self.parent_or_size[y];
            self.parent_or_size[y] = x as i32;
            x
        }

        pub fn groups(&mut self) -> Vec<Vec<usize>> {
            let n = self.parent_or_size.len();
            let mut result = (0..n)
                .map(|u| {
                    let size = if u == self.leader(u) { self.size(u) } else { 0 };
                    Vec::with_capacity(size)
                })
                .collect::<Vec<_>>();
            for u in 0..n {
                result[self.leader(u)].push(u);
            }
            result.into_iter().filter(|v| !v.is_empty()).collect()
        }
    }
}

#[allow(unused)]
mod hld {
    pub struct HLD {
        parent: Vec<usize>,
        index: Vec<usize>,
        head: Vec<usize>,
        pre_order: Vec<usize>,
        subtree_size: Vec<usize>,
    }

    impl HLD {
        pub fn from_edges(
            root: usize,
            edges: impl ExactSizeIterator<Item = (usize, usize)>,
        ) -> Self {
            let n = edges.len() + 1;
            let mut graph = vec![vec![]; n];
            for (u, v) in edges {
                graph[u].push(v);
                graph[v].push(u);
            }

            let mut pre_order = Vec::with_capacity(n);
            let mut parent = vec![!0; n];
            let mut stack = vec![root];
            while let Some(v) = stack.pop() {
                pre_order.push(v);
                graph[v].retain(|&u| u != parent[v]);
                for &u in &graph[v] {
                    parent[u] = v;
                    stack.push(u);
                }
            }

            let mut subtree_size = vec![1; n];
            for &v in pre_order.iter().rev() {
                if !graph[v].is_empty() {
                    graph[v].select_nth_unstable_by_key(0, |&c| std::cmp::Reverse(subtree_size[c]));
                }
                if v != root {
                    subtree_size[parent[v]] += subtree_size[v];
                }
            }

            let mut index = vec![!0; n];
            let mut head = (0..n).collect::<Vec<_>>();
            pre_order.clear();
            stack.push(root);
            while let Some(v) = stack.pop() {
                index[v] = pre_order.len();
                pre_order.push(v);
                if let Some(&c) = graph[v].first() {
                    head[c] = head[v];
                }
                stack.extend(graph[v].iter().copied().rev());
            }

            Self {
                parent,
                index,
                head,
                pre_order,
                subtree_size,
            }
        }

        pub fn pre_order(&self) -> &'_ [usize] {
            &self.pre_order
        }

        pub fn parent(&self, v: usize) -> Option<usize> {
            Some(self.parent[v]).filter(|&v| v != !0)
        }

        pub fn index(&self, v: usize) -> usize {
            self.index[v]
        }

        pub fn edge_index(&self, u: usize, v: usize) -> usize {
            self.index[u].max(self.index[v])
        }

        pub fn subtree(&self, v: usize) -> (usize, usize) {
            let l = self.index[v];
            (l, l + self.subtree_size[v])
        }

        pub fn is_ancestor(&self, u: usize, v: usize) -> bool {
            let (l, r) = self.subtree(u);
            (l..r).contains(&self.index(v))
        }

        pub fn la(&self, mut v: usize, mut d: usize) -> usize {
            while v != !0 {
                let u = self.head[v];
                if self.index[v] - self.index[u] >= d {
                    v = self.pre_order[self.index[v] - d];
                    break;
                }
                d -= self.index[v] - self.index[u] + 1;
                v = self.parent[u];
            }
            v
        }

        pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
            if self.index(u) > self.index(v) {
                std::mem::swap(&mut u, &mut v);
            }

            if self.is_ancestor(u, v) {
                return u;
            }

            while self.index(u) < self.index(v) {
                v = self.parent[self.head[v]];
            }

            v
        }

        pub fn dist(&self, u: usize, v: usize) -> usize {
            self.path(u, v)
                .map(|(l, r, last)| usize::from(!last) + self.index[r] - self.index[l])
                .sum()
        }

        pub fn path_vertices(
            &self,
            u: usize,
            v: usize,
        ) -> impl Iterator<Item = (usize, usize)> + '_ {
            self.path(u, v)
                .map(|(u, v, _)| (self.index[u], self.index[v] + 1))
        }

        pub fn path_edges(&self, u: usize, v: usize) -> impl Iterator<Item = (usize, usize)> + '_ {
            self.path(u, v)
                .map(|(u, v, last)| (self.index[u] + usize::from(last), self.index[v] + 1))
        }

        fn path(&self, u: usize, v: usize) -> PathSegments<'_> {
            PathSegments {
                hld: self,
                u,
                v,
                exhausuted: false,
            }
        }
    }

    pub struct PathSegments<'a> {
        hld: &'a HLD,
        u: usize,
        v: usize,
        exhausuted: bool,
    }

    impl Iterator for PathSegments<'_> {
        type Item = (usize, usize, bool);

        fn next(&mut self) -> Option<Self::Item> {
            if self.exhausuted {
                return None;
            }

            let Self {
                hld:
                    HLD {
                        parent,
                        index,
                        head,
                        ..
                    },
                u,
                v,
                ..
            } = *self;

            if head[u] == head[v] {
                self.exhausuted = true;
                if index[u] < index[v] {
                    Some((u, v, true))
                } else {
                    Some((v, u, true))
                }
            } else {
                if index[u] < index[v] {
                    self.v = parent[head[v]];
                    Some((head[v], v, false))
                } else {
                    self.u = parent[head[u]];
                    Some((head[u], u, false))
                }
            }
        }
    }
}

#[allow(unused)]
mod segtree {
    pub trait Operator {
        type Value: Clone;

        fn identity() -> Self::Value;
        fn op(a: &Self::Value, b: &Self::Value) -> Self::Value;
    }

    pub struct SegmentTree<O: Operator> {
        n: usize,
        offset: usize,
        value: Vec<O::Value>,
    }

    impl<O: Operator> From<Vec<O::Value>> for SegmentTree<O> {
        fn from(v: Vec<O::Value>) -> Self {
            let n = v.len();
            let offset = n.next_power_of_two();
            let mut value = vec![O::identity(); 2 * offset];
            value[offset..][..n].clone_from_slice(&v);
            let mut ret = Self { n, offset, value };
            for i in (1..offset).rev() {
                ret.update(i);
            }
            ret
        }
    }

    impl<O: Operator> SegmentTree<O> {
        pub fn new(n: usize) -> Self {
            vec![O::identity(); n].into()
        }

        pub fn as_slice(&self) -> &[O::Value] {
            &self.value[self.offset..][..self.n]
        }

        pub fn get(&self, i: usize) -> O::Value {
            debug_assert!(i < self.n);
            self.value[i + self.offset].clone()
        }

        pub fn set(&mut self, mut i: usize, x: O::Value) {
            debug_assert!(i < self.n);
            i += self.offset;
            self.value[i] = x;
            while i > 1 {
                i >>= 1;
                self.update(i);
            }
        }

        pub fn prod(&self, mut l: usize, mut r: usize) -> O::Value {
            debug_assert!(l <= r && r <= self.n);

            l += self.offset;
            r += self.offset;
            let mut prod_l = O::identity();
            let mut prod_r = O::identity();

            while l < r {
                if l & 1 == 1 {
                    prod_l = O::op(&prod_l, &self.value[l]);
                    l += 1;
                }
                if r & 1 == 1 {
                    prod_r = O::op(&self.value[r - 1], &prod_r);
                }
                l >>= 1;
                r >>= 1;
            }

            O::op(&prod_l, &prod_r)
        }

        pub fn all_prod(&self) -> O::Value {
            self.value[1].clone()
        }

        pub fn max_right(&self, l: usize, f: impl Fn(&O::Value) -> bool) -> usize {
            debug_assert!(l <= self.n);
            debug_assert!(f(&O::identity()));

            let mut i = l + self.offset;
            let mut prod = O::identity();

            loop {
                i >>= i.trailing_zeros();
                let next = O::op(&prod, &self.value[i]);
                if !f(&next) {
                    break;
                }
                i += 1;
                prod = next;

                if i & i.wrapping_neg() == i {
                    return self.n;
                }
            }

            while i < self.offset {
                i *= 2;
                let next = O::op(&prod, &self.value[i]);
                if f(&next) {
                    i += 1;
                    prod = next;
                }
            }

            i - self.offset
        }

        pub fn min_left(&self, r: usize, f: impl Fn(&O::Value) -> bool) -> usize {
            debug_assert!(r <= self.n);
            debug_assert!(f(&O::identity()));

            let mut i = r + self.offset;
            let mut prod = O::identity();
            loop {
                i >>= i.trailing_zeros();
                if i > 1 {
                    i -= 1;
                }
                let next = O::op(&self.value[i], &prod);
                if !f(&next) {
                    break;
                }
                prod = next;

                if i & i.wrapping_neg() == i {
                    return 0;
                }
            }
            while i < self.offset {
                i = 2 * i + 1;
                let next = O::op(&self.value[i], &prod);
                if f(&next) {
                    i -= 1;
                    prod = next;
                }
            }
            i + 1 - self.offset
        }

        fn update(&mut self, i: usize) {
            self.value[i] = O::op(&self.value[2 * i], &self.value[2 * i + 1]);
        }
    }
}