結果

問題 No.1641 Tree Xor Query
コンテスト
ユーザー LyricalMaestro
提出日時 2024-09-24 00:42:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 518 ms / 5,000 ms
コード長 3,099 bytes
コンパイル時間 2,923 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 120,996 KB
最終ジャッジ日時 2024-09-24 06:06:13
合計ジャッジ時間 4,594 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1641

from collections import deque

class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [0] * (2 * self.size)
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self.array[i] = self.array[2 * i] ^ self.array[2 * i + 1]
            end_index = start_index
            start_index = end_index // 2

    def add(self, x, a):
        index = self.size + x
        self.array[index] ^= a
        while index > 1:
            index //= 2
            self.array[index] = self.array[2 * index] ^ self.array[2 * index + 1]

    def get_max(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s ^= self.array[R]
            if L & 1:
                s ^= self.array[L]
                L += 1
            L >>= 1; R >>= 1
        return s


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    next_nodes = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        next_nodes[u - 1].append(v - 1)
        next_nodes[v - 1].append(u - 1)
    
    txy = []
    for _ in range(Q):
        t, x, y = map(int, input().split())
        txy.append((t, x - 1, y))

    # オイラーツアー
    eular_tour_index_map = [[-1, -1] for _ in range(N)]
    eular_tour_index = 0
    parents = [-2] * N
    parents[0] = -1
    stack = deque()
    stack.append((0, 0))
    while len(stack) > 0:
        v, index = stack.pop()
        if index == 0:
            eular_tour_index_map[v][0] = eular_tour_index
            eular_tour_index += 1

        while index < len(next_nodes[v]):
            w = next_nodes[v][index]
            if w == parents[v]:
                index +=1
                continue
            parents[w] = v
            stack.append((v, index + 1))
            stack.append((w, 0))
            break
    
        if index == len(next_nodes[v]):
            eular_tour_index_map[v][1] = eular_tour_index
            eular_tour_index += 1

    # オイラーツアーベースのセグメントツリー
    eular_tour = [0] * (2 * N)
    for i in range(N):
        eular_tour[eular_tour_index_map[i][0]] = C[i]
    seg_tree = SegmentTree(eular_tour)

    for t, x, y in txy:
        if t == 1:
            x_ = eular_tour_index_map[x][0]
            seg_tree.add(x_, y)
        else:
            # t= 2s
            in_, out_ = eular_tour_index_map[x]
            answer = seg_tree.get_max(in_, out_)
            print(answer)
    




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