#1149220 (Rust) No.3423 Minimum Xor Query

• 問題: No.3423 Minimum Xor Query
• ユーザー: urectanc
• 提出日時: 2026-02-24 21:13:15
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2,236 ms / 5,000 ms
• コード長: 9,115 bytes
• コンパイル時間: 4,697 ms
• コンパイル使用メモリ: 225,960 KB
• 実行使用メモリ: 11,392 KB
• 最終ジャッジ日時: 2026-02-24 21:13:46
• 合計ジャッジ時間: 21,801 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

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

use crate::bit::BinaryIndexedTree;

#[fastout]
fn main() {
    input! {
        n: usize, q: usize,
        a: [usize; 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: usize }
                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<usize>,
    update: Vec<(usize, usize, usize)>,
    set: MultiSet,
    xor: MultiSet,
}

impl AdjXor {
    fn insert(&mut self, x: usize) {
        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: usize) {
        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 = usize;

    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
    }
}

struct MultiSet {
    len: usize,
    bit: BinaryIndexedTree<i32>,
}

impl std::fmt::Debug for MultiSet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_set()
            .entries(
                self.bit
                    .to_vec()
                    .into_iter()
                    .enumerate()
                    .map(|(i, cnt)| std::iter::repeat_n(i, cnt as usize)),
            )
            .finish()
    }
}

impl MultiSet {
    fn new() -> Self {
        Self {
            len: 0,
            bit: BinaryIndexedTree::new(1 << 20),
        }
    }

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

    fn insert(&mut self, x: usize) {
        self.len += 1;
        self.bit.add(x, 1);
    }

    fn remove(&mut self, x: usize) {
        self.len -= 1;
        self.bit.add(x, -1);
    }

    fn count(&self, x: usize) -> usize {
        self.bit.sum(x..=x) as _
    }

    fn prev(&self, x: usize) -> Option<usize> {
        let cum = self.bit.sum(..x);
        (cum > 0).then(|| self.bit.partition_point(|sum| sum < cum))
    }

    fn next(&self, x: usize) -> Option<usize> {
        let cum = self.bit.sum(..=x);
        (cum < self.len as i32).then(|| self.bit.partition_point(|sum| sum <= cum))
    }

    fn first(&self) -> Option<usize> {
        (self.len > 0).then(|| self.bit.partition_point(|sum| sum == 0))
    }
}

#[allow(unused)]
mod bit {
    use std::ops::{Add, AddAssign, RangeBounds, SubAssign};

    pub struct BinaryIndexedTree<T> {
        n: usize,
        data: Vec<T>,
    }

    impl<T> From<&[T]> for BinaryIndexedTree<T>
    where
        T: Copy + Default + Add<Output = T> + AddAssign + SubAssign + PartialOrd,
    {
        fn from(a: &[T]) -> Self {
            let n = a.len();
            let mut data = Vec::with_capacity(n + 1);
            data.push(T::default());
            data.extend_from_slice(a);

            for i in 1..n {
                let k = i & i.wrapping_neg();
                if i + k <= n {
                    let add = data[i];
                    data[i + (i & i.wrapping_neg())] += add;
                }
            }

            Self { n, data }
        }
    }

    impl<T> BinaryIndexedTree<T>
    where
        T: Copy + Add<Output = T> + Default + AddAssign + SubAssign + PartialOrd,
    {
        pub fn new(n: usize) -> Self {
            Self {
                n,
                data: vec![T::default(); n + 1],
            }
        }

        pub fn to_vec(&self) -> Vec<T> {
            let mut a = self.data.clone();
            for i in (1..self.n).rev() {
                let k = i & i.wrapping_neg();
                if i + k <= self.n {
                    let sub = a[i];
                    a[i + (i & i.wrapping_neg())] -= sub;
                }
            }
            a[1..].to_owned()
        }

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

        pub fn sum(&self, range: impl RangeBounds<usize>) -> T {
            let mut l = match range.start_bound() {
                std::ops::Bound::Included(&l) => l,
                std::ops::Bound::Excluded(&l) => l + 1,
                std::ops::Bound::Unbounded => 0,
            };
            let mut r = match range.end_bound() {
                std::ops::Bound::Included(&r) => r + 1,
                std::ops::Bound::Excluded(&r) => r,
                std::ops::Bound::Unbounded => self.n,
            };

            let mut sum = T::default();
            while l < r {
                sum += self.data[r];
                r -= r & r.wrapping_neg();
            }
            while r < l {
                sum -= self.data[l];
                l -= l & l.wrapping_neg();
            }

            sum
        }

        pub fn partition_point<F>(&self, f: F) -> usize
        where
            F: Fn(T) -> bool,
        {
            let mut r = 0;
            let mut sum = T::default();
            let mut d = self.n.next_power_of_two();
            while d > 0 {
                if r + d <= self.n && f(sum + self.data[r + d]) {
                    sum += self.data[r + d];
                    r += d;
                }
                d >>= 1;
            }
            r
        }
    }
}