結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

template <typename T, typename F> class SegTree
{
private:
  const T e;
  int num;
  std::vector<T> dat;
  F eval;
public:
  SegTree(std::vector<T> &v, T E, F func) : e(E), eval(func)
  {
    int siz = static_cast<int>(v.size());
    for (num = 1; num < siz; num <<= 1);
    dat = std::vector<T> (2 * num - 1, e);
    for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i];
    for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]);
  }
  SegTree(int n, T E, F func) : e(E), eval(func)
  {
    for (num = 1; num < n; num <<= 1);
    dat = std::vector<T> (2 * num - 1, e);
  }
  void update_a(int i, T val)
  {
    for (i += num - 1, dat[i] = val; i != 0;)
    {
      i = (i - 1) / 2;
      dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
  void update_r(int i, T val)
  {
    for (i += num - 1, dat[i] = eval(dat[i], val); i != 0;)
    {
      i = (i - 1) / 2;
      dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
  T getval(int left, int right)
  {
    left = std::max(0, left), right = std::min(num, right);
    T ansl = e, ansr = e;
    for (left += num - 1, right += num - 1; left < right; left >>= 1, right >>= 1)
    {
      if (!(left & 1)) ansl = eval(ansl, dat[left]);
      if (--right & 1) ansr = eval(dat[right], ansr);
    }
    return eval(ansl, ansr);
  }
  T getall() {return dat[0];}
  T getval(int id) {return dat[num - 1 + id];}
  template<typename Fc>
  int maxright(int left, Fc check)
  {
    T now = e;
    int id = left + num - 1;
    while (true)
    {
      T tmp = eval(now, dat[id]);
      if (check(tmp))
      {
        if (id & 1) ++id;
        else
        {
          int tmpid = id + 2;
          if ((tmpid & -tmpid) == tmpid) return num;
          id >>= 1;
        }
        now = tmp;
      }
      else
      {
        if (num - 1 <= id && id < num * 2 - 1) break;
        id = (id << 1) + 1;
      }
    }
    return id - num + 1;
  }
  template<typename Fc>
  int minleft(int right, Fc check)
  {
    if (right == 0) return 0;
    T now = e;
    int id = right + num - 2;
    while (true)
    {
      T tmp = eval(dat[id], now);
      if (check(tmp))
      {
        if (id & 1)
        {
          int tmpid = id + 1;
          if ((tmpid & -tmpid) == tmpid) return 0;
          id = (id >> 1);
        }
        --id;
        now = tmp;
      }
      else
      {
        if (num - 1 <= id && id < num * 2 - 1) break;
        id = (id << 1) + 2;
      }
    }
    return id - num + 2;
  }
};
template <class T, class F>
SegTree(std::vector<T> &, T, F) -> SegTree<T, F>;
template <class T, class F>
SegTree(int, T, F) -> SegTree<T, F>;

array<int, 3> eval(array<int, 3> &a, array<int, 3> &b)
{
  array<int, 3> ret;
  if (a[2] == -1) return b;
  else if (b[2] == -1) return a;
  ret[1] = min(min(a[1], b[1]), (a[2] ^ b[0]));
  ret[0] = min(a[0], b[0]);
  ret[2] = max(a[2], b[2]);
  return ret;
}

int main()
{
  const int ama = (1 << 20);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  array<int, 3> e;
  e[0] = ama;
  e[1] = ama;
  e[2] = -1;
  SegTree sg(ama, e, eval);
  vector<int> cnt(ama);
  int c2 = 0;
  for (int i = 0; i < n; ++i) ++cnt[a[i]];
  for (int i = 0; i < ama; ++i) c2 += (cnt[i] > 1);
  int nowr = n;
  for (int i = 0; i < ama; ++i)
  {
    if (cnt[i])
    {
      array<int, 3> tmp = {i, ama, i};
      sg.update_a(i, tmp);
    }
  }
  auto del = [&](int v) -> void
  {
    if (cnt[v] == 2) --c2;
    --cnt[v];
    if (cnt[v] == 0) sg.update_a(v, e);
  };
  auto add = [&](int v) -> void
  {
    if (cnt[v] == 1) ++c2;
    ++cnt[v];
    if (cnt[v] == 1) sg.update_a(v, array<int, 3>{v, ama, v});
  };
  while (q--)
  {
    int t;
    cin >> t;
    if (t == 1)
    {
      int id, x;
      cin >> id >> x;
      --id;
      del(a[id]);
      a[id] = x;
      add(a[id]);
    }
    else if (t == 2)
    {
      int r;
      cin >> r;
      while (nowr > r)
      {
        del(a[nowr - 1]);
        --nowr;
      }
      while (nowr < r)
      {
        add(a[nowr]);
        ++nowr;
      }
      if (c2 > 0)
      {
        cout << "0\n";
        continue;
      }
      auto res = sg.getall();
      cout << res[1] << '\n';
    }
  }
}
0