結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー 👑 ArcAki
提出日時 2026-01-22 17:13:30
言語 Rust
(1.92.0 + proconio + num + itertools)
結果
AC  
実行時間 240 ms / 5,000 ms
コード長 7,276 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,369 ms
コンパイル使用メモリ 220,928 KB
実行使用メモリ 25,728 KB
最終ジャッジ日時 2026-01-22 18:55:33
合計ジャッジ時間 24,105 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// 2e5に収まるなら3、そうでないなら4。4だと手元で実行できないので注意
const TREELEVEL: usize = 4;
#[derive(Clone, Debug)]
pub struct Predecessor64{
    d: [[u64; 1<<18]; TREELEVEL],
}

impl Predecessor64 {
    pub fn new()->Self{
        Predecessor64{
            d: [[0; 1<<18]; TREELEVEL],
        }
    }

    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.d[TREELEVEL-1][0]==0
    }

    #[inline(always)]
    pub fn include(&self, p: usize) -> bool {
        self.d[0][p>>6]&1<<(p&63)!=0
    }

    #[inline(always)]
    pub fn insert(&mut self, p: usize){
        for i in 0..TREELEVEL{
            if self.d[i][p>>(6*(i+1))]&1<<((p>>(6*i))&63)==0{
                self.d[i][p>>(6*(i+1))] |= 1<<((p>>(6*i))&63);
            } else {
                return;
            }
        }
    }

    #[inline(always)]
    pub fn remove(&mut self, p: usize){
        if self.d[0][p>>6]&1<<(p&63)==0{return;}
        for i in 0..TREELEVEL{
            self.d[i][p>>(6*(i+1))] ^= 1<<((p>>(6*i))&63);
            if self.d[i][p>>(6*(i+1))]!=0{
                return;
            } 
        }
    }

    #[inline(always)]
    fn ml(r: usize)->u64{
        (1<<r)-1
    }

    #[inline(always)]
    fn mr(l: usize)->u64{
        if l==63{return 0;}
        !((1<<(l+1))-1)
    }

    #[inline(always)]
    fn msb(bit: u64)->usize{
        63-bit.leading_zeros()as usize
    }

    #[inline(always)]
    fn lsb(bit: u64)->usize{
        bit.trailing_zeros()as usize
    }

    //存在しないは!0
    #[inline(always)]
    pub fn prev(&self, mut p: usize)->usize{
        for i in 0..TREELEVEL{
            if Self::ml(p&63)&self.d[i][p>>6]!=0{
                let mut res = ((p>>6)<<6)|Self::msb(self.d[i][p>>6]&Self::ml(p&63));
                for j in (0..i).rev(){
                    res = (res<<6)|Self::msb(self.d[j][res]);
                }
                return res;
            }
            p >>= 6;
        }
        !0
    }

    #[inline(always)]
    pub fn next(&self, mut p: usize)->usize{
        for i in 0..TREELEVEL{
            if Self::mr(p&63)&self.d[i][p>>6]!=0{
                let mut res = ((p>>6)<<6)|Self::lsb(self.d[i][p>>6]&Self::mr(p&63));
                for j in (0..i).rev(){
                    res = (res<<6)|Self::lsb(self.d[j][res]);
                }
                return res;
            }
            p >>= 6;
        }
        !0
    }

    #[inline(always)]
    pub fn inprev(&self, p: usize)->usize{
        if self.include(p){p}
        else {self.prev(p)}
    }

    #[inline(always)]
    pub fn innext(&self, p: usize)->usize{
        if self.include(p){p}
        else {self.next(p)}
    }

    #[inline(always)]
    pub fn min(&self)->usize{
        self.innext(0)
    }

    #[inline(always)]
    pub fn max(&self)->usize{
        self.inprev((1<<TREELEVEL)-1)
    }
}

#[inline(always)]
fn remove(x: i32, fr1: &mut [i32], fr2: &mut [i32], c: &mut Predecessor64, re: &mut Predecessor64){
    let x = x as usize;
    fr1[x] -= 1;
    if fr1[x]==0{
        c.remove(x);
        let r = c.next(x);
        let l = c.prev(x);
        if l==!0{
            if r < 1<<20{
                fr2[x^r] -= 1;
                if fr2[x^r]==0{
                    re.remove(x^r);
                }
            } 
        } else if r < 1<<20{
            if fr2[l^r]==0{
                re.insert(l^r);
            }
            fr2[l^r] += 1;
            fr2[l^x] -= 1;
            if fr2[l^x]==0{
                re.remove(l^x);
            }
            fr2[r^x] -= 1;
            if fr2[r^x]==0{
                re.remove(r^x);
            }
        } else {
            fr2[l^x] -= 1;
            if fr2[l^x] == 0{
                re.remove(l^x);
            }
        }
    } else {
        fr2[0] -= 1;
        if fr2[0]==0{
            re.remove(0);
        }
    }
}

#[inline(always)]
fn insert(x: i32, fr1: &mut [i32], fr2: &mut [i32], c: &mut Predecessor64, re: &mut Predecessor64){
    let x = x as usize;
    if fr1[x]==0{
        let r = c.next(x);
        let l = c.prev(x);
        if l==!0{
            if r < 1<<20{
                if fr2[x^r]==0{
                    re.insert(x^r);
                }
                fr2[x^r] += 1;
            } 
        } else if r < 1<<20{
            fr2[l^r] -= 1;
            if fr2[l^r]==0{
                re.remove(l^r);
            }
            if fr2[l^x]==0{
                re.insert(l^x);
            }
            fr2[l^x] += 1;
            if fr2[r^x]==0{
                re.insert(r^x);
            }
            fr2[r^x] += 1;
        } else {
            if fr2[l^x] == 0{
                re.insert(l^x);
            }
            fr2[l^x] += 1;
        }
        c.insert(x);
    } else {
        if fr2[0]==0{
            re.insert(0);
        }
        fr2[0] += 1;
    }
    fr1[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 = Predecessor64::new();
    let mut res = Predecessor64::new();
    let mut fr1 = vec![0; 1<<20];
    let mut fr2 = vec![0; 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 fr1, &mut fr2, &mut cnt, &mut res);              
                    insert(v, &mut fr1, &mut fr2, &mut cnt, &mut res);
                }
            }
            r += 1;
        }
        while l > left{
            l -= 1;
            remove(a[l], &mut fr1, &mut fr2, &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 fr1, &mut fr2, &mut cnt, &mut res);
                    insert(u, &mut fr1, &mut fr2, &mut cnt, &mut res);
                }
            }
        }
        while l < left{
            insert(a[l], &mut fr1, &mut fr2, &mut cnt, &mut res);
            l += 1;
        }
        ans[idx] = res.min();
    }
    for x in ans{
        println!("{}", x);
    }
}

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