結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー areik
提出日時 2026-01-11 16:01:52
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,228 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,873 ms
コンパイル使用メモリ 239,364 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-11 16:02:22
合計ジャッジ時間 12,685 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
次のファイルから読み込み:  /usr/local/gcc-15/include/c++/15.2.0/cassert:46,
         次から読み込み:  /usr/include/atcoder/segtree.hpp:5,
         次から読み込み:  main.cpp:2:
In member function ‘int atcoder::segtree<S, op, e>::max_right(int, F) const [with F = _main()::<lambda(i64)>; S = long long int; auto op = op; auto e = e]’,
    inlined from ‘void _main()’ at main.cpp:98:30:
/usr/include/atcoder/segtree.hpp:74:9: 警告: ‘r’ may be used uninitialized [-Wmaybe-uninitialized]
   74 |         assert(f(e()));
      |         ^~~~~~
main.cpp: In function ‘void _main()’:
main.cpp:98:13: 備考: ‘r’ はここで定義されています
   98 |         i64 r = seg.max_right(x1 + 1, [&](i64 x){return x > r;});
      |             ^

ソースコード

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};
  }
  atcoder::segtree<i64, op, e> seg(vs.size());
  for (i64 i = 0; i < vs.size(); i++) seg.set(i, n);
  for (i64 i = 0; i < n; i++) {
    seg.set(a[i], i);
  }
  vector<bool> c(n, true);
  atcoder::segtree<i64, op, e> seg1(n);
  for (i64 bi = 0; bi * B < q; bi++) {
    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], n);
      c[j] = false;
    }
    for (i64 i = 0; i < n; i++) {
      if (!c[i]) {
        seg1.set(i, e());
        continue;
      }
      i64 l = seg.min_left(a[i], [&](i64 x){return x > i;}) - 1;
      i64 cur = 1e18;
      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, _] = query[i];
      if (op == 1) 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;
        i64 l = seg.min_left(x1, [&](i64 x){return x > r;}) - 1;
        if (l >= 0) ans = min(ans, vs[x1].first ^ vs[l].first);
        i64 r = seg.max_right(x1 + 1, [&](i64 x){return x > r;});
        if (r < vs.size()) ans = min(ans, vs[x1].first ^ vs[r].first);
        seg.set(x1, j1);
      }
      for (i64 ii = bi * B; ii < i; ii++) {
        auto [op1, j1, x1] = query[ii];
        if (op1 == 2) continue;
        if (j1 > r) continue;
        seg.set(x1, n);
      }
      cout << ans << "\n";
    }
    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], n);
      c[j] = 1, a[j] = x;
      seg.set(a[j], j);
    }
  }
}
0