結果

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

ソースコード

diff #
raw source code 

# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#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 = 800;

    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);
        }
        */
        int px = S.prev(x);
        int nx = S.next(x);
        int n1 = S.next(-1);
        int pp = S.prev(1<<20);
        if(n1 != x){
           T.insert(x ^ px);
        }
        /*
        auto it2 = it;
        it2++;
        if(it2 != S.end()){
            T.insert(*it ^ *it2);
        }
        */
        if(pp != x){
            T.insert(x ^ nx);
        }
        if(n1 != x && pp != x){
            T.erase(px ^ nx);
        }
    };

    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);
        }
        */
        int px = S.prev(x);
        int nx = S.next(x);
        int n1 = S.next(-1);
        int pp = S.prev(1<<20);
        if(n1 != x){
           T.erase(x ^ px);
        }
        /*
        auto it2 = it;
        it2++;
        if(it2 != S.end()){
            T.insert(*it ^ *it2);
        }
        */
        if(pp != x){
            T.erase(x ^ nx);
        }
        if(n1 != x && pp != x){
            T.insert(px ^ nx);
        }
        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);
        */
    };

    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;
            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]);
                    }
                }
            }
            FS tmp_s(1<<20);
            FS tmp_t(1<<20);
            for(int i = r / B * B; i <= r; i++){
                add(tmp_s, tmp_t, a[i]);
            }
            if(tmp_t.next(0) != (1<<20)){
                ans = min(ans, tmp_t.next(-1));
            }

            //if(tmp_t.size() >= 1)ans = min(ans, *tmp_t.begin());
            cout << ans << endl;
        }
    }
}
0