結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー 👑 ArcAki
提出日時 2026-01-08 12:46:08
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 1,653 ms / 5,000 ms
コード長 7,396 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 27,347 ms
コンパイル使用メモリ 412,244 KB
実行使用メモリ 25,616 KB
最終ジャッジ日時 2026-01-11 13:13:48
合計ジャッジ時間 39,747 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

pub trait SegTreeMonoid{
    type S: Clone;
    fn identity() -> Self::S;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
}

pub struct SegTree<M: SegTreeMonoid> {
    n: usize,
    data: Vec<M::S>,
}

impl<M: SegTreeMonoid> SegTree<M> {
    pub fn new(n: usize) -> Self {
        let n = n.next_power_of_two();
        let data = vec![M::identity(); 2 * n];
        SegTree{ n, data }
    }

    pub fn set(&mut self, i: usize, x: M::S) {
        let mut p = i + self.n;
        self.data[p] = x;
        while p > 1 {
            p /= 2;
            self.data[p] = M::op(&self.data[p << 1], &self.data[(p << 1) | 1]);
        }
    }

    pub fn from(a: Vec<M::S>) -> Self{
        let n = a.len().next_power_of_two();
        let mut data = vec![M::identity(); 2*n];
        for (i, v) in a.iter().enumerate(){
            data[i+n] = v.clone();
        }
        for i in (1..n).rev(){
            data[i] = M::op(&data[2*i], &data[2*i+1]);
        }
        SegTree{
            n, data,
        }
    }

    pub fn get(&self, p: usize)->M::S{
        self.data[self.n+p].clone()
    }

    #[inline(always)]
    pub fn push(&mut self, i: usize, x: M::S) {
        let mut p = i + self.n;
        self.data[p] = M::op(&self.data[p], &x);
        while p > 1 {
            p /= 2;
            self.data[p] = M::op(&self.data[p << 1], &self.data[(p << 1) | 1]);
        }
    }

    pub fn prod(&self, l: usize, r: usize) -> M::S {
        let mut p_l = l + self.n;
        let mut p_r = r + self.n;
        let mut res_l = M::identity();
        let mut res_r = M::identity();
        while p_l < p_r {
            if p_l & 1 == 1 {
                res_l = M::op(&res_l, &self.data[p_l]);
                p_l += 1;
            }
            if p_r & 1 == 1 {
                p_r -= 1;
                res_r = M::op(&self.data[p_r], &res_r);
            }
            p_l >>= 1;
            p_r >>= 1;
        }
        M::op(&res_l, &res_r)
    }

    pub fn all_prod(&self)-> M::S {
        self.data[1].clone()
    }

    #[inline(always)]
    pub fn max_right<F>(&self, mut l: usize, f: F) -> usize where F: Fn(&M::S)->bool {
        assert!(f(&M::identity())); // これはバグってくれないと多分デバックが悲惨
        if l == self.n {
            return self.n 
        }
        l += self.n; 
        let mut ac = M::identity();
        while {
            while l % 2 == 0 {
                l >>= 1;
            }
            if !f(&M::op(&ac, &self.data[l])) {
                while l < self.n {
                    l <<= 1;
                    let res = M::op(&ac, &self.data[l]);
                    if f(&res) {
                        ac = res;
                        l += 1;
                    }
                }
                return l - self.n;
            }
            ac = M::op(&ac, &self.data[l]);
            l += 1;
            let z = l as isize;
            (z & -z) != z
        } {}
        self.n
    }

    #[inline(always)]
    pub fn min_left<F>(&self, mut r: usize, f: F) -> usize where F: Fn(&M::S) -> bool {
        assert!(f(&M::identity()));
        if r == 0 {return 0}
        r += self.n;
        let mut ac = M::identity();
        while {
            r -= 1;
            while r > 1 && r % 2 == 1 {
                r >>= 1;
            }
            if !f(&M::op(&self.data[r], &ac)) {
                while r < self.n{
                    r = 2 * r + 1;
                    let res = M::op(&self.data[r], &ac);
                    if f(&res) {
                        ac = res;
                        r -= 1;
                    }
                }
                return r + 1 - self.n;
            }
            ac = M::op(&self.data[r], &ac);
            let z = r as isize;
            z & -z != z
        } {}
        0
    }
}

struct M;
impl SegTreeMonoid for M{
    type S = i32;

    fn identity() -> Self::S {
        0
    }

    fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
        a+b
    }
}

#[inline(always)]
fn remove(x: i32, c: &mut SegTree<M>, re: &mut SegTree<M>){
    let x = x as usize;
    c.push(x, -1);
    if c.get(x)==0{
        let r = c.max_right(x, |&f| f==0);
        let mut l = c.min_left(x, |&f| f==0);
        if l==0{
            if r < 1<<20{
                re.push(x^r ,-1);
            } 
        } else if r < 1<<20{
            l -= 1;
            re.push(l^r, 1);
            re.push(l^x, -1);
            re.push(x^r,-1);
        } else {
            l -= 1;
            re.push(l^x, -1);
        }
    } else {
        re.push(0, -1);
    }
}

#[inline(always)]
fn insert(x: i32, c: &mut SegTree<M>, re: &mut SegTree<M>){
    let x = x as usize;
    if c.get(x)==0{
        let r = c.max_right(x, |&f| f==0);
        let mut l = c.min_left(x, |&f| f==0);
        if l==0{
            if r < 1<<20{
                re.push(x^r ,1);
            } 
        } else if r < 1<<20{
            l -= 1;
            re.push(l^r, -1);
            re.push(l^x, 1);
            re.push(x^r,1);
        } else {
            l -= 1;
            re.push(l^x, 1);
        }
    } else {
        re.push(0, 1);
    }
    c.push(x, 1);
}

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.225/(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 = SegTree::<M>::new(1<<20);
    let mut res = SegTree::<M>::new(1<<21);
    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.max_right(0, |&f| f==0);
    }
    for x in ans{
        println!("{}", x);
    }
}

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