結果

問題 No.1641 Tree Xor Query
ユーザー hir355hir355
提出日時 2021-08-06 22:55:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 567 ms / 5,000 ms
コード長 2,149 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 81,616 KB
実行使用メモリ 117,352 KB
最終ジャッジ日時 2023-10-17 04:24:15
合計ジャッジ時間 4,427 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,492 KB
testcase_01 AC 38 ms
53,492 KB
testcase_02 AC 38 ms
53,492 KB
testcase_03 AC 40 ms
53,492 KB
testcase_04 AC 45 ms
59,476 KB
testcase_05 AC 45 ms
59,476 KB
testcase_06 AC 45 ms
59,476 KB
testcase_07 AC 40 ms
53,492 KB
testcase_08 AC 38 ms
53,492 KB
testcase_09 AC 39 ms
53,492 KB
testcase_10 AC 41 ms
53,492 KB
testcase_11 AC 39 ms
53,492 KB
testcase_12 AC 38 ms
53,492 KB
testcase_13 AC 564 ms
114,984 KB
testcase_14 AC 567 ms
114,984 KB
testcase_15 AC 114 ms
76,772 KB
testcase_16 AC 215 ms
79,540 KB
testcase_17 AC 208 ms
79,120 KB
testcase_18 AC 126 ms
77,644 KB
testcase_19 AC 172 ms
77,264 KB
testcase_20 AC 449 ms
117,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def euler_tour(g, root=0):
    s = [root]
    d = [1] * len(g)
    order = []
    while s:
        p = s.pop()
        if d[p] == 1:
            d[p] = 0
            s.append(p)
            order.append(p)
            for node in g[p]:
                if d[node]:
                    s.append(node)
        else:
            d[p] = -1
            order.append(p)
    return order

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

n, q = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
euler = euler_tour(g)
x = [-1] * n
y = [-1] * n
for i, v in enumerate(euler):
    if x[v] == -1:
        x[v] = i
    else:
        y[v] = i
seg = SegmentTree(n * 2, f=lambda x, y: x ^ y)
tp = 0
for i in range(n):
    tp ^= c[i]
    seg.update(x[i], c[i])
for i in range(q):
    t, a, b = map(int, input().split())
    if t == 1:
        tp ^= b
        c[a - 1] ^= b
        seg.update(x[a - 1], c[a - 1])
    else:
        print(seg.query(x[a - 1], y[a - 1]))
0