結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー harurun
提出日時 2026-01-11 16:05:12
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,863 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,756 ms
コンパイル使用メモリ 128,500 KB
実行使用メモリ 66,768 KB
最終ジャッジ日時 2026-01-11 16:05:27
合計ジャッジ時間 14,224 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
ゆるしてくれ～
*/

# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

#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.empty() && *(now->one_index.begin())<r){
                res|=(1<<i);
                now=now->one;
            }else{
                assert(!now->zero_index.empty() && *(now->zero_index.begin())<r);
                now=now->zero;
            }
        }else{
            if(!now->zero_index.empty() &&  *(now->zero_index.begin())<r){
                now=now->zero;
            }else{
                res|=(1<<i);
                assert(!now->one_index.empty() && *(now->one_index.begin())<r);
                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]);
        }
    }
    ll min_right=N;
    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]);
                min_right=min(min_right, idx);
            }
        }else{
            ll r;
            cin>>r;
            for(ll j=min_right;j<r;j++){
                ll c=get_min(root, A[j], j);
                seg.set(j, c^A[j]);
            }
            min_right=r;
            ll ans=seg.prod(0,r);
            cout<<ans<<endl;
        }
    }
}
0