結果

問題 No.1641 Tree Xor Query
コンテスト
ユーザー hir355
提出日時 2021-08-06 22:55:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 486 ms / 5,000 ms
コード長 2,149 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 118,128 KB
最終ジャッジ日時 2024-09-17 03:07:55
合計ジャッジ時間 3,532 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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