結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-08-07 00:04:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 532 ms / 5,000 ms |
コード長 | 3,277 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 123,768 KB |
最終ジャッジ日時 | 2024-09-17 04:23:54 |
合計ジャッジ時間 | 3,909 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
def segfunc(x,y):return x^yclass SegmentTree(object):def __init__(self, A, dot, unit):n = 1 << (len(A) - 1).bit_length()tree = [unit] * (2 * n)for i, v in enumerate(A):tree[i + n] = vfor i in range(n - 1, 0, -1):tree[i] = dot(tree[i << 1], tree[i << 1 | 1])self._n = nself._tree = treeself._dot = dotself._unit = unitdef __getitem__(self, i):return self._tree[i + self._n]def update(self, i, v):i += self._nself._tree[i] = vwhile i != 1:i >>= 1self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])def add(self, i, v):self.update(i, self[i] + v)def sum(self, l, r): #これで[l,r)から取り出す。l += self._nr += self._nl_val = r_val = self._unitwhile l < r:if l & 1:l_val = self._dot(l_val, self._tree[l])l += 1if r & 1:r -= 1r_val = self._dot(self._tree[r], r_val)l >>= 1r >>= 1return self._dot(l_val, r_val)def main():n,Q = map(int,input().split())C = list(map(int,input().split()))graph = [[] for _ in range(n)]for i in range(n-1):a,b = map(int,input().split())a -= 1; b -= 1graph[a].append(b)graph[b].append(a)idx = 0start = 0euler = []left = [-1] * n #初めて出てくる位置。(行き)right = [-1] * n #二回目に出てくる位置。(帰り)depth = [-1] * npar = [-1] * ndepth[start] = 0 #根の深さは0stack = []stack.append(~start) #帰りがけ用stack.append(start) #行き用。行きを先に取り出したいので後に追加。while stack:v = stack.pop()if v >= 0:euler.append(v)if left[v] == -1:left[v] = idxidx += 1d = depth[v]for u in graph[v]:if par[v] == u:continuepar[u] = vdepth[u] = d + 1stack.append(~u) #後で取り出したいのでこちらが先stack.append(u)else:a = ~v #戻すif right[a] == -1:right[a] = idx#euler.append(a)#idx += 1#print(euler) #古いINDEXを入れると新しいINDEXが出てくる#print(left)#print(right)NC = [-1]*n; dic = {} #新しいINDEXを入れると古いINDEXが出てくる。for i in range(n):idx = left[i]dic[idx] = icval = C[i]NC[idx] = cval#print(NC)Tree = SegmentTree(NC,segfunc,0)for _ in range(Q):t,x,y = map(int,input().split())x -= 1 #0-indexnx = left[x]if t == 1:val = Tree.__getitem__(nx)^yTree.update(nx,val)else:#ret = []#for i in range(n):# ret.append(Tree.__getitem__(i))#print(ret)ans = Tree.sum(left[x],right[x])print(ans)if __name__ == '__main__':main()