結果
問題 | No.1641 Tree Xor Query |
ユーザー |
|
提出日時 | 2024-04-18 18:51:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,449 ms / 5,000 ms |
コード長 | 2,274 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 63,132 KB |
最終ジャッジ日時 | 2024-10-10 12:12:19 |
合計ジャッジ時間 | 6,337 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.buffer.readlinesys.setrecursionlimit(10**9)class SegmentTree:"""https://qiita.com/dn6049949/items/afa12d5d079f518de368 から拝借しています。"""def __init__(self, size, f=lambda x, y: x ^ y, default=0):self.size = 2 ** (size - 1).bit_length()self.default = defaultself.dat = [default] * (self.size * 2)self.f = fdef initialize(self, A):for i, a in enumerate(A, self.size):self.dat[i] = afor i in range(self.size - 1, 0, -1):self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])def update(self, i, x):i += self.sizeself.dat[i] = xwhile i > 0:i >>= 1self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])def query(self, l, r):"""半開区間[l,r)"""l += self.sizer += self.sizelres, rres = self.default, self.defaultwhile l < r:if l & 1:lres = self.f(lres, self.dat[l])l += 1if r & 1:r -= 1rres = self.f(self.dat[r], rres)l >>= 1r >>= 1res = self.f(lres, rres)return resdef get(self, i):return self.dat[i + self.size]N, Q = map(int, input().split())C = list(map(int, input().split()))T = [[] for _ in range(N)]for _ in range(N - 1):a, b = map(lambda x: int(x) - 1, input().split())T[a].append(b)T[b].append(a)# euler tourtour = []v_in_tour = [[] for _ in range(N)]def dfs(v, p):v_in_tour[v].append(len(tour))tour.append(v)for u in T[v]:if u == p:continuedfs(u, v)v_in_tour[v].append(len(tour))tour.append(v)dfs(0, -1)init_c = [0] * (2 * N)for i, c in enumerate(C):init_c[v_in_tour[i][0]] = c# segment treest = SegmentTree(2 * N)st.initialize(init_c)for _ in range(Q):query = tuple(map(int, input().split()))if query[0] == 1:x = query[1] - 1y = query[2]st.update(v_in_tour[x][0], st.get(v_in_tour[x][0]) ^ y)elif query[0] == 2:x = query[1] - 1print(st.query(v_in_tour[x][0], v_in_tour[x][1]))