Submit Info #48265

Problem Lang User Status Time Memory
Range Chmin Chmax Add Range Sum rust dalt AC 807 ms 44.17 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
max_random_00 AC 775 ms 43.79 MiB
max_random_01 AC 776 ms 43.79 MiB
max_random_02 AC 766 ms 43.79 MiB
medium_00 AC 2 ms 0.75 MiB
medium_01 AC 2 ms 0.68 MiB
medium_02 AC 2 ms 0.68 MiB
random2_00 AC 674 ms 44.04 MiB
random2_01 AC 669 ms 44.16 MiB
random2_02 AC 670 ms 44.17 MiB
random3_00 AC 801 ms 43.16 MiB
random3_01 AC 795 ms 43.20 MiB
random3_02 AC 807 ms 43.14 MiB
random_00 AC 494 ms 22.80 MiB
random_01 AC 539 ms 41.05 MiB
random_02 AC 326 ms 11.93 MiB
small_00 AC 1 ms 0.68 MiB
small_01 AC 1 ms 0.68 MiB
small_02 AC 0 ms 0.61 MiB
small_03 AC 1 ms 0.68 MiB
small_04 AC 2 ms 0.68 MiB
small_05 AC 0 ms 0.61 MiB
small_06 AC 0 ms 0.67 MiB
small_07 AC 0 ms 0.64 MiB
small_08 AC 1 ms 0.67 MiB
small_09 AC 1 ms 0.68 MiB

//==================header==================== #![allow(dead_code)] #![allow(unused)] #![allow(unused_imports)] #![allow(non_snake_case)] use std::{ cmp::{max, min}, fmt::{Debug, Display}, mem::{self, swap}, ops::{Add, Sub}, }; use std::{ collections::{HashMap, VecDeque}, fmt, io::{self, BufRead, BufReader, BufWriter, Write}, slice, str::{self, FromStr}, }; macro_rules! input { ($reader:expr) => {}; ($reader:expr, ) => {}; ($reader:expr, $var:ident : $t:tt $($r:tt)*) => { let mut $var:$t = $reader.read(); input!{$reader $($r)*} }; } #[cfg(debug_assertions)] macro_rules! debug { ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap()) } #[cfg(debug_assertions)] macro_rules! debugln { ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap()) } #[cfg(not(debug_assertions))] macro_rules! debug { ($($format:tt)*) => {}; } #[cfg(not(debug_assertions))] macro_rules! debugln { ($($format:tt)*) => {}; } //==================main==================== #[derive(Debug)] struct Query { l: usize, r: usize, ans: i64, } fn solve<R, W>(test_case_id: i32, inp: &mut In<R>, out: &mut BufWriter<W>) where R: BufRead, W: Write, { // input!(inp, n:usize, q:usize); // let mut a = vec![0;n]; // for i in 0..n { // a[i] = inp.read(); // } // let mut qs = Vec::with_capacity(q); // for i in 0..q{ // input!(inp, l:usize, r:usize); // qs.push(Query{l: l - 1, r: r - 1, ans:0}); // } // let mut qs_order: Vec<usize> = (0..q).collect(); // qs_order.sort_by(|a, b| qs[*a].l.cmp(&qs[*b].l)); // let mut stb = SegTreeBeatExt::new(n, 2e18 as i64); // stb.init(|i| -a[i]); // let mut b = a.clone(); // prefixsum_prepare(&mut b); // debugln!("a = {:?}", b); // debugln!("qs = {:?}", qs); // debugln!("qs_order = {:?}", qs_order); // for i in (0..n).rev() { // debugln!("i = {}, sbt = {:?}", i, stb); // debugln!("i = {}, n - 1 = {}, -a[i] = {}", i, n - i, -a[i]); // stb.update_min(i, n - 1, -a[i]); // loop { // match qs_order.last() { // Some(x) => { // if(qs[*x].l == i){ // qs[*x].ans = -stb.query_sum(qs[*x].l, qs[*x].r) - prefixsum_interval(&b, qs[*x].l, qs[*x].r); // qs_order.pop(); // }else{ // break; // } // } // None => {break} // } // } // } // for x in qs { // writeln!(out, "{}", x.ans); // } input!(inp, n: usize, q: usize); let mut a: Vec<i64> = vec![0; n]; for i in 0..n { a[i] = inp.read(); } let mut st = SegTreeBeatExt::new(n, 2e18 as i64); st.init(|i| a[i]); for i in 0..q { input!(inp, t: usize, l: usize, r: usize); r -= 1; if (t == 3) { let ans = st.query_sum(l, r); writeln!(out, "{}", ans); continue; } let b: i64 = inp.read(); match t { 0 => { st.update_min(l, r, b); } 1 => { st.update_max(l, r, b); } 2 => { st.update_value(l, r, b); } _ => (), } } } fn run() { let stdin = io::stdin(); let stdout = io::stdout(); let mut inp = In::new(BufReader::new(stdin.lock())); let mut out = BufWriter::new(stdout.lock()); let test_case_num: i32 = 1; for test_case_id in 1..test_case_num + 1 { solve(test_case_id, &mut inp, &mut out); } out.flush(); } fn main() { let thread = std::thread::Builder::new() .stack_size(256 << 20) .spawn(|| run()) .unwrap() .join() .unwrap(); } //==================IO==================== struct In<R> where R: BufRead, { reader: R, line: String, dq: VecDeque<String>, } impl<R> In<R> where R: BufRead, { fn new(reader: R) -> Self { In { reader, line: String::from(""), dq: VecDeque::new(), } } fn read<T>(self: &mut Self) -> T where T: FromStr, { loop { if let Some(token) = self.dq.pop_front() { return token.parse().ok().expect("Failed parse"); } self.line.clear(); self.reader.read_line(&mut self.line).expect("IO error"); let iter = self.line.split_ascii_whitespace(); for token in iter { self.dq.push_back(String::from(token)); } } } } //==================Utils==================== fn ceil_log(x: usize) -> usize { if (x <= 0) { return 0; } return mem::size_of::<usize>() * 8 - ((x - 1).leading_zeros() as usize); } fn floor_log(x: usize) -> usize { return mem::size_of::<usize>() * 8 - 1 - (x.leading_zeros() as usize); } macro_rules! leave { ($L:ident, $R:ident, $l:ident, $r:ident) => { ($R < $l || $L > $r) }; } macro_rules! enter { ($L:ident, $R:ident, $l:ident, $r:ident) => { ($L <= $l && $r <= $R) }; } //==================SegTreeBeatExt==================== #[derive(Debug)] struct SegTreeBeatExt { first_large: Vec<i64>, second_large: Vec<i64>, first_large_cnt: Vec<u32>, first_small: Vec<i64>, second_small: Vec<i64>, first_small_cnt: Vec<u32>, size: Vec<u32>, dirty: Vec<i64>, sum: Vec<i64>, n: usize, m: usize, inf: i64, } impl Drop for SegTreeBeatExt { fn drop(&mut self) {} } impl SegTreeBeatExt { pub fn new(mut n: usize, inf: i64) -> SegTreeBeatExt { let m = 1 << ceil_log(n); let mut res = SegTreeBeatExt { size: vec![0; m * 2], dirty: vec![0; m * 2], sum: vec![0; m * 2], first_large: vec![-inf; m * 2], second_large: vec![-inf; m * 2], first_large_cnt: vec![0; m * 2], first_small: vec![inf; m * 2], second_small: vec![inf; m * 2], first_small_cnt: vec![0; m * 2], n, m, inf, }; res } pub fn init(self: &mut Self, f: impl Fn(usize) -> i64) { for i in 0..self.m + self.m { self.dirty[i] = (0); self.sum[i] = (0); self.first_large[i] = (-self.inf); self.second_large[i] = (-self.inf); self.first_large_cnt[i] = (0); self.first_small[i] = (self.inf); self.second_small[i] = (self.inf); self.first_small_cnt[i] = (0); self.size[i] = (0); } for i in self.m..self.m + self.n { self.sum[i] = f(i - self.m); self.first_large[i] = self.sum[i]; self.first_large_cnt[i] = 1; self.second_large[i] = -self.inf; self.first_small[i] = self.sum[i]; self.second_small[i] = self.inf; self.first_small_cnt[i] = 1; self.size[i] = 1; } for i in (1..self.m).rev() { self.push_up(i); } } fn modify_min(self: &mut Self, root: usize, u: i64) { if (self.first_large[root] <= u) { return; } self.sum[root] -= (self.first_large[root] - u) * self.first_large_cnt[root] as i64; self.first_large[root] = u; if (self.first_small[root] >= u) { self.first_small[root] = u; } self.second_small[root] = i64::min(self.second_small[root], u); if (self.first_small[root] == self.second_small[root]) { self.second_small[root] = self.inf; } } fn modify_max(self: &mut Self, root: usize, u: i64) { if (self.first_small[root] >= u) { return; } self.sum[root] += (u - self.first_small[root]) * self.first_small_cnt[root] as i64; self.first_small[root] = u; if (self.first_large[root] <= u) { self.first_large[root] = u; } self.second_large[root] = i64::max(self.second_large[root], u); if (self.first_large[root] == self.second_large[root]) { self.second_large[root] = -self.inf; } } fn modify_val(self: &mut Self, root: usize, u: i64) { self.dirty[root] += u; self.sum[root] += u * self.size[root] as i64; self.first_small[root] += u; self.first_large[root] += u; self.second_small[root] += u; self.second_large[root] += u; } fn push_up(self: &mut Self, root: usize) { self.sum[root] = self.sum[root * 2] + self.sum[root * 2 + 1]; self.size[root] = self.size[root * 2] + self.size[root * 2 + 1]; //large self.first_large[root] = i64::max(self.first_large[root * 2], self.first_large[root * 2 + 1]); self.second_large[root] = -self.inf; self.first_large_cnt[root] = 0; if (self.first_large[root * 2] != self.first_large[root]) { self.second_large[root] = i64::max(self.second_large[root], self.first_large[root * 2]); } else { self.first_large_cnt[root] += self.first_large_cnt[root * 2]; self.second_large[root] = i64::max(self.second_large[root], self.second_large[root * 2]); } if (self.first_large[root * 2 + 1] != self.first_large[root]) { self.second_large[root] = i64::max(self.second_large[root], self.first_large[root * 2 + 1]); } else { self.first_large_cnt[root] += self.first_large_cnt[root * 2 + 1]; self.second_large[root] = i64::max(self.second_large[root], self.second_large[root * 2 + 1]); } //small self.first_small[root] = i64::min(self.first_small[root * 2], self.first_small[root * 2 + 1]); self.second_small[root] = self.inf; self.first_small_cnt[root] = 0; if (self.first_small[root * 2] != self.first_small[root]) { self.second_small[root] = i64::min(self.second_small[root], self.first_small[root * 2]); } else { self.first_small_cnt[root] += self.first_small_cnt[root * 2]; self.second_small[root] = i64::min(self.second_small[root], self.second_small[root * 2]); } if (self.first_small[root * 2 + 1] != self.first_small[root]) { self.second_small[root] = i64::min(self.second_small[root], self.first_small[root * 2 + 1]); } else { self.first_small_cnt[root] += self.first_small_cnt[root * 2 + 1]; self.second_small[root] = i64::min(self.second_small[root], self.second_small[root * 2 + 1]); } } fn push_down(self: &mut Self, root: usize) { if (self.dirty[root] != 0) { self.modify_val(root * 2, self.dirty[root]); self.modify_val(root * 2 + 1, self.dirty[root]); self.dirty[root] = 0; } self.modify_min(root * 2, self.first_large[root]); self.modify_min(root * 2 + 1, self.first_large[root]); self.modify_max(root * 2, self.first_small[root]); self.modify_max(root * 2 + 1, self.first_small[root]); } pub fn query_sum(self: &mut Self, L: usize, R: usize) -> i64 { self.query_sum_rec(1, L, R, 0, self.m - 1) } fn query_sum_rec(self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize) -> i64 { if (leave!(L, R, l, r)) { return 0; } if (enter!(L, R, l, r)) { return self.sum[root]; } self.push_down(root); let mid = (l + r) / 2; let lson = self.query_sum_rec(root * 2, L, R, l, mid); let rson = self.query_sum_rec(root * 2 + 1, L, R, mid + 1, r); return lson + rson; } pub fn query_max(self: &mut Self, L: usize, R: usize) -> i64 { self.query_max_rec(1, L, R, 0, self.m - 1) } fn query_max_rec(self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize) -> i64 { if (leave!(L, R, l, r)) { return -self.inf; } if (enter!(L, R, l, r)) { return self.first_large[root]; } self.push_down(root); let mid = (l + r) / 2; let lson = self.query_max_rec(root * 2, L, R, l, mid); let rson = self.query_max_rec(root * 2 + 1, L, R, mid + 1, r); return i64::max(lson, rson); } pub fn query_min(self: &mut Self, L: usize, R: usize) -> i64 { self.query_min_rec(1, L, R, 0, self.m - 1) } fn query_min_rec(self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize) -> i64 { if (leave!(L, R, l, r)) { return self.inf; } if (enter!(L, R, l, r)) { return self.first_small[root]; } self.push_down(root); let mid = (l + r) / 2; let lson = self.query_min_rec(root * 2, L, R, l, mid); let rson = self.query_min_rec(root * 2 + 1, L, R, mid + 1, r); return i64::min(lson, rson); } pub fn update_min(self: &mut Self, L: usize, R: usize, u: i64) { self.update_min_rec(1, L, R, 0, self.m - 1, u) } //x = min(x, u) fn update_min_rec( self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize, u: i64, ) { if (leave!(L, R, l, r)) { return; } if (enter!(L, R, l, r)) { if (self.first_large[root] <= u) { return; } if (self.second_large[root] < u) { self.modify_min(root, u); return; } } self.push_down(root); let mid = (l + r) / 2; self.update_min_rec(root * 2, L, R, l, mid, u); self.update_min_rec(root * 2 + 1, L, R, mid + 1, r, u); self.push_up(root); } pub fn update_max(self: &mut Self, L: usize, R: usize, u: i64) { self.update_max_rec(1, L, R, 0, self.m - 1, u) } //x = max(x, u) fn update_max_rec( self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize, u: i64, ) { if (leave!(L, R, l, r)) { return; } if (enter!(L, R, l, r)) { if (self.first_small[root] >= u) { return; } if (self.second_small[root] > u) { self.modify_max(root, u); return; } } self.push_down(root); let mid = (l + r) / 2; self.update_max_rec(root * 2, L, R, l, mid, u); self.update_max_rec(root * 2 + 1, L, R, mid + 1, r, u); self.push_up(root); } pub fn update_value(self: &mut Self, L: usize, R: usize, u: i64) { self.update_value_rec(1, L, R, 0, self.m - 1, u) } //x = min(x, u) fn update_value_rec( self: &mut Self, root: usize, L: usize, R: usize, l: usize, r: usize, u: i64, ) { if (leave!(L, R, l, r)) { return; } if (enter!(L, R, l, r)) { self.modify_val(root, u); return; } self.push_down(root); let mid = (l + r) / 2; self.update_value_rec(root * 2, L, R, l, mid, u); self.update_value_rec(root * 2 + 1, L, R, mid + 1, r, u); self.push_up(root); } } //==================PrefixSum==================== pub fn prefixsum_prepare<T: Add<Output = T> + Copy>(a: &mut Vec<T>) { for i in 1..a.len() { a[i] = a[i] + a[i - 1]; } } pub fn prefixsum_interval<T: Sub<Output = T> + Copy>(a: &Vec<T>, l: usize, r: usize) -> T { let mut res = a[r]; if l > 0 { res = res - a[l - 1]; } return res; }