結果

問題 No.1641 Tree Xor Query
ユーザー ansainansain
提出日時 2021-08-06 22:35:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 394 ms / 5,000 ms
コード長 6,926 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 146,168 KB
最終ジャッジ日時 2023-10-17 04:03:31
合計ジャッジ時間 3,688 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
55,776 KB
testcase_01 AC 42 ms
55,776 KB
testcase_02 AC 43 ms
55,776 KB
testcase_03 AC 44 ms
55,776 KB
testcase_04 AC 45 ms
55,776 KB
testcase_05 AC 45 ms
55,776 KB
testcase_06 AC 44 ms
55,776 KB
testcase_07 AC 43 ms
55,776 KB
testcase_08 AC 42 ms
55,776 KB
testcase_09 AC 43 ms
55,776 KB
testcase_10 AC 43 ms
55,776 KB
testcase_11 AC 43 ms
55,776 KB
testcase_12 AC 44 ms
55,776 KB
testcase_13 AC 391 ms
146,164 KB
testcase_14 AC 394 ms
146,168 KB
testcase_15 AC 106 ms
78,316 KB
testcase_16 AC 160 ms
81,932 KB
testcase_17 AC 150 ms
80,144 KB
testcase_18 AC 112 ms
78,600 KB
testcase_19 AC 119 ms
77,844 KB
testcase_20 AC 344 ms
137,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, Counter, deque
from itertools import chain, permutations, combinations, product, combinations_with_replacement, groupby, accumulate
import operator
from math import sqrt, gcd, factorial
#from math import isqrt, prod, comb  #python3.8用(notpypy)
#from bisect import bisect_left, bisect_right
#from functools import lru_cache, reduce
from operator import xor
#from heapq import heappush, heappop, heapify, heappushpop, heapreplace
#import numpy as np
#import networkx as nx
#from networkx.utils import UnionFind
#from numba import njit, b1, i1, i4, i8, f8
#numba例 @njit(i1(i4[:], i8[:, :]),cache=True) 引数i4配列、i8 2次元配列,戻り値i1
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, NegativeCycleError, maximum_bipartite_matching, maximum_flow, minimum_spanning_tree
def input(): return sys.stdin.readline().rstrip()
def divceil(n, k): return 1+(n-1)//k  # n/kの切り上げを返す
def yn(hantei, yes='Yes', no='No'): print(yes if hantei else no)

from collections import deque
 
#ライブラリ参照https://judge.yosupo.jp/submission/45650

class SparceTable:
    def __init__(self, A, op=min):
        self.op = op
        self.table = [None]*(len(A).bit_length())  # [i, i+2^k)のop
        self.table[0] = A
        pre_table = A
        k = 0
        for k in range(len(A).bit_length()-1):
            pre_table = self.table[k]
            self.table[k+1] = [op(pre_table[i], pre_table[i+(1 << k)])
                               for i in range(len(pre_table)-(1 << k))]
            k += 1

    # [l, r)のop
    def query(self, l, r):
        k = (r-l).bit_length()-1
        return self.op(self.table[k][l], self.table[k][r-(1 << k)])


def make_children_parents(n, edges, root=0):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    parents = [-1]*n
    children= [[] for _ in range(n)]
    d = deque()
    d.append(root)
    parents[root]=root
    while d:
        v = d.popleft()
        for i in graph[v]:
            if parents[i] != -1:
                continue
            parents[i] = v
            children[v].append(i)
            d.append(i)
    return children,parents

def euler_tour(N, children, parents, root=0):
        et_order = [None]*(2*N)
        t_in, t_out, depth = [None]*N, [None]*N, [None]*N
        q = [~root, root]
        t, d = 0, 0
        while q:
            u = q.pop()
            if u >= 0:
                # 行きがけの処理
                depth[u] = d
                d += 1
                # 記録
                et_order[t] = (u, depth[u])
                t_in[u] = t
                t += 1
                # 探索先を追加
                for v in children[u][::-1]:
                    q.append(~v)
                    q.append(v)
            else:
                # 帰りがけの処理
                d -= 1
                # 記録
                et_order[t] = (u, depth[parents[~u]])
                t_out[~u] = t
                t += 1
        return et_order, t_in , t_out,depth

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16580070
class SegmentTree:
 
    __slots__ = ["func", "e", "original_size", "n", "data"]
 
    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
 
    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2
 
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)
 
    def all_folded(self):
        return self.data[1]
 
    def __getitem__(self, index):
        return self.data[self.n + index]
 
    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size
 
    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0


def main():
    mod = 10**9+7
    mod2 = 998244353
    n,q=map(int, input().split())
    c=list(map(int, input().split()))
    children,parents=make_children_parents(n,[list(map(lambda x: int(x)-1, input().split())) for i in range(n-1)],0)
    order,tin,tout,depth=euler_tour(n,children,parents,0)
    tree=[0]*len(order)
    for i in range(n):
        tree[tin[i]]=c[i]
    seg=SegmentTree(tree,xor,0)
    for i in range(q):
        t,x,y=map(int, input().split())
        x-=1
        if t==1:
            seg.replace(tin[x],seg[tin[x]]^y)
        else:
            print(seg.folded(tin[x],tout[x]))

    
    



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