結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー areik
提出日時 2026-01-11 16:24:32
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,929 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,733 ms
コンパイル使用メモリ 236,512 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 16:24:50
合計ジャッジ時間 17,494 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/segtree.hpp>
#include <atcoder/lazysegtree.hpp>
#include <atcoder/modint.hpp>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using f64 = double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

i64 op(i64 a, i64 b) {return min(a, b);}
i64 e() {return 1e18;}
void _main() {
  i64 n, q;
  cin >> n >> q;
  vector<i64> a(n);
  vector<p2> vs;
  for (i64 i = 0; i < n; i++) {
    cin >> a[i];
    vs.push_back({a[i], i});
  }
  i64 B = max(1ll, (i64)sqrt(q));
  vector<el> query(q);
  for (i64 qi = 0; qi < q; qi++) {
    i64 op;
    cin >> op;
    if (op == 1) {
      i64 i, x;
      cin >> i >> x;
      i--;
      query[qi] = {op, i, x};
      vs.push_back({x, n + qi});
    } else {
      i64 r;
      cin >> r;
      r--;
      query[qi] = {op, r, -1};
    }
  }
  sort(vs.begin(), vs.end());
  for (i64 i = 0; i < n; i++) {
    a[i] = lower_bound(vs.begin(), vs.end(), (p2){a[i], i}) - vs.begin();
  }
  for (i64 i = 0; i < q; i++) {
    auto [op, j, x] = query[i];
    if (op == 2) continue;
    x = lower_bound(vs.begin(), vs.end(), (p2){x, n + i}) - vs.begin();
    query[i] = {op, j, x};
  }
  for (i64 bi = 0; bi * B < q; bi++) {
    vector<bool> c(n, true);
    vector<i64> mx(n, -1);
    atcoder::segtree<i64, op, e> seg(vs.size());
    atcoder::segtree<i64, op, e> seg1(n);
    for (i64 i = 0; i < n; i++) {
      seg.set(a[i], i);
    }
    for (i64 i = bi * B; i < min(q, bi * B + B); i++) {
      auto [op, j, x] = query[i];
      if (op == 2) continue;
      seg.set(a[j], e());
      c[j] = false;
    }
    for (i64 i = 0; i < n; i++) {
      if (!c[i]) continue;
      i64 cur = 1e18;
      i64 l = seg.min_left(a[i], [&](i64 x){return x >= i;}) - 1;
      if (l >= 0) cur = min(cur, vs[a[i]].first ^ vs[l].first);
      i64 r = seg.max_right(a[i] + 1, [&](i64 x){return x >= i;});
      if (r < vs.size()) cur = min(cur, vs[a[i]].first ^ vs[r].first);
      seg1.set(i, cur);
    }
    for (i64 i = bi * B; i < min(q, bi * B + B); i++) {
      auto [op, R, xx] = query[i];
      i64 rr = get<1>(query[i]);
      if (op == 1) {
        seg.set(xx, R);
        a[R] = xx;
        continue;
      }
      i64 ans = seg1.prod(0, R + 1);
      for (i64 ii = bi * B; ii < i; ii++) {
        auto [op1, j1, x1] = query[ii];
        if (op1 == 2) continue;
        if (j1 > R) continue;
        if (a[j1] != x1) continue;
        i64 l = seg.min_left(x1, [&](i64 x){return x > rr;}) - 1;
        if (l >= 0) ans = min(ans, vs[x1].first ^ vs[l].first);
        i64 r = seg.max_right(x1 + 1, [&](i64 x){return x > rr;});
        if (r < vs.size()) ans = min(ans, vs[x1].first ^ vs[r].first);
        seg.set(x1, j1);
      }
      cout << ans << "\n";
    }
  }
}
0