#1144402 (Rust) No.3423 Minimum Xor Query

• 問題: No.3423 Minimum Xor Query
• ユーザー: akakimidori
• 提出日時: 2026-01-11 17:34:58
• 言語: Rust (1.92.0 + proconio + num)
• 結果: AC
• 実行時間: 174 ms / 5,000 ms
• コード長: 8,081 bytes
• コンパイル時間: 24,390 ms
• コンパイル使用メモリ: 412,300 KB
• 実行使用メモリ: 69,216 KB
• 最終ジャッジ日時: 2026-01-11 17:35:26
• 合計ジャッジ時間: 26,634 ms
• ジャッジサーバーID （参考情報）: judge6 / judge3

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

コンパイルメッセージ

warning: type alias `Deque` is never used
   --> src/main.rs:136:6
    |
136 | type Deque<T> = VecDeque<T>;
    |      ^^^^^
    |
    = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

ソースコード

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let q: usize = sc.next();
    let mut a: Vec<usize> = sc.next_vec(n);
    let k = 20;
    let size = 1 << k;
    let cond = std::cell::RefCell::new(vec![Map::new(); n]);
    let rmq = std::cell::RefCell::new(SegmentTreePURQ::new(n, size, |a, b| std::cmp::min(*a, *b)));
    let insert = |pos: usize, val: usize| {
        let cond = &mut cond.borrow_mut()[pos];
        *cond.entry(val).or_insert(0) += 1;
        while let Some((&val, &c)) = cond.iter().next() {
            if c == 0 {
                cond.remove(&val);
            } else {
                rmq.borrow_mut().update(pos, val);
                break;
            }
        }
    };
    let delete = |pos: usize, val: usize| {
        let cond = &mut cond.borrow_mut()[pos];
        let po = cond.entry(val).or_insert(0);
        assert!(*po > 0);
        *po -= 1;
        while let Some((&val, &c)) = cond.iter().next() {
            if c == 0 {
                cond.remove(&val);
            } else {
                rmq.borrow_mut().update(pos, val);
                break;
            }
        }
    };
    let seg = std::cell::RefCell::new(vec![(n, size); 2 * size]);
    let set = std::cell::RefCell::new(vec![Set::new(); size]);
    let seg_update = |x: usize, index: usize| {
        assert!(x < size);
        let mut seg = seg.borrow_mut();
        let mut pos = size + x;
        while pos > 1 {
            pos /= 2;
            let (l, r) = (seg[2 * pos], seg[2 * pos + 1]);
            if l.0.max(r.0) < n {
                delete(l.0.max(r.0), l.1 ^ r.1);
            }
        }
        pos = size + x;
        seg[pos] = (index, x);
        while pos > 1 {
            pos /= 2;
            let (l, r) = (seg[2 * pos], seg[2 * pos + 1]);
            if l.0.max(r.0) < n {
                insert(l.0.max(r.0), l.1 ^ r.1);
            }
            seg[pos] = std::cmp::min(l, r);
        }
    };
    let seg_insert = |a: usize, index: usize| {
        assert!(a < size);
        let set = &mut set.borrow_mut()[a];
        if let Some(&x) = set.iter().nth(1) {
            delete(x, 0);
        }
        set.insert(index);
        seg_update(a, *set.iter().next().unwrap());
        if let Some(&x) = set.iter().nth(1) {
            insert(x, 0);
        }
    };
    let seg_delete = |a: usize, index: usize| {
        assert!(a < size);
        let set = &mut set.borrow_mut()[a];
        if let Some(&x) = set.iter().nth(1) {
            delete(x, 0);
        }
        set.remove(&index);
        seg_update(a, set.iter().next().map_or(n, |p| *p));
        if let Some(&x) = set.iter().nth(1) {
            insert(x, 0);
        }
    };
    for (i, &a) in a.iter().enumerate() {
        seg_insert(a, i);
    }
    for _ in 0..q {
        let op = sc.next::<u32>();
        if op == 1 {
            let i = sc.next::<usize>() - 1;
            let x = sc.next::<usize>();
            seg_delete(a[i], i);
            a[i] = x;
            seg_insert(a[i], i);
        } else {
            let r = sc.next::<usize>();
            let ans = rmq.borrow().find(0, r);
            writeln!(out, "{}", ans).ok();
        }
    }
}

// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
    n: usize,
    size: usize,
    data: Vec<T>,
    e: T,
    op: F,
}

impl<T, F> SegmentTreePURQ<T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    pub fn new(n: usize, e: T, op: F) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let data = vec![e.clone(); 2 * size];
        SegmentTreePURQ {
            n,
            size,
            data,
            e,
            op,
        }
    }
    pub fn update_tmp(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        self.data[x + self.size] = v;
    }
    pub fn update_all(&mut self) {
        for i in (1..self.size).rev() {
            self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
        }
    }
    pub fn update(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        let mut x = x + self.size;
        self.data[x] = v;
        x >>= 1;
        while x > 0 {
            self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
            x >>= 1;
        }
    }
    pub fn find(&self, l: usize, r: usize) -> T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.e.clone();
        }
        let mut l = self.size + l;
        let mut r = self.size + r;
        let mut x = self.e.clone();
        let mut y = self.e.clone();
        while l < r {
            if l & 1 == 1 {
                x = (self.op)(&x, &self.data[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = (self.op)(&self.data[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.op)(&x, &y)
    }
    pub fn max_right<P>(&self, l: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&self.e));
        if l == self.n {
            return self.n;
        }
        let mut l = l + self.size;
        let mut sum = self.e.clone();
        while {
            l >>= l.trailing_zeros();
            let v = (self.op)(&sum, &self.data[l]);
            if !f(&v) {
                while l < self.size {
                    l <<= 1;
                    let v = (self.op)(&sum, &self.data[l]);
                    if f(&v) {
                        sum = v;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sum = v;
            l += 1;
            l.count_ones() > 1
        } {}
        self.n
    }
    pub fn min_left<P>(&self, r: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&self.e));
        if r == 0 {
            return 0;
        }
        let mut r = r + self.size;
        let mut sum = self.e.clone();
        while {
            r -= 1;
            while r > 1 && r & 1 == 1 {
                r >>= 1;
            }
            let v = (self.op)(&self.data[r], &sum);
            if !f(&v) {
                while r < self.size {
                    r = 2 * r + 1;
                    let v = (self.op)(&self.data[r], &sum);
                    if f(&v) {
                        sum = v;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sum = v;
            (r & (!r + 1)) != r
        } {}
        0
    }
}
// ---------- end segment tree Point Update Range Query ----------