#1143102 (C++23) No.3423 Minimum Xor Query

• 問題: No.3423 Minimum Xor Query
• ユーザー: rogi52
• 提出日時: 2026-01-07 20:11:27
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 2,288 ms / 5,000 ms
• コード長: 15,289 bytes
• コンパイル時間: 4,870 ms
• コンパイル使用メモリ: 365,920 KB
• 実行使用メモリ: 61,648 KB
• 最終ジャッジ日時: 2026-01-11 13:11:37
• 合計ジャッジ時間: 16,226 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 18

ソースコード

#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;
using f128 = __float128;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

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

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T >& a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T >& a) { for(const T& x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

constexpr pair<int, int> dir4[] = {{-1, 0}, {0, -1}, {+1, 0}, {0, +1}};

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }
int Yes() { return print("Yes"); }
int No() { return print("No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
template < class T > constexpr T infty = 0;
template <> constexpr int infty<int> = 1e9;
template <> constexpr int infty<u32> = 1e9;
template <> constexpr i64 infty<i64> = 1e18;
template <> constexpr u64 infty<u64> = 1e18;

namespace bit {
int pop(int x) { return popcount<u32>(x); }
int pop(u32 x) { return popcount<u32>(x); }
int pop(i64 x) { return popcount<u64>(x); }
int pop(u64 x) { return popcount<u64>(x); }
int parity(int x) { return __builtin_parity(x); }
int parity(u32 x) { return __builtin_parity(x); }
int parity(i64 x) { return __builtin_parityll(x); }
int parity(u64 x) { return __builtin_parityll(x); }
int sgn(int x) { return parity(x) ? -1 : +1; }
int sgn(u32 x) { return parity(x) ? -1 : +1; }
int sgn(i64 x) { return parity(x) ? -1 : +1; }
int sgn(u64 x) { return parity(x) ? -1 : +1; }
int top(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(u32 x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(i64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int top(u64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int low(int x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(u32 x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(i64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int low(u64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int ceil(int x) { return bit_ceil<u32>(x); }
}

#line 2 "/Users/korogi/Desktop/cp-cpp/ds/set64.hpp"

// 参考: https://judge.yosupo.jp/submission/170327 by maspy
struct set64 {
    static constexpr u32 B = 64;
    int n, lg;
    vector<vector<u64>> a;
    set64() {}
    set64(int n) : n(n) {
        do { a.emplace_back(n = (n + B - 1) / B); } while(n > 1);
        lg = ssize(a);
    }
    // i in S <=> b[i] = 1
    set64(const vector<int>& b) : set64(ssize(b)) {
        FOR(i, n) a[0][i / B] |= u64(b[i]) << (i % B);
        FOR(h, lg - 1) FOR(i, ssize(a[h])) {
            a[h + 1][i / B] |= u64(bool(a[h][i])) << (i % B);
        }
    }
    void insert(int i) {
        assert(0 <= i and i < n);
        FOR(h, lg) a[h][i / B] |= u64(1) << (i % B), i /= B;
    }
    void erase(int i) {
        assert(0 <= i and i < n);
        u64 x = 0;
        FOR(h, lg) {
            a[h][i / B] &= ~(u64(1) << (i % B));
            a[h][i / B] |= x << (i % B);
            x = bool(a[h][i / B]);
            i /= B;
        }
    }
    bool contains(int i) {
        return a[0][i / B] >> (i % B) & 1;
    }
    int next(int i) {
        assert(i <= n);
        chmax(i, 0);
        FOR(h, lg) {
            if(i / B == ssize(a[h])) break;
            u64 d = a[h][i / B] >> (i % B);
            if(!d) { i = i / B + 1; continue; }
            i += bit::low(d);
            REV(g, h) {
                i *= B;
                i += bit::low(a[g][i / B]);
            }
            return i;
        }
        return n;
    }
    int prev(int i) {
        assert(-1 <= i);
        if(n <= i) i = n - 1;
        FOR(h, lg) {
            if(i == -1) break;
            u64 d = a[h][i / B] << (63 - i % B);
            if(!d) { i = i / B - 1; continue; }
            i -= __builtin_clzll(d);
            REV(g, h) {
                i *= B;
                i += bit::top(a[g][i / B]);
            }
            return i;
        }
        return -1;
    }
};
#line 2 "/Users/korogi/Desktop/cp-cpp/ds/mo.hpp"

template < class AddLeft, class AddRight, class DelLeft, class DelRight, class Answer >
void mo_algo(int n, vector<pair<int, int>> qs, AddLeft add_left, AddRight add_right, DelLeft del_left, DelRight del_right, Answer answer) {
    const int q = ssize(qs);
    const int B = max<int>(1, n / max<double>(1.0, sqrt(q * 2.0 / 3.0)));
    vector<int> ord = iota(q);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        auto [Li, Ri] = qs[i];
        auto [Lj, Rj] = qs[j];
        if(Li / B != Lj / B) return Li < Lj;
        return Li / B & 1 ? Ri < Rj : Ri > Rj;
    });
    int nL = 0, nR = 0;
    for(int i : ord) {
        auto [L, R] = qs[i];
        while(nL > L) add_left (--nL);
        while(nR < R) add_right(nR++);
        while(nL < L) del_left (nL++);
        while(nR > R) del_right(--nR);
        answer(i);
    }
}

template < class AddLeft, class AddRight, class Reset, class Snapshot, class Rollback, class Answer >
void rollback_mo(int n, vector<pair<int, int>> qs, AddLeft add_left, AddRight add_right, Reset reset, Snapshot snapshot, Rollback rollback, Answer answer) {
    const int q = ssize(qs);
    if(q == 0) return;
    const int b_num = sqrt(q);
    const int b_sz = ceil_div(n, b_num);
    vector<vector<int>> qid((n - 1) / b_sz + 1);
    FOR(qi, q) {
        auto [L, R] = qs[qi];
        const int L_id = L / b_sz;
        const int R_id = R / b_sz;
        if(L_id == R_id) {
            snapshot();
            FOR(i, L, R) add_right(i);
            answer(qi);
            rollback();
        } else {
            qid[L_id].push_back(qi);
        }
    }

    FOR(L_id, ssize(qid)) {
        vector<int>& I = qid[L_id];
        if(I.empty()) continue;
        sort(I, [&](const int i, const int j) { return qs[i].second < qs[j].second; });
        int Lmax = 0;
        for(int i : I) chmax(Lmax, qs[i].first);
        reset();
        int l = Lmax, r = Lmax;
        for(int i : I) {
            auto [L, R] = qs[i];
            while(r < R) add_right(r++);
            snapshot();
            while(L < l) add_left(--l);
            answer(i);
            rollback();
            l = Lmax;
        }
    }
}
#line 4 "a.cpp"

namespace std_ex {
template < class T > T pop(std::queue < T >& c) { T x = c.front(); c.pop(); return x; }
template < class T > T pop(std::stack < T >& c) { T x = c.top();   c.pop(); return x; }
template < class T > T pop(std::vector< T >& c) { T x = c.top();   c.pop(); return x; } 
template < class T > T pop(   heap_min< T >& c) { T x = c.top();   c.pop(); return x; }
template < class T > T pop(   heap_max< T >& c) { T x = c.top();   c.pop(); return x; }
}
template < class container > struct erasable {
    using T = typename container::value_type;
    container c, rm_c;

    erasable() {}
    erasable(std::vector< T >& a) : c(a.begin(), a.end()) {}
    void push(T x) { c.push(x); }
    int size() const { return c.size() - rm_c.size(); }
    int empty() { return size() == 0; }
    T pop() { set(); return std_ex::pop(c); }
    T top() { set(); return c.top(); }
    void erase(T x) { rm_c.push(x); }

  private:
    void set() { while(not rm_c.empty() and rm_c.top() == c.top()) rm_c.pop(), c.pop(); }
};

int main() {
    int N = in(), Q = in();
    vector<int> A = in(N);
    vector<pair<int, int>> query;
    vector<vector<int>> B(N);
    vector<int> K(N, 0), pos, V = A;
    FOR(i, N) B[i].push_back(A[i]);
    int c1 = 0, c2 = 0;
    FOR(Q) {
        int t = in();
        if(t == 1) {
            int i = in(), x = in(); i--;
            c1 += 1;
            B[i].push_back(x);
            pos.push_back(i);
            V.push_back(x);
        } else {
            int r = in();
            c2 += 1;
            query.push_back({c1, r});
        }
    }
    unique(V);
    const int M = ssize(V);
    vector<int> I(1 << 20, -1);
    FOR(i, M) I[V[i]] = i;

    vector<int> ans(c2);
    int r = 0;
    erasable<heap_min<int>> T;

    set64 S(M);
    vector<int> F(M, 0);

    auto insert = [&](int x) {
        const int i = I[x];
        if(F[i] == 0) {
            const int pi = S.prev(i);
            const int ni = S.next(i);
            if(pi != -1 and ni != M) T.erase(V[pi] ^ V[ni]);
            if(pi != -1) T.push(V[pi] ^ x);
            if(ni !=  M) T.push(V[ni] ^ x);
            S.insert(i);
        } else {
            T.push(0);
        }
        F[i] += 1;
    };
    auto erase = [&](int x) {
        const int i = I[x];
        F[i] -= 1;
        if(F[i] == 0) {
            S.erase(i);
            const int pi = S.prev(i);
            const int ni = S.next(i);
            if(pi != -1 and ni != M) T.push(V[pi] ^ V[ni]);
            if(pi != -1) T.erase(V[pi] ^ x);
            if(ni !=  M) T.erase(V[ni] ^ x);
        } else {
            T.erase(0);
        }
    };
    auto add_left = [&](int p) {
        const int i = pos[p];
        if(i < r) erase(B[i][K[i]]);
        K[i]--;
        if(i < r) insert(B[i][K[i]]);
    };
    auto del_left = [&](int p) {
        const int i = pos[p];
        if(i < r) erase(B[i][K[i]]);
        K[i]++;
        if(i < r) insert(B[i][K[i]]);
    };
    auto add_right = [&](int i) { insert(B[i][K[i]]); r++; };
    auto del_right = [&](int i) { erase(B[i][K[i]]); r--; };
    auto answer = [&](int i) { ans[i] = T.top(); };
    mo_algo(N, query, add_left, add_right, del_left, del_right, answer);
    print_n(ans);
}