#1149219 (Rust) No.3423 Minimum Xor Query

• 問題: No.3423 Minimum Xor Query
• ユーザー: urectanc
• 提出日時: 2026-02-24 20:42:22
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 3,572 ms / 5,000 ms
• コード長: 6,396 bytes
• コンパイル時間: 3,172 ms
• コンパイル使用メモリ: 230,392 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-02-24 20:43:10
• 合計ジャッジ時間: 33,231 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 18

ソースコード

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

use crate::multiset::MultiSet;

#[fastout]
fn main() {
    input! {
        n: usize, q: usize,
        a: [u32; n],
    }

    let mut update = vec![];
    let mut mo_queries = vec![];
    {
        let mut a = a.clone();
        for _ in 0..q {
            input! { op: u8 }
            if op == 1 {
                input! { i: Usize1, x: u32 }
                update.push((i, a[i], x));
                a[i] = x;
            } else {
                input! { r: usize }
                mo_queries.push((update.len(), r));
            }
        }
    }

    let data = AdjXor {
        a,
        update,
        set: MultiSet::new(),
        xor: MultiSet::new(),
    };

    let ans = mo::solve(data, &mo_queries);
    println!("{}", ans.iter().join("\n"));
}

struct AdjXor {
    a: Vec<u32>,
    update: Vec<(usize, u32, u32)>,
    set: MultiSet,
    xor: MultiSet,
}

impl AdjXor {
    fn insert(&mut self, x: u32) {
        if self.set.count(x) > 0 {
            self.xor.insert(0);
        } else {
            match (self.set.prev(x), self.set.next(x)) {
                (None, None) => (),
                (None, Some(next)) => self.xor.insert(next ^ x),
                (Some(prev), None) => self.xor.insert(prev ^ x),
                (Some(prev), Some(next)) => {
                    self.xor.remove(prev ^ next);
                    self.xor.insert(prev ^ x);
                    self.xor.insert(next ^ x);
                }
            }
        }
        self.set.insert(x);
    }

    fn remove(&mut self, x: u32) {
        self.set.remove(x);
        if self.set.count(x) > 0 {
            self.xor.remove(0);
        } else {
            match (self.set.prev(x), self.set.next(x)) {
                (None, None) => (),
                (None, Some(next)) => self.xor.remove(next ^ x),
                (Some(prev), None) => self.xor.remove(prev ^ x),
                (Some(prev), Some(next)) => {
                    self.xor.insert(prev ^ next);
                    self.xor.remove(prev ^ x);
                    self.xor.remove(next ^ x);
                }
            }
        }
    }
}

impl mo::Mo for AdjXor {
    type Result = u32;

    fn increment_x(&mut self, x: usize) {
        let (i, old, new) = self.update[x];
        if i < self.set.len() {
            self.remove(old);
            self.insert(new);
        }
        self.a[i] = new;
    }

    fn decrement_x(&mut self, x: usize) {
        let (i, old, new) = self.update[x];
        if i < self.set.len() {
            self.remove(new);
            self.insert(old);
        }
        self.a[i] = old;
    }

    fn increment_y(&mut self, y: usize) {
        self.insert(self.a[y]);
    }

    fn decrement_y(&mut self, y: usize) {
        self.remove(self.a[y]);
    }

    fn query(&self) -> Self::Result {
        self.xor.first().unwrap()
    }
}

#[allow(unused)]
mod mo {
    pub trait Mo {
        type Result: Clone + Default;

        fn increment_x(&mut self, x: usize);
        fn decrement_x(&mut self, x: usize);
        fn increment_y(&mut self, y: usize);
        fn decrement_y(&mut self, y: usize);
        fn query(&self) -> Self::Result;
    }

    pub fn solve<M: Mo>(mut data: M, queries: &[(usize, usize)]) -> Vec<M::Result> {
        let q = queries.len();
        let x_max = queries.iter().map(|&(x, _)| x).max().unwrap() as f64;
        let y_max = queries.iter().map(|&(_, y)| y).max().unwrap() as f64;
        let is_segment = queries.iter().all(|&(x, y)| x <= y);

        let coeff = if is_segment { 2.0 } else { 1.0 } / 3.0;
        let bucket_num = (coeff * q as f64 * x_max / y_max).sqrt();
        let bucket_width = (x_max / bucket_num).ceil() as usize;

        let mut sorted = queries.into_iter().copied().enumerate().collect::<Vec<_>>();
        sorted.sort_unstable_by_key(|&(_, (x, y))| (x / bucket_width, y));
        sorted
            .chunk_by_mut(|&(_, (x0, _)), &(_, (x1, _))| x0 / bucket_width == x1 / bucket_width)
            .skip(1)
            .step_by(2)
            .for_each(|bucket| bucket.reverse());

        let mut ans = vec![M::Result::default(); q];
        let (mut x, mut y) = (0, 0);
        for (i, (qx, qy)) in sorted {
            while qx < x {
                x -= 1;
                data.decrement_x(x);
            }
            while y < qy {
                data.increment_y(y);
                y += 1;
            }
            while x < qx {
                data.increment_x(x);
                x += 1;
            }
            while qy < y {
                y -= 1;
                data.decrement_y(y);
            }

            ans[i] = data.query();
        }

        ans
    }
}

#[allow(unused)]
mod multiset {
    use std::collections::BTreeMap;

    pub struct MultiSet {
        len: usize,
        map: BTreeMap<u32, usize>,
    }

    impl std::fmt::Debug for MultiSet {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            f.debug_set()
                .entries(
                    self.map
                        .iter()
                        .flat_map(|(&k, &v)| std::iter::repeat_n(k, v)),
                )
                .finish()
        }
    }

    impl MultiSet {
        pub fn new() -> Self {
            Self {
                len: 0,
                map: BTreeMap::new(),
            }
        }

        pub fn len(&self) -> usize {
            self.len
        }

        pub fn insert(&mut self, x: u32) {
            self.len += 1;
            *self.map.entry(x).or_insert(0) += 1;
        }

        pub fn remove(&mut self, x: u32) {
            self.len -= 1;
            *self.map.get_mut(&x).unwrap() -= 1;
            if self.count(x) == 0 {
                self.map.remove(&x);
            }
        }

        pub fn count(&self, x: u32) -> usize {
            *self.map.get(&x).unwrap_or(&0)
        }

        pub fn prev(&self, x: u32) -> Option<u32> {
            self.map.range(..x).last().map(|(&k, _)| k)
        }

        pub fn next(&self, x: u32) -> Option<u32> {
            self.map.range(x + 1..).next().map(|(&k, _)| k)
        }

        pub fn first(&self) -> Option<u32> {
            self.map.first_key_value().map(|(&k, _)| k)
        }

        pub fn last(&self) -> Option<u32> {
            self.map.last_key_value().map(|(&k, _)| k)
        }
    }
}