#1119186 (Rust) No.3265 地元に帰れば天才扱い！

• 問題: No.3265 地元に帰れば天才扱い！
• ユーザー: urectanc
• 提出日時: 2025-09-06 14:50:33
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 521 ms / 2,500 ms
• コード長: 10,887 bytes
• コンパイル時間: 19,249 ms
• コンパイル使用メモリ: 384,512 KB
• 実行使用メモリ: 30,624 KB
• 最終ジャッジ日時: 2025-09-06 14:51:14
• 合計ジャッジ時間: 32,573 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 21

ソースコード

use bit::BinaryIndexedTree;
use lazy_segtree::{LazySegmentTree, Operator};
use proconio::{input, marker::Usize1};
use std::io::Write;

fn main() {
    input! {
        n: usize, m: usize,
        mut alr: [(i64, Usize1, usize); n],
        q: usize,
        queries: [(Usize1, Usize1, Usize1, usize); q],
    }
    let mut stdout = std::io::BufWriter::new(std::io::stdout().lock());

    let mut pos = (0..n).collect::<Vec<_>>();
    let mut bit_sum = BinaryIndexedTree::new(m, 0);
    let mut init = vec![0; m + 1];

    for (i, &(a, l, r)) in alr.iter().enumerate() {
        bit_sum.add(i, a);
        init[l] += 1;
        init[r] -= 1;
    }
    for i in 0..m {
        init[i + 1] += init[i];
    }

    let mut seg_cover = LazySegmentTree::<O>::from(init);

    let mut score = 0;
    for &(a, l, r) in &alr {
        let sum = bit_sum.sum(l, r);
        score += a * (r - l) as i64 - sum;
    }

    for &(x, to, u, v) in &queries {
        let (a, l, r) = alr[x];
        let from = pos[x];
        pos[x] = to;

        score -= a * (r - l) as i64;
        alr[x] = (a, u, v);
        score += a * (v - u) as i64;

        let sum = bit_sum.sum(l, r);
        score += sum;
        bit_sum.add(from, -a);
        bit_sum.add(to, a);
        let sum = bit_sum.sum(u, v);
        score -= sum;

        seg_cover.apply_range(l, r, -1);
        let cover = seg_cover.get(from);
        score += cover * a;
        let cover = seg_cover.get(to);
        score -= cover * a;
        seg_cover.apply_range(u, v, 1);

        writeln!(stdout, "{score}").unwrap();
    }
}

struct O;

impl Operator for O {
    type Value = i64;
    type Map = i64;

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

    fn identity_map() -> Self::Map {
        0
    }

    fn op(_a: &Self::Value, _b: &Self::Value) -> Self::Value {
        0
    }

    fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value {
        *x + *f
    }

    fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map {
        *f + *g
    }
}

#[allow(dead_code)]
mod bit {
    pub struct BinaryIndexedTree<T> {
        n: usize,
        array: Vec<T>,
        e: T,
    }

    impl<T> BinaryIndexedTree<T>
    where
        T: Clone + std::ops::AddAssign + std::ops::Sub<Output = T> + std::cmp::PartialOrd,
    {
        pub fn new(n: usize, e: T) -> Self {
            Self {
                n,
                array: vec![e.clone(); n + 1],
                e,
            }
        }

        pub fn add(&mut self, i: usize, x: T) {
            let mut i = i + 1;
            while i <= self.n {
                self.array[i] += x.clone();
                i += i & i.wrapping_neg();
            }
        }

        pub fn cum(&self, mut i: usize) -> T {
            let mut cum = self.e.clone();
            while i > 0 {
                cum += self.array[i].clone();
                i -= i & i.wrapping_neg();
            }
            cum
        }

        pub fn sum(&self, l: usize, r: usize) -> T {
            self.cum(r) - self.cum(l)
        }

        pub fn lower_bound(&self, mut x: T) -> usize {
            let mut i = 0;
            let mut k = 1 << (self.n.next_power_of_two().trailing_zeros());
            while k > 0 {
                if i + k <= self.n && self.array[i + k] < x {
                    x = x - self.array[i + k].clone();
                    i += k;
                }
                k >>= 1;
            }
            i
        }
    }
}

#[allow(dead_code)]
mod lazy_segtree {
    pub trait Operator {
        type Value: Clone;
        type Map: Clone;

        fn identity() -> Self::Value;
        fn identity_map() -> Self::Map;
        fn op(a: &Self::Value, b: &Self::Value) -> Self::Value;
        fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value;
        fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map;
    }

    pub struct LazySegmentTree<O: Operator> {
        n: usize,
        offset: usize,
        height: usize,
        value: Vec<O::Value>,
        map: Vec<O::Map>,
    }

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

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

        pub fn as_slice(&mut self) -> &[O::Value] {
            for i in 1..self.offset {
                self.push(i);
            }
            &self.value[self.offset..][..self.n]
        }

        pub fn get(&mut self, i: usize) -> O::Value {
            debug_assert!(i < self.n);
            let i = i + self.offset;
            for k in (1..=self.height).rev() {
                self.push(i >> k);
            }
            self.value[i].clone()
        }

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

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

            for k in (1..=self.height).rev() {
                if ((l >> k) << k) != l {
                    self.push(l >> k);
                }
                if ((r >> k) << k) != r {
                    self.push(r >> k);
                }
            }

            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 apply(&mut self, i: usize, f: O::Map) {
            debug_assert!(i < self.n);
            let i = i + self.offset;
            for k in (1..=self.height).rev() {
                self.push(i >> k);
            }
            self.value[i] = O::apply(&f, &self.value[i]);
            for k in 1..=self.height {
                self.update(i >> k);
            }
        }

        pub fn apply_range(&mut self, l: usize, r: usize, f: O::Map) {
            debug_assert!(l <= r && r <= self.n);
            let (l, r) = (l + self.offset, r + self.offset);

            for k in (1..=self.height).rev() {
                if ((l >> k) << k) != l {
                    self.push(l >> k);
                }
                if ((r >> k) << k) != r {
                    self.push(r >> k);
                }
            }

            {
                let (mut l, mut r) = (l, r);
                while l < r {
                    if l & 1 == 1 {
                        self.all_apply(l, &f);
                        l += 1;
                    }
                    if r & 1 == 1 {
                        self.all_apply(r - 1, &f);
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }

            for k in 1..=self.height {
                if ((l >> k) << k) != l {
                    self.update(l >> k);
                }
                if ((r >> k) << k) != r {
                    self.update(r >> k);
                }
            }
        }

        pub fn max_right(&mut 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;

            for k in (1..=self.height).rev() {
                self.push(i >> k);
            }

            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 {
                self.push(i);
                i *= 2;
                let next = O::op(&prod, &self.value[i]);
                if f(&next) {
                    i += 1;
                    prod = next;
                }
            }
            i - self.offset
        }

        pub fn min_left(&mut 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;

            for k in (1..=self.height).rev() {
                self.push((i - 1) >> k);
            }

            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 {
                self.push(i);
                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]);
        }

        fn all_apply(&mut self, i: usize, f: &O::Map) {
            self.value[i] = O::apply(f, &self.value[i]);
            if i < self.offset {
                self.map[i] = O::compose(f, &self.map[i]);
            }
        }

        fn push(&mut self, i: usize) {
            let f = std::mem::replace(&mut self.map[i], O::identity_map());
            self.all_apply(2 * i, &f);
            self.all_apply(2 * i + 1, &f);
        }
    }
}