結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー y_1
提出日時 2026-01-11 16:25:41
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 6,495 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,296 ms
コンパイル使用メモリ 372,976 KB
実行使用メモリ 295,272 KB
最終ジャッジ日時 2026-01-11 16:26:07
合計ジャッジ時間 23,157 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;

#define i128 __int128_t


using U = uint64_t;
const U B = 64;
struct FS {
   U n;
   vector<vector<U>> a;
   vector<int> cnt;
   FS(U n) : n(n) ,cnt(n,0) {
      do a.eb(n = (n + B - 1) / B);
      while(n > 1);
   }
   bool operator[](ll i) const { return a[0][i / B] >> (i % B) & 1; }
   void set(ll i) {
      cnt[i]++;
      if(cnt[i] != 1){return;}
      for(auto& v : a) {
         v[i / B] |= 1ULL << (i % B);
         i /= B;
      }
   }
   void insert(ll i){
      set(i);
   }
   void erase(ll i) {
      cnt[i]--;
      if(cnt[i] != 0){return;}
      for(auto& v : a) {
         v[i / B] &= ~(1ULL << (i % B));
         if(v[i / B]) break;
         i /= B;
      }
   }
   ll next(ll i) {
      rep(h, si(a)) {
         i++;
         if(i / B >= si(a[h])) break;
         U d = a[h][i / B] >> (i % B);
         if(d) {
            i += countr_zero(d);
            while(h--) i = i * B + countr_zero(a[h][i]);
            return i;
         }
         i /= B;
      }
      return n;
   }
   ll prev(ll i) {
      rep(h, si(a)) {
         i--;
         if(i < 0) break;
         U d = a[h][i / B] << (~i % B);
         if(d) {
            i -= countl_zero(d);
            while(h--) i = i * B + __lg(a[h][i]);
            return i;
         }
         i /= B;
      }
      return -1;
   }
};


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

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

    auto del = [&](FS &S, FS &T, int x)->void {
        /*
        auto it = S.find(x);
        if(it != S.begin()){
            auto it2 = it;
            it2--;
            T.insert(*it ^ *it2);
        }
        */
        if(S.next(-1) != x){
           T.erase(x ^ S.prev(x));
        }
        /*
        auto it2 = it;
        it2++;
        if(it2 != S.end()){
            T.insert(*it ^ *it2);
        }
        */
        if(S.prev(1<<20) != x){
            T.erase(x ^ S.next(x));
        }
        if(S.next(-1) != x && S.prev(1<<20) != x){
            T.insert(S.prev(x) ^ S.next(x));
        }
        S.erase(x);
        /*
        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 ^ *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].insert(v_s[i][j] ^ v_s[i][j-1]);
            }
            pref_s[i].insert(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 {
            ll ans = 1LL<<30;
            int r; cin >> r;
            --r;
            if(r / B != 0){
                //ans = *pref_t[r/B-1].begin();
                ans = pref_t[r/B-1].next(-1);
                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]));
                    */
                    if(pref_s[r/B-1].prev(1<<20) != a[i]){
                       ans = min(ans, (pref_s[r/B-1].prev(a[i])) ^ a[i]);
                    }
                    if(pref_s[r/B-1].next(-1) != a[i]){
                       ans = min(ans, (pref_s[r/B-1].next(a[i])) ^ 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 , ll(v[i] ^ v[i+1]));
            }

            cout << ans << endl;
        }
    }
}
0