結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー kidodesu
提出日時 2026-01-03 18:15:48
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 4,428 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,002 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 277,336 KB
最終ジャッジ日時 2026-01-11 13:09:40
合計ジャッジ時間 17,261 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import *
hq0 = []
hq1 = []
cnt_0 = 0
N = 1 << 20
Binary_Tree = [0] * (N*2)

def add(x):
    rep_l, rep_r = -1, -1
    if Binary_Tree[N+x]:
        Binary_Tree[N+x] += 1
        global cnt_0
        cnt_0 += 1
    else:
        back = 0
        now = N+x
        while now:
            if now & 1 and Binary_Tree[now-1]:
                now = now-1
                back = 1
                break
            else:
                now >>= 1
        if back:
            while now < N:
                nxt0 = now << 1; nxt1 = nxt0+1
                if Binary_Tree[nxt1]:
                    now = nxt1
                else:
                    now = nxt0
            rep_l = now-N
            back = 0
        now = N+x
        while now:
            if not now & 1 and Binary_Tree[now+1]:
                now = now+1
                back = 1
                break
            else:
                now >>= 1
        if back:
            while now < N:
                nxt0 = now << 1; nxt1 = nxt0+1
                if Binary_Tree[nxt0]:
                    now = nxt0
                else:
                    now = nxt1
            rep_r = now-N
        if rep_l != -1 and rep_r != -1:
            heappush(hq1, rep_l^rep_r)
        if rep_l != -1:
            heappush(hq0, rep_l^x)
        if rep_r != -1:
            heappush(hq0, x^rep_r)
        now = N+x
        while now:
            Binary_Tree[now] += 1
            now >>= 1

def erase(x):
    rep_l, rep_r = -1, -1
    if Binary_Tree[N+x]-1:
        Binary_Tree[N+x] -= 1
        global cnt_0
        cnt_0 -= 1
    else:
        now = N+x
        while now:
            Binary_Tree[now] -= 1
            now >>= 1
        back = 0
        now = N+x
        while now:
            if now & 1 and Binary_Tree[now-1]:
                now = now-1
                back = 1
                break
            else:
                now >>= 1
        if back:
            while now < N:
                nxt0 = now << 1; nxt1 = nxt0+1
                if Binary_Tree[nxt1]:
                    now = nxt1
                else:
                    now = nxt0
            rep_l = now-N
            back = 0
        now = N+x
        while now:
            if not now & 1 and Binary_Tree[now+1]:
                now = now+1
                back = 1
                break
            else:
                now >>= 1
        if back:
            while now < N:
                nxt0 = now << 1; nxt1 = nxt0+1
                if Binary_Tree[nxt0]:
                    now = nxt0
                else:
                    now = nxt1
            rep_r = now-N
        if rep_l != -1 and rep_r != -1:
            heappush(hq0, rep_l^rep_r)
        if rep_l != -1:
            heappush(hq1, rep_l^x)
        if rep_r != -1:
            heappush(hq1, x^rep_r)

n, q = map(int, input().split())
A = list(map(int, input().split()))
A_ = [A[i] for i in range(n)]
q0 = q1 = 0
Q = [list(map(int, input().split())) for _ in range(q)]
Q_ = []
T = []
for i in range(q):
    if Q[i][0] == 1:
        Q[i][1] -= 1
        T.append((Q[i][1], A_[Q[i][1]], Q[i][2]))
        A_[Q[i][1]] = Q[i][2]
        q0 += 1
    else:
        Q_.append((q0, Q[i][1], q1))
        q1 += 1
Ans = [-1] * q1

b_siz = int((n*q0/q1) ** 0.5) + 1
b_cnt = n // b_siz + 1
D = [[] for _ in range(b_cnt)]
for i in range(q1):
    t, r, idx = Q_[i]
    D[r//b_siz].append((t, r, idx))
for i in range(b_cnt):
    if i % 2:
        D[i].sort(reverse = True)
    else:
        D[i].sort()

nt = nr = 0
for nd in D:
    for t, r, ans_idx in nd:
        if nt <= t:
            for now in range(nt, t):
                i, pa, a = T[now]
                if i < nr:
                    erase(pa)
                    add(a)
                A[i] = a
        else:
            for now in range(nt-1, t-1, -1):
                i, pa, a = T[now]
                if i < nr:
                    erase(a)
                    add(pa)
                A[i] = pa
        if nr <= r:
            for now in range(nr, r):
                a = A[now]
                add(a)
        else:
            for now in range(nr-1, r-1, -1):
                a = A[now]
                erase(a)
        nt, nr = t, r
        if cnt_0:
            Ans[ans_idx] = 0
        else:
            while hq0 and hq1 and hq0[0] == hq1[0]:
                heappop(hq0)
                heappop(hq1)
            Ans[ans_idx] = hq0[0]

for ans in Ans:
	print(ans)
0