結果

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

ソースコード

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

    auto del = [&](multiset<int> &S, multiset<int> &T, int 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.emplace(*it2 ^ *it3);
        }
        S.erase(it);
    };

    vector<vector<int>> v_s((n + B - 1) / B);

    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]);
            v_s[j].push_back(a[i]);
        }
    }

    for(int i = 0; i < (n + B - 1) / B; i++){
        sort(v_s[i].begin(), v_s[i].end());
        for(int j = 0; j < (int)v_s[i].size(); j++){
            if(j != 0){
                pref_t[i].emplace(v_s[i][j] ^ v_s[i][j-1]);
            }
            pref_s[i].emplace(v_s[i][j]);
        }
    }

    while(q--){
        int type; cin >> type;
        if(type == 1){
            int i; cin >> i;
            int 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 {
            int ans = 1LL<<30;
            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]));
                }
            }
            vector<int> v;
            for(int i = r / B * B; i <= r; i++){
                v.push_back(a[i]);
            }
            sort(v.begin(), v.end());
            for(int i = 0; i < (int)v.size() - 1; i++){
                ans = min(ans , v[i] ^ v[i+1]);
            }
            cout << ans << endl;
        }
    }
}
0