結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー syndrome
提出日時 2025-12-24 16:46:59
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3,204 ms / 5,000 ms
コード長 5,744 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,065 ms
コンパイル使用メモリ 364,188 KB
実行使用メモリ 37,800 KB
最終ジャッジ日時 2026-01-11 13:03:15
合計ジャッジ時間 21,358 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// (⁠◕⁠ᴗ⁠◕⁠✿⁠)

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }

#define debug(var)  do{std::cout << #var << " : \n";view(var);}while(0)
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } }

// https://nyaannyaan.github.io/library/misc/mo.hpp.html
//widthの大きさを改造
struct Mo {
    int width;
    vector<int> left, right, order;

    Mo(){}

    void insert(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    void set(int N, int M, int Q){
        order.resize(Q);
        iota(order.begin(), order.end(), 0);
        width = max<int>(1, sqrt(M * N / (double)Q));
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL &add_left, const AR &add_right, const DL &delete_left,
                const DR &delete_right, const REM &rem) {
        assert(left.size() == order.size());
        sort(begin(order), end(order), [&](int a, int b) {
        int ablock = left[a] / width, bblock = left[b] / width;
        if (ablock != bblock) return ablock < bblock;
        if (ablock & 1) return right[a] < right[b];
        return right[a] > right[b];
        });
        int nl = 0, nr = 0;
        for (auto idx : order) {
            while (nl > left[idx]) add_left(--nl, nr);
            while (nr < right[idx]) add_right(nr++);
            while (nl < left[idx]) delete_left(nl++, nr);
            while (nr > right[idx]) delete_right(--nr);
            rem(idx);
        }
    }
};

void solve(vi &A, vc<tuple<int, int, int>> &query){
    int N = len(A), Q = len(query);
    multiset<int> adjacents;
    priority_queue<int, vi, greater<>> candidate, candidate_ng;
    vi version(N, 0);
    vvi versionA(N); rep(i, N) versionA[i].push_back(A[i]);
    vi subQuery;

    Mo mo;
    int one_count = 0, real_Q = 0;
    for (auto [t, a, b] : query){
        if (t == 1){
            one_count++;
            a--;
            versionA[a].push_back(b);
            subQuery.push_back(a);
        }else{
            real_Q++;
            mo.insert(one_count, a);
        }
    }
    mo.set(N, one_count, real_Q);
    vi ans(real_Q);

    auto add = [&](int x){
        auto it = adjacents.lower_bound(x);
        int l = -1, r = -1;
        if (it != adjacents.end()){
            l = *it;
        }
        if (it != adjacents.begin()){
            it--;
            r = *it;
        }
        if (l != -1 && r != -1) candidate_ng.push(l ^ r);
        adjacents.insert(x);
        if (l != -1) candidate.push(l ^ x);
        if (r != -1) candidate.push(r ^ x);
    };

    auto remove = [&](int x){
        auto it = adjacents.lower_bound(x);
        int l = -1, r = -1;
        it++;
        if (it != adjacents.end()){
            r = *it;
        }
        it--;
        if (it != adjacents.begin()){
            it--;
            l = *it;
        }

        adjacents.erase(adjacents.find(x));
        if (l != -1) candidate_ng.push(l ^ x);
        if (r != -1) candidate_ng.push(x ^ r);
        if (l != -1 && r != -1) candidate.push(l ^ r);
    };

    auto add_left = [&](int i, int r){
        int idx = subQuery[i];
        if (idx < r){
            remove(versionA[idx][version[idx]]);
            version[idx]--;
            add(versionA[idx][version[idx]]);
        }else{
            version[idx]--;
        }
    };

    auto delete_left = [&](int i, int r){
        int idx = subQuery[i];
        if (idx < r){
            remove(versionA[idx][version[idx]]);
            version[idx]++;
            add(versionA[idx][version[idx]]);
        }else{
            version[idx]++;
        }
    };

    auto add_right = [&](int i){
        add(versionA[i][version[i]]);
    };

    auto delete_right = [&](int i){
        remove(versionA[i][version[i]]);
    };

    auto rem = [&](int i){
        assert(i < real_Q);
        while (len(candidate) && len(candidate_ng) && candidate.top() == candidate_ng.top()){
            candidate.pop();
            candidate_ng.pop();
        }
        ans[i] = candidate.top();
    };

    mo.run(add_left, add_right, delete_left, delete_right, rem);
    rep(i, real_Q) cout << ans[i] << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q; cin >> N >> Q;
    vi A(N); rep(i, N) cin >> A[i];
    vc<tuple<int, int, int>> query;
    while (Q--){
        int t;cin >> t;
        if (t == 1){
            int i, x; cin >> i >> x;
            query.emplace_back(t, i, x);
        }else{
            int r; cin >> r;
            query.emplace_back(t, r, -1);
        }
    }
    solve(A, query);
}
0