結果

問題 No.776 A Simple RMQ Problem
ユーザー Haar
提出日時 2025-04-10 23:49:41
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 17,091 bytes
コンパイル時間 13,901 ms
コンパイル使用メモリ 388,124 KB
実行使用メモリ 14,596 KB
最終ジャッジ日時 2025-04-10 23:50:14
合計ジャッジ時間 20,850 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> src/main.rs:54:29
   |
54 |                         let mut ret = seg.fold(l1..l2).right_max
   |                             ----^^^
   |                             |
   |                             help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

ソースコード

diff #

// Bundled at 2025/04/10 23:49:21 +09:00
// Author: Haar

pub mod main {
    use super::*;
    #[allow(unused_imports)]
    use haar_lib::{get, input, io::fastio::*, iter::join_str::*};
    #[allow(unused_imports)]
    use std::cell::{Cell, RefCell};
    #[allow(unused_imports)]
    use std::cmp::{max, min, Reverse};
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::mem::swap;
    #[allow(unused_imports)]
    use std::rc::Rc;
    #[derive(Clone, Default)]
    pub struct Problem {}
    use haar_lib::algebra::max_partial_sum::*;
    use haar_lib::ds::segtree::*;
    impl Problem {
        pub fn init() -> Self {
            Self {}
        }
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            let mut io = FastIO::new();
            let n = io.read_usize();
            let q = io.read_usize();
            let m = MaxPartialSum::<i64>::new();
            let mut seg = Segtree::new(n, m);
            let mut a = get!(io, [i64; n]);
            for i in 0..n {
                seg.assign(i, MaxPartialSumValue::new(a[i]));
            }
            for _ in 0..q {
                let query = io.read_bytes();
                if query == b"set" {
                    let i = io.read_usize() - 1;
                    let x = io.read_i64();
                    seg.assign(i, MaxPartialSumValue::new(x));
                    a[i] = x;
                } else {
                    let l1 = io.read_usize() - 1;
                    let l2 = io.read_usize() - 1;
                    let r1 = io.read_usize() - 1;
                    let r2 = io.read_usize() - 1;
                    let r1 = r1.max(l1);
                    let l2 = l2.min(r2);
                    let mut ans = i64::MIN;
                    let f = |l1, l2, r1, r2| {
                        let mut ret = seg.fold(l1..l2).right_max
                            + seg.fold(min(l2, r1)..r1 + 1).sum
                            + seg.fold(r1 + 1..r2 + 1).left_max;
                        ret
                    };
                    if l2 <= r1 {
                        ans = f(l1, l2, r1, r2);
                    } else {
                        if l1 <= r1 {
                            ans = ans.max(f(l1, r1, r1, r2));
                        }
                        if l2 <= r2 {
                            ans = ans.max(f(l1, l2, l2, r2));
                        }
                        if r1 <= l2 {
                            ans = ans.max(seg.fold(r1..l2 + 1).partial_max);
                        }
                    }
                    io.writeln(ans);
                }
            }
            Ok(())
        }
    }
}
fn main() {
    main::Problem::init().main().unwrap();
}
use crate as haar_lib;
pub mod algebra {
    pub mod traits {
        use crate::trait_alias;
        pub trait Set {
            type Element;
        }
        pub trait BinaryOp: Set {
            fn op(&self, _: Self::Element, _: Self::Element) -> Self::Element;
        }
        pub trait Identity: Set {
            fn id(&self) -> Self::Element;
        }
        pub trait Inverse: Set {
            fn inv(&self, _: Self::Element) -> Self::Element;
        }
        pub trait Commutative {}
        pub trait Associative {}
        pub trait Idempotence {}
        trait_alias!(#[doc = "半群"]Semigroup:BinaryOp+Associative);
        trait_alias!(#[doc = "モノイド"]Monoid:Semigroup+Identity);
        trait_alias!(#[doc = "可換モノイド"]AbelianMonoid:Monoid+Commutative);
        trait_alias!(#[doc = "群"]Group:Monoid + Inverse);
        trait_alias!(#[doc = "可換群"]AbelianGroup:Group+Commutative);
        pub trait Times: BinaryOp + Identity
        where
            Self::Element: Clone,
        {
            fn times(&self, mut a: Self::Element, mut n: u64) -> Self::Element {
                let mut ret = self.id();
                while n > 0 {
                    if n & 1 == 1 {
                        ret = self.op(ret, a.clone());
                    }
                    a = self.op(a.clone(), a);
                    n >>= 1;
                }
                ret
            }
        }
        impl<A: BinaryOp + Identity> Times for A where Self::Element: Clone {}
    }
    pub mod max_partial_sum {
        pub use crate::algebra::traits::*;
        use crate::max;
        use crate::num::one_zero::Zero;
        use std::marker::PhantomData;
        use std::ops::Add;
        #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
        pub struct MaxPartialSumValue<T> {
            pub sum: T,
            pub left_max: T,
            pub right_max: T,
            pub partial_max: T,
        }
        impl<T: Copy> MaxPartialSumValue<T> {
            pub fn new(value: T) -> Self {
                Self {
                    sum: value,
                    left_max: value,
                    right_max: value,
                    partial_max: value,
                }
            }
        }
        #[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
        pub struct MaxPartialSum<T>(PhantomData<T>);
        impl<T> MaxPartialSum<T> {
            pub fn new() -> Self {
                Self(PhantomData)
            }
        }
        impl<T> Set for MaxPartialSum<T> {
            type Element = MaxPartialSumValue<T>;
        }
        impl<T: Copy + Zero> Identity for MaxPartialSum<T> {
            fn id(&self) -> Self::Element {
                MaxPartialSumValue::new(T::zero())
            }
        }
        impl<T: Copy + Ord + Add<Output = T>> BinaryOp for MaxPartialSum<T> {
            fn op(&self, a: Self::Element, b: Self::Element) -> Self::Element {
                MaxPartialSumValue {
                    sum: a.sum + b.sum,
                    left_max: a.left_max.max(a.sum + b.left_max),
                    right_max: b.right_max.max(b.sum + a.right_max),
                    partial_max: max!(a.partial_max, b.partial_max, a.right_max + b.left_max),
                }
            }
        }
        impl<T> Associative for MaxPartialSum<T> {}
    }
}
pub mod ds {
    pub mod segtree {
        pub use crate::algebra::traits::Monoid;
        use crate::misc::range::range_bounds_to_range;
        use std::ops::{Index, RangeBounds};
        #[derive(Clone)]
        pub struct Segtree<M: Monoid> {
            original_size: usize,
            size: usize,
            data: Vec<M::Element>,
            monoid: M,
        }
        impl<M: Monoid> Segtree<M>
        where
            M::Element: Clone,
        {
            pub fn new(n: usize, monoid: M) -> Self {
                let size = n.next_power_of_two() * 2;
                Segtree {
                    original_size: n,
                    size,
                    data: vec![monoid.id(); size],
                    monoid,
                }
            }
            pub fn fold<R: RangeBounds<usize>>(&self, range: R) -> M::Element {
                let (l, r) = range_bounds_to_range(range, 0, self.size / 2);
                let mut ret_l = self.monoid.id();
                let mut ret_r = self.monoid.id();
                let mut l = l + self.size / 2;
                let mut r = r + self.size / 2;
                while l < r {
                    if r & 1 == 1 {
                        r -= 1;
                        ret_r = self.monoid.op(self.data[r].clone(), ret_r);
                    }
                    if l & 1 == 1 {
                        ret_l = self.monoid.op(ret_l, self.data[l].clone());
                        l += 1;
                    }
                    r >>= 1;
                    l >>= 1;
                }
                self.monoid.op(ret_l, ret_r)
            }
            pub fn assign(&mut self, i: usize, value: M::Element) {
                let mut i = i + self.size / 2;
                self.data[i] = value;
                while i > 1 {
                    i >>= 1;
                    self.data[i] = self
                        .monoid
                        .op(self.data[i << 1].clone(), self.data[(i << 1) | 1].clone());
                }
            }
            pub fn update(&mut self, i: usize, value: M::Element) {
                self.assign(
                    i,
                    self.monoid.op(self.data[i + self.size / 2].clone(), value),
                );
            }
        }
        impl<M: Monoid> From<&Segtree<M>> for Vec<M::Element>
        where
            M::Element: Clone,
        {
            fn from(from: &Segtree<M>) -> Self {
                from.data[from.size / 2..from.size / 2 + from.original_size].to_vec()
            }
        }
        impl<M: Monoid> Index<usize> for Segtree<M> {
            type Output = M::Element;
            fn index(&self, i: usize) -> &Self::Output {
                &self.data[self.size / 2 + i]
            }
        }
    }
}
pub mod io {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }
            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                let c = *self.in_bytes.get(self.in_cur)?;
                self.in_cur += 1;
                Some(c)
            }
            #[inline]
            pub fn peek(&self) -> Option<u8> {
                Some(*self.in_bytes.get(self.in_cur)?)
            }
            #[inline]
            pub fn skip(&mut self) {
                while self.peek().is_some_and(|c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }
            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().is_some_and(|c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }
            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }
            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }
            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().is_some_and(|c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }
            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }
            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }
            pub fn read_f64(&mut self) -> f64 {
                self.read_chars()
                    .into_iter()
                    .collect::<String>()
                    .parse()
                    .unwrap()
            }
            pub fn read_chars(&mut self) -> Vec<char> {
                self.skip();
                let mut ret = vec![];
                while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur] as char);
                    self.in_cur += 1;
                }
                ret
            }
            pub fn read_bytes(&mut self) -> Vec<u8> {
                self.skip();
                let mut ret = vec![];
                while self.peek().is_some_and(|c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur]);
                    self.in_cur += 1;
                }
                ret
            }
            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
            }
            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(b"\n").unwrap();
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
}
pub mod iter {
    pub mod join_str {
        pub trait JoinStr: Iterator {
            fn join_str(self, s: &str) -> String
            where
                Self: Sized,
                Self::Item: ToString,
            {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
        impl<I> JoinStr for I where I: Iterator + ?Sized {}
    }
}
pub mod macros {
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
        }
    };
    ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in, $type $(as $to)*)),*)
    };
    ( $in:ident, i8 ) => { $in.read_i64() as i8 };
    ( $in:ident, i16 ) => { $in.read_i64() as i16 };
    ( $in:ident, i32 ) => { $in.read_i64() as i32 };
    ( $in:ident, i64 ) => { $in.read_i64() };
    ( $in:ident, isize ) => { $in.read_i64() as isize };
    ( $in:ident, u8 ) => { $in.read_u64() as u8 };
    ( $in:ident, u16 ) => { $in.read_u64() as u16 };
    ( $in:ident, u32 ) => { $in.read_u64() as u32 };
    ( $in:ident, u64 ) => { $in.read_u64() };
    ( $in:ident, usize ) => { $in.read_u64() as usize };
    ( $in:ident, [char] ) => { $in.read_chars() };
    ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };
    ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
        let mut $name = get!($in, $type as $to);
    };
    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };
    ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
        let $name = get!($in, $type as $to);
    };
    ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
        $(input!(@inner $in, $($names)* : $type $(as $to)*);)*
    }
}
    }
    pub mod max_min {
        #[macro_export]
        macro_rules! max {
    ($x:expr, $($xs:expr),*) => {
        {
            let mut ret = $x;
            for &x in &[$($xs),*] {
                if x > ret {
                    ret = x
                }
            }
            ret
        }
    }
}
        #[macro_export]
        macro_rules! min {
    ($x:expr, $($xs:expr),*) => {
        {
            let mut ret = $x;
            for &x in &[$($xs),*] {
                if x < ret {
                    ret = x
                }
            }
            ret
        }
    }
}
    }
    pub mod trait_alias {
        #[macro_export]
        macro_rules! trait_alias {
    ($(#[$meta:meta])* $name:ident: $($t:tt)+) => {
        $(#[$meta])*
        pub trait $name : $($t)+ {}
        impl<T: $($t)+> $name for T {}
    };
}
    }
}
pub mod misc {
    pub mod range {
        use std::ops::RangeBounds;
        pub fn range_bounds_to_range<R: RangeBounds<usize>>(
            r: R,
            start: usize,
            end: usize,
        ) -> (usize, usize) {
            use std::ops::Bound::*;
            let l = match r.start_bound() {
                Included(&l) => l,
                Excluded(&l) => l + 1,
                Unbounded => start,
            }
            .max(start);
            let r = match r.end_bound() {
                Included(&r) => r + 1,
                Excluded(&r) => r,
                Unbounded => end,
            }
            .min(end);
            (l, r)
        }
    }
}
pub mod num {
    pub mod one_zero {
        pub trait Zero {
            fn zero() -> Self;
        }
        pub trait One {
            fn one() -> Self;
        }
        macro_rules! impl_one_zero {
    ($($t:ty),*) => {
        $(
            impl Zero for $t {
                fn zero() -> Self { 0 as $t }
            }
            impl One for $t {
                fn one() -> Self { 1 as $t }
            }
        )*
    }
}
        impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64);
    }
}
0