結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー 👑 ArcAki
提出日時 2026-01-08 16:47:22
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 3,936 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 364 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 112,980 KB
最終ジャッジ日時 2026-01-11 13:14:34
合計ジャッジ時間 21,319 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin, stdout
from array import array

class Segtree:
    def __init__(self):
        self.data = array('i', [0])*(1<<22)
        self.n = 1<<21

    def get(self, p):
        return self.data[p+self.n]

    def push(self, p, c):
        p += self.n
        self.data[p] += c
        p >>= 1
        while p:
            self.data[p] = self.data[p<<1]+self.data[(p<<1)|1]
            p >>= 1

    def max_right(self, l):
        if l==self.n: return self.n
        l += self.n
        ac = 0
        while 1:
            while not l&1:
                l >>= 1
            if ac+self.data[l]:
                while l < self.n:
                    l <<= 1
                    res = ac+self.data[l]
                    if not res:
                        ac = res
                        l += 1
                return l-self.n
            ac += self.data[l]
            l += 1
            if l&(-l)==l:
                break
        return self.n

    def min_left(self, r):
        if not r: return r
        r += self.n
        ac = 0
        while 1:
            r -= 1
            while r and r&1:
                r >>= 1
            if ac+self.data[r]:
                while r < self.n:
                    r = (r<<1)+1
                    res = ac+self.data[r]
                    if not res:
                        ac = res
                        r -= 1
                return r+1-self.n
            ac += self.data[r]
            if r&(-r)==r:
                break
        return 0


def add(c: int, cnt: Segtree, res: Segtree):
    if cnt.get(c):
        res.push(0, 1)
    else:
        l = cnt.min_left(c)
        r = cnt.max_right(c)
        if l:
            l -= 1
            if r < 1<<20:
                res.push(c^l, 1)
                res.push(c^r, 1)
                res.push(l^r, -1)
            else:
                res.push(l^c, 1)
        elif r < 1<<20:
            res.push(r^c, 1)
    cnt.push(c, 1)


def sub(c: int, cnt: Segtree, res: Segtree):
    cnt.push(c, -1)
    if cnt.get(c):
        res.push(0, -1)
    else:
        l = cnt.min_left(c)
        r = cnt.max_right(c)
        if l:
            l -= 1
            if r < 1<<20:
                res.push(c^l, -1)
                res.push(c^r, -1)
                res.push(l^r, +1)
            else:
                res.push(l^c, -1)
        elif r < 1<<20:
            res.push(r^c, -1)


def main():
    it = list(map(int, stdin.buffer.read().split()))
    n = it[0]
    q = it[1]
    a = it[2:2+n]
    pre = a[:]
    qs = []
    ps = []
    us = []
    vs = []
    pp = n+2
    for _ in range(q):
        t = it[pp]
        pp += 1
        if t==1:
            p = it[pp]-1
            x = it[pp+1]
            pp += 2
            ps.append(p)
            us.append(pre[p])
            vs.append(x)
            pre[p]=x
        else:
            r = it[pp]
            qs.append((r, len(ps)))
            pp += 1
    m = len(qs)
    cnt = Segtree()
    res = Segtree()
    order = list(range(m))
    div = int(2.2*n/(q**0.5))+1
    order.sort(key=lambda ind: qs[ind][0]//div*(1<<25)+(-qs[ind][1] if qs[ind][0]&1 else qs[ind][1]))
    l = r = 0
    ans = [0]*m
    for idx in order:
        left, right = qs[idx]
        while r < right:
            p = ps[r]
            u = us[r]
            v = vs[r]
            a[p] = v
            if p < l:
                sub(u, cnt, res)
                add(v, cnt, res)
            r += 1
        while l > left:
            l -= 1
            sub(a[l], cnt, res)
        while r > right:
            r -= 1
            p = ps[r]
            u = us[r]
            v = vs[r]
            a[p] = u
            if p < l:
                sub(v, cnt, res)
                add(u, cnt, res)
        while l < left:
            add(a[l], cnt, res)
            l += 1
        ans[idx] = res.max_right(0)
    stdout.write("\n".join(map(str, ans)))
    print("")


if __name__ == "__main__":
    main()
0