#1143146 (Rust) No.3423 Minimum Xor Query

• 問題: No.3423 Minimum Xor Query
• ユーザー: 👑 ArcAki
• 提出日時: 2026-01-08 08:51:31
• 言語: Rust (1.92.0 + proconio + num)
• 結果: AC
• 実行時間: 4,677 ms / 5,000 ms
• コード長: 6,097 bytes
• コンパイル時間: 27,051 ms
• コンパイル使用メモリ: 414,392 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-01-11 13:13:09
• 合計ジャッジ時間: 73,291 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

use proconio::{input, marker::Usize1, fastout};
use std::{collections::{BTreeMap, btree_map::Range as BTreeRange}, ops::RangeBounds};

#[derive(Debug, Clone)]
pub struct Counter<T: Ord>{
    c: usize,
    map: BTreeMap<T, usize>,
}

impl<T: Copy+Ord> Counter<T>{
    pub fn new()->Self{
        Counter{
            c: 0,
            map: BTreeMap::new(),
        }
    }

    #[inline(always)]
    pub fn range<R>(&self, range: R)->BTreeRange<'_, T, usize> where R: RangeBounds<T>{
        self.map.range(range)
    }

    #[inline(always)]
    pub fn mi(&self)->Option<T>{
        if let Some((x, _)) = self.range(..).next(){
            Some(*x)
        } else {
            None
        }
    }

    #[inline(always)]
    pub fn mx(&self)->Option<T>{
        if let Some((x, _)) = self.range(..).next_back(){
            Some(*x)
        } else {
            None
        }
    }

    #[inline(always)]
    pub fn one_add(&mut self, x: T){
        *self.map.entry(x).or_insert(0) += 1;
        self.c += 1;
    }

    #[inline(always)]
    pub fn one_sub(&mut self, x: T){
        if !self.map.contains_key(&x){return}
        let e = self.map.entry(x).or_insert(0);
        *e = e.saturating_sub(1);
        if self.map[&x] <= 0{
            self.map.remove(&x);
        }
        self.c = self.c.saturating_sub(1);
    }

    #[inline(always)]
    pub fn one_update(&mut self, x: T, y: T){
        self.one_sub(x);
        self.one_add(y);
    }

    #[inline(always)]
    pub fn del(&mut self, x: T){
        self.c = self.c.saturating_sub(*self.map.get(&x).unwrap_or(&0));
        self.map.remove(&x);
    }

    #[inline(always)]
    pub fn add(&mut self, x: T, c: usize){
        *self.map.entry(x).or_insert(0) += c;
        self.c += c;
    }

    #[inline(always)]
    pub fn sub(&mut self, x: T, c: usize){
        let e = self.map.entry(x).or_insert(0);
        *e = e.saturating_sub(c);
        if self.map[&x] == 0{
            self.map.remove(&x);
        }
        self.c = self.c.saturating_sub(c);
    }

    #[inline(always)]
    pub fn include(&self, x: T)->bool{
        self.map.contains_key(&x)
    }

    #[inline(always)]
    pub fn cnt(&self, x: T)->usize{
        *self.map.get(&x).unwrap_or(&0)
    }

    #[inline(always)]
    pub fn is_empty(&self)->bool{
        self.map.is_empty()
    }

    #[inline(always)]
    pub fn len(&self)->usize{
        self.map.len()
    }

    #[inline(always)]
    pub fn clear(&mut self){
        self.map.clear();
        self.c = 0;
    }

    #[inline(always)]
    pub fn merge(&mut self, rhs: &mut Counter<T>){
        if self.len() < rhs.len(){
            std::mem::swap(self, rhs);
        }
        for (&k, &v) in rhs.map.iter(){
            self.add(k, v);
        }
        rhs.clear();
    }
}

#[inline(always)]
fn remove(x: i32, c: &mut Counter<i32>, re: &mut Counter<i32>){
    c.one_sub(x);
    if c.cnt(x)==0{
        let &r = c.range(x..).next().unwrap_or((&(1<<20), &1)).0;
        let &l = c.range(..x).next_back().unwrap_or((&(-1), &1)).0;
        if l==-1{
            if r < 1<<20{
                re.one_sub(x^r);
            } 
        } else if r < 1<<20{
            re.one_add(l^r);
            re.one_sub(l^x);
            re.one_sub(x^r);
        } else {
            re.one_sub(l^x);
        }
    } else {
        re.one_sub(0);
    }
}

#[inline(always)]
fn insert(x: i32, c: &mut Counter<i32>, re: &mut Counter<i32>){
    if c.cnt(x)==0{
        let &r = c.range(x..).next().unwrap_or((&(1<<20), &1)).0;
        let &l = c.range(..x).next_back().unwrap_or((&(-1), &1)).0;
        if l==-1{
            if r < 1<<20{
                re.one_add(x^r);
            } 
        } else if r < 1<<20{
            re.one_sub(l^r);
            re.one_add(l^x);
            re.one_add(x^r);
        } else {
            re.one_add(l^x);
        }
    } else {
        re.one_add(0);
    }
    c.one_add(x);
}

const MULTI: bool = false;
#[fastout]
fn solve(){
    input!{
        n: usize, q: usize,
        mut a: [i32; n],
    }
    let mut pre = a.clone();
    let mut query = vec![(!0, -1, -1); q];
    let mut qs = Vec::new();
    for i in 0..q{
        input!{
            t: u8,
        }
        if t==1 {
            input!{
                p: Usize1, x: i32,
            }
            query[i] = (p, pre[p], x);
            pre[p] = x;
        } else {
            input!{
                r: usize,
            }
            qs.push((r, i));
        }
    }
    let div = (n as f64*2.35/(q as f64).sqrt()).ceil() as usize;
    let mut ord = (0..qs.len()).collect::<Vec<_>>();
    ord.sort_unstable_by(|&u, &v| (qs[u].0/div).cmp(&(qs[v].0/div)).then(if qs[u].0/div%2==0{
        qs[u].1.cmp(&qs[v].1)
    } else {
        qs[v].1.cmp(&qs[u].1)
    }));
    let mut ans = vec![0; qs.len()];
    let mut cnt = Counter::new();
    let mut res = Counter::new();
    let (mut l, mut r) = (0, 0);
    for idx in ord{
        let (left, right) = (qs[idx].0, qs[idx].1);
        while r < right{
            if query[r].0!=!0{
                let (p, u, v) = query[r];
                a[p] = v;
                if p < l{
                    remove(u, &mut cnt, &mut res);              
                    insert(v, &mut cnt, &mut res);
                }
            }
            r += 1;
        }
        while l > left{
            l -= 1;
            remove(a[l], &mut cnt, &mut res);
        }
        while r > right{
            r -= 1;
            if query[r].0!=!0{
                let (p, u, v) = query[r];
                a[p] = u;
                if p < l{
                    remove(v, &mut cnt, &mut res);
                    insert(u, &mut cnt, &mut res);
                }
            }
        }
        while l < left{
            insert(a[l], &mut cnt, &mut res);
            l += 1;
        }
        ans[idx] = *res.range(..).next().unwrap().0;
    }
    for x in ans{
        println!("{}", x);
    }
}

//#[fastout]
fn main() {
    if MULTI{
        input!{
            t: usize,
        }
        for _ in 0..t{
            solve();
        }
    } else {
        solve();
    }
}