結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー harurun
提出日時 2026-01-11 15:04:27
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 2,291 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,776 ms
コンパイル使用メモリ 193,228 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-11 15:04:50
合計ジャッジ時間 4,982 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <iostream>
#include <utility>
#include <set>
#include <atcoder/segtree>
#include <assert.h>

using namespace std;
using ll=long long;

ll e(){
    return 1LL<<60;
}

ll op(ll a, ll b){
    return min(a,b);
}

struct S{
    set<ll> zero_index, one_index;
    S* zero;
    S* one;
};

void add(S* now, ll x, ll index){
    for(ll i=30;i>=0;i--){
        if((x>>i)&1){
            now->one_index.insert(index);
            if(now->one==nullptr){
                now->one=new S();
            }
            now=now->one;
        }else{
            now->zero_index.insert(index);
            if(now->zero==nullptr){
                now->zero=new S();
            }
            now=now->zero;
        }
    }
}

void erase(S* now, ll x, ll index){
    for(ll i=30;i>=0;i--){
        if((x>>i)&1){
            now->one_index.erase(index);
            now=now->one;
        }else{
            now->zero_index.erase(index);
            now=now->zero;
        }
    }
}

ll get_min(S* now, ll x, ll r){
    ll res=0;
    for(ll i=30;i>=0;i--){
        if((x>>i)&1){
            if(*(now->one_index.begin())<r){
                res|=(1<<i);
                now=now->one;
            }else{
                now=now->zero;
            }
        }else{
            if(*(now->zero_index.begin())<r){
                now=now->zero;
            }else{
                res|=(1<<i);
                now=now->one;
            }
        }
    }
    return res;
}

int main(){
    ll N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    for(ll i=0;i<N;i++){
        cin>>A[i];
    }
    S* root=new S();
    atcoder::segtree<ll,op,e> seg(N);
    for(ll i=0;i<N;i++){
        add(root, A[i], i);
        if(i>0){
            ll c=get_min(root, A[i], i);
            seg.set(i, c^A[i]);
        }
  }
    for(ll i=0;i<Q;i++){
        ll t;
        cin>>t;
        if(t==1){
            ll idx, x;
            cin>>idx>>x;
            idx--;
            erase(root, A[idx], idx);
            A[idx]=x;
            add(root, A[idx], idx);
            if(idx>0){
                ll c=get_min(root, A[idx], idx);
                seg.set(idx, c^A[idx]);
            }
        }else{
            ll r;
            cin>>r;
            ll ans=seg.prod(0,r);
            cout<<ans<<endl;
        }
    }
}
0