結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n,q; cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++)cin >> a[i];
    int B = sqrt(n);

    vector<multiset<ll>> pref_s((n + B - 1) / B);
    vector<multiset<ll>> pref_t((n + B - 1) / B);
    
    auto add = [&](multiset<ll> &S, multiset<ll> &T, ll x)->void {
        S.insert(x);
        auto it = S.find(x);
        if(it != S.begin()){
            auto it2 = it;
            it2--;
            T.insert(*it ^ *it2);
        }
        auto it2 = it;
        it2++;
        if(it2 != S.end()){
            T.insert(*it ^ *it2);
        }
        if(it != S.begin() && it2 != S.end()){
            auto it3 = it;
            it3--;
            T.erase(T.find(*it3 ^ *it2));
        }
    };

    auto del = [&](multiset<ll> &S, multiset<ll> &T, ll x)->void {
        auto it = S.find(x);
        if(it != S.begin()){
            auto it2 = it;
            it2--;
            T.erase(T.find(*it ^ *it2));
        }
        auto it2 = it;
        it2++;
        if(it2 != S.end()){
            T.erase(T.find(*it ^ *it2));
        }
        if(it != S.begin() && it2 != S.end()){
            auto it3 = it;
            it3--;
            T.insert(*it2 ^ *it2);
        }
        S.erase(it);
    };

    for(int i = 0; i < n; i++){
        for(int j = (n + B - 1) / B - 1; i < (j+1) * B; j--){
            if(i < (j+1) * B)add(pref_s[j], pref_t[j], a[i]);
        }
    }

    while(q--){
        int type; cin >> type;
        if(type == 1){
            int i; cin >> i;
            ll x; cin >> x;
            --i;
            for(int j = (n + B - 1) / B - 1; i < (j+1) * B; j--){
                del(pref_s[j], pref_t[j], a[i]);
            }

            a[i] = x;

            for(int j = (n + B - 1) / B - 1; i < (j+1) * B; j--){
                add(pref_s[j], pref_t[j], a[i]);
            }
        }
        else {
            ll ans = 1LL<<60;
            int r; cin >> r;
            --r;
            if(r / B != 0){
                ans = *pref_t[r/B-1].begin();
                for(int i = r / B * B; i <= r; i++){
                    auto it = pref_s[r/B-1].lower_bound(a[i]);
                    if(it != pref_s[r/B-1].end()){
                        ans = min(ans, (*it) ^ (a[i]));
                    }
                    if(it == pref_s[r/B-1].begin())continue;
                    it--;
                    ans = min(ans , (*it) ^ (a[i]));
                }
            }
            multiset<ll> tmp_s;
            multiset<ll> tmp_t;
            for(int i = r / B * B; i <= r; i++){
                add(tmp_s, tmp_t, a[i]);
            }
            if(tmp_t.size() >= 1)ans = min(ans, *tmp_t.begin());
            cout << ans << endl;
        }
    }
}
0