#1013100 (PyPy3) No.1641 Tree Xor Query

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
## 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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX