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

• 問題: No.3265 地元に帰れば天才扱い！
• ユーザー: elphe
• 提出日時: 2025-11-23 11:55:28
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 365 ms / 2,500 ms
• コード長: 5,889 bytes
• コンパイル時間: 25,379 ms
• コンパイル使用メモリ: 396,444 KB
• 実行使用メモリ: 27,088 KB
• 最終ジャッジ日時: 2025-11-23 11:56:11
• 合計ジャッジ時間: 29,247 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

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

ソースコード

use proconio::{fastout, input};

mod mylib {
    pub struct SegmentTree<S: Monoid> {
        container: Vec<Vec<S::T>>,
    }

    pub trait Monoid {
        type T: Clone;
        const DEFAULT: Self::T;
        fn op(a: &Self::T, b: &Self::T) -> Self::T;
    }

    impl<S: Monoid> SegmentTree<S> {
        pub fn update(&mut self, index: usize, value: S::T) {
            self.container[0][index] = value;
            for layer in 1..self.container.len() {
                self.container[layer][index >> layer] = S::op(
                    &self.container[layer - 1][(index >> layer) << 1],
                    &self.container[layer - 1][((index >> layer) << 1) | 1],
                );
            }
        }

        pub fn range_pick_up(&self, mut l: usize, mut r: usize) -> S::T {
            let mut ans_l = S::DEFAULT;
            let mut ans_r = S::DEFAULT;
            for layer in 0..self.container.len() {
                if l >= r {
                    break;
                }
                if (l & 1) == 1 {
                    ans_l = S::op(&ans_l, &self.container[layer][l]);
                    l += 1;
                }
                if (r & 1) == 1 {
                    ans_r = S::op(&self.container[layer][r - 1], &ans_r);
                    // r -= 1;
                }
                l >>= 1;
                r >>= 1;
            }

            S::op(&ans_l, &ans_r)
        }
    }

    impl<S: Monoid> From<Vec<S::T>> for SegmentTree<S> {
        fn from(mut value: Vec<S::T>) -> Self {
            let mut st = Self {
                container: Vec::<Vec<S::T>>::with_capacity(30),
            };
            if value.is_empty() {
                return st;
            }

            value.extend(vec![
                S::DEFAULT;
                value.len().next_power_of_two() - value.len()
            ]);
            st.container.push(value);

            let mut layer: usize = 1;
            while (st.container.last().unwrap().len() >> 1) > 0 {
                st.container
                    .push(vec![S::DEFAULT; st.container.last().unwrap().len() >> 1]);
                for i in 0..st.container.last().unwrap().len() {
                    st.container[layer][i] = S::op(
                        &st.container[layer - 1][i << 1],
                        &st.container[layer - 1][(i << 1) | 1],
                    );
                }
                layer += 1;
            }
            st
        }
    }

    impl<S: Monoid> Into<Vec<S::T>> for SegmentTree<S> {
        fn into(mut self) -> Vec<S::T> {
            self.container.swap_remove(0)
        }
    }

    impl<S: Monoid> std::ops::Index<usize> for SegmentTree<S> {
        type Output = S::T;
        fn index(&self, index: usize) -> &Self::Output {
            &self.container[0][index]
        }
    }
}

struct S64 {}

impl mylib::Monoid for S64 {
    type T = i64;
    const DEFAULT: Self::T = 0;
    fn op(a: &Self::T, b: &Self::T) -> Self::T {
        *a + *b
    }
}

struct S32 {}

impl mylib::Monoid for S32 {
    type T = i32;
    const DEFAULT: Self::T = 0;
    fn op(a: &Self::T, b: &Self::T) -> Self::T {
        *a + *b
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        residents: [(i32, u32, u32); n],
        queries: [(u32, u32, u32, u32)],
    }

    println!("{}", output(solve(prepare(m, residents), queries)));
}

fn prepare(
    m: usize,
    residents: Vec<(i32, u32, u32)>,
) -> (Vec<i32>, Vec<i64>, Vec<(u32, u32, u32)>, i64) {
    let n = residents.len();
    let mut cur_sum = 0;
    let mut residents_info = Vec::with_capacity(n + 1);
    let mut weight_imos = vec![0; m + 2];
    let mut rate = Vec::with_capacity(m + 1);
    rate.push(0);
    residents_info.push((0, 0, 0));
    rate.extend(residents.into_iter().enumerate().map(|(i, (a, l, r))| {
        weight_imos[l as usize] += 1;
        weight_imos[(r + 1) as usize] -= 1;
        cur_sum += a as i64 * ((r + 1) - l) as i64;
        residents_info.push(((i + 1) as u32, l, r));
        a as i64
    }));
    rate.extend(vec![0; m - n]);

    let mut weight = weight_imos.clone();
    for i in 1..=n {
        weight[i] += weight[i - 1];
        cur_sum -= rate[i] as i64 * weight[i] as i64;
    }

    (weight_imos, rate, residents_info, cur_sum)
}

fn solve(
    (weight_imos, rate, mut residents_info, mut cur_sum): (
        Vec<i32>,
        Vec<i64>,
        Vec<(u32, u32, u32)>,
        i64,
    ),
    queries: Vec<(u32, u32, u32, u32)>,
) -> Vec<i64> {
    let mut ans = Vec::with_capacity(queries.len());
    let mut weight_imos_st = mylib::SegmentTree::<S32>::from(weight_imos);
    let mut rate_st = mylib::SegmentTree::<S64>::from(rate);

    for (x, y, u, v) in queries {
        let (pos, l, r) = &mut residents_info[x as usize];
        let rate = rate_st[*pos as usize];
        cur_sum -= rate * ((*r + 1) - *l) as i64;
        cur_sum += rate_st.range_pick_up(*l as usize, (*r + 1) as usize);
        rate_st.update(*pos as usize, 0);
        weight_imos_st.update(*l as usize, weight_imos_st[*l as usize] - 1);
        weight_imos_st.update((*r + 1) as usize, weight_imos_st[(*r + 1) as usize] + 1);
        cur_sum += rate * weight_imos_st.range_pick_up(0, (*pos + 1) as usize) as i64;
        (*pos, *l, *r) = (y, u, v);
        cur_sum -= rate * weight_imos_st.range_pick_up(0, (*pos + 1) as usize) as i64;
        rate_st.update(*pos as usize, rate);
        weight_imos_st.update(*l as usize, weight_imos_st[*l as usize] + 1);
        weight_imos_st.update((*r + 1) as usize, weight_imos_st[(*r + 1) as usize] - 1);
        cur_sum -= rate_st.range_pick_up(*l as usize, (*r + 1) as usize);
        cur_sum += rate * ((*r + 1) - *l) as i64;

        ans.push(cur_sum);
    }
    ans
}

fn output(ans: Vec<i64>) -> String {
    ans.into_iter()
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join("\n")
}