結果

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

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3423.cc:  No.3423 Minimum Xor Query - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 20000;
const int BN = 20;
const int BUFSIZE = BN * MAX_N;
const int INF = 1 << 30;

/* typedef */

struct Node {
  Node *cs[2];
  Node(): cs() {}
};

/* global variables */

int as[MAX_N];
Node buf[BUFSIZE], *bpt, *root;

/* subroutines */

Node *allocnode() {
  bpt->cs[0] = bpt->cs[1] = nullptr;
  return bpt++;
}

void trie_add(int a) {
  Node *u = root;
  for (int i = BN - 1; i >= 0; i--) {
    int ci = (a >> i) & 1;
    if (u->cs[ci] == nullptr) u->cs[ci] = allocnode();
    u = u->cs[ci];
  }
}

int trie_min(int a) {
  Node *u = root;
  int x = 0;
  for (int i = BN - 1; i >= 0; i--) {
    int ci = (a >> i) & 1;
    if (u->cs[ci] == nullptr) {
      x |= (1 << i);
      u = u->cs[ci ^ 1];
    }
    else
      u = u->cs[ci];
  }
  return x;
}

/* main */

int main() {
  int n, qn;
  scanf("%d%d", &n, &qn);
  for (int i = 0; i < n; i++) scanf("%d", as + i);

  while (qn--) {
    int op;
    scanf("%d", &op);

    if (op == 1) {
      int i, x;
      scanf("%d%d", &i, &x), i--;

      as[i] = x;
    }
    else {
      int r;
      scanf("%d", &r);

      bpt = buf;
      root = allocnode();
      int minx = INF;
      for (int i = 0; i < r; i++) {
	if (i > 0) minx = min(minx, trie_min(as[i]));
	trie_add(as[i]);
      }

      printf("%d\n", minx);
    }
  }
  
  return 0;
}
0