結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2023-02-22 00:12:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 279 ms / 5,000 ms |
コード長 | 2,023 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 116,576 KB |
最終ジャッジ日時 | 2024-07-22 07:22:58 |
合計ジャッジ時間 | 3,569 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
import sysreadline = sys.stdin.readlineclass SegmentTree: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 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 += 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 non_rec_dfs(s):stack = []stack.append(~s)stack.append(s)euler_tour = []discovery = [-1] * Nfinishing = [-1] * Nnow = 0par = [-1] * Nwhile stack:u = stack.pop()if u >= 0:stack.append(~u)discovery[u] = noweuler_tour.append(u)for v in G[u]:if v == par[u]:continuepar[v] = ustack.append(v)else:u = ~ufinishing[u] = noweuler_tour.append(u)now += 1return discovery, finishing, euler_tourN, Q = map(int, readline().split())C = list(map(int, readline().split()))G = [[] for i in range(N)]for i in range(N - 1):A, B = map(int, readline().split())A, B = A - 1, B - 1G[A].append(B)G[B].append(A)D, F, _ = non_rec_dfs(0)T = SegmentTree(202020)for i in range(N):T.update(D[i], C[i])for _ in range(Q):t, x, y = map(int, readline().split())x -= 1if t == 1:C[x] ^= yT.update(D[x], C[x])else:print(T.query(D[x], F[x] + 1))