結果

問題 No.1641 Tree Xor Query
ユーザー harurunharurun
提出日時 2021-06-24 18:47:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,732 ms / 5,000 ms
コード長 6,773 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 284,916 KB
最終ジャッジ日時 2023-10-17 02:19:39
合計ジャッジ時間 7,684 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
55,588 KB
testcase_01 AC 42 ms
55,588 KB
testcase_02 AC 41 ms
55,588 KB
testcase_03 AC 47 ms
63,308 KB
testcase_04 AC 53 ms
65,500 KB
testcase_05 AC 58 ms
65,500 KB
testcase_06 AC 54 ms
65,500 KB
testcase_07 AC 50 ms
63,440 KB
testcase_08 AC 42 ms
55,588 KB
testcase_09 AC 49 ms
63,444 KB
testcase_10 AC 51 ms
65,480 KB
testcase_11 AC 46 ms
63,308 KB
testcase_12 AC 46 ms
61,260 KB
testcase_13 AC 1,353 ms
236,816 KB
testcase_14 AC 1,366 ms
236,876 KB
testcase_15 AC 171 ms
82,048 KB
testcase_16 AC 347 ms
97,708 KB
testcase_17 AC 310 ms
90,232 KB
testcase_18 AC 196 ms
86,692 KB
testcase_19 AC 238 ms
82,280 KB
testcase_20 AC 1,732 ms
284,916 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#assert
def _ceil_pow2(n: int):
    x = 0
    while (1 << x) < n:
        x += 1
    return x


def _bsf(n: int):
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2
    return x

class SegTree:
    def __init__(self,op,e,v):
        self._op = op
        self._e = e
        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p, x):
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p):
        assert 0 <= p < self._n

        return self._d[p + self._size]

    def prod(self, left, right):
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self):
        return self._d[1]

    def max_right(self, left,f):
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right,f):
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int):
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])



class INPUT:
  def __init__(self):
    self._l=open(0).read().split()
    self._length=len(self._l)
    self._index=0
    return

  def stream(self,k=1,f=int,f2=False):
    assert(-1<k)
    if self._length==self._index or self._length-self._index<k:
      raise Exception("There is no input!")
    elif f!=str:
      if k==0:
        ret=list(map(f,self._l[self._index:]))
        self._index=self._length
        return ret
      if k==1 and not f2:
        ret=f(self._l[self._index])
        self._index+=1
        return ret
      if k==1 and f2:
        ret=[f(self._l[self._index])]
        self._index+=1
        return ret
      ret=[]
      for _ in [0]*k:
        ret.append(f(self._l[self._index]))
        self._index+=1
      return ret
    else:
      if k==0:
        ret=list(self._l[self._index:])
        self._index=self._length
        return ret
      if k==1 and not f2:
        ret=self._l[self._index]
        self._index+=1
        return ret
      if k==1 and f2:
        ret=[self._l[self._index]]
        self._index+=1
        return ret
      ret=[]
      for _ in [0]*k:
        ret.append(self._l[self._index])
        self._index+=1
      return ret
pin=INPUT().stream

"""
pin(number[default:1],f[default:int],f2[default:False])
if number==0 -> return left all
listを変数で受け取るとき、必ずlistをTrueにすること。
"""
from collections import deque
from sys import stderr
bit_length=10

def myop(a,b):
  ret=[0]*bit_length
  #stderr.write(f"{a},{b}\n")
  for i in range(bit_length):
    ret[i]=a[i]+b[i]
  return ret

#def e():
#  ret=[0]*bit_length
#  return ret
e=[0]*bit_length

def xor(a,b):
  ret=[0]*bit_length
  for i in range(bit_length):
    ret[i]=a[i]^b[i]
  return ret

def restore(a):
  ret=0
  c=1
  for i in range(bit_length):
    ret+=c*a[i]
    c*=2
  return ret

def change(a):
  ret=[0]*bit_length
  for i in range(bit_length):
    if (a>>i)&1:
      ret[i]=1
  return ret

def calculate(a):
  ret=0
  c=1
  for i in range(bit_length):
    ret+=c*((a[i]//2)%2)
    c*=2
  return ret

def main():
  N,Q=pin(2)
  assert(2<=N<=100000)
  assert(1<=Q<=100000)
  C=pin(N,int,True)
  MAX_C=2**10-1
  for i in C:
    assert(0<=i<=MAX_C)
  depth=[0]*N
  d=[[]for _ in[0]*N]
  for _ in[0]*(N-1):
    a,b=pin(2)
    assert(1<=a<=N)
    assert(1<=b<=N)
    d[a-1].append(b-1)
    d[b-1].append(a-1)
  dq=deque()
  B=[False]*N
  dq.append(0)
  while dq:
    q=dq.pop()
    B[q]=True
    for i in d[q]:
      if B[i]:
        continue
      dq.append(i)
      depth[i]+=depth[q]+1
  parents=[[]for _ in[0]*N]
  children=[[]for _ in[0]*N]
  for i in range(N):
    for j in d[i]:
      if depth[i]<depth[j]:
        children[i].append(j)
      else:
        parents[i].append(j)
  now=0
  next=-1
  Nodes=[[]for _ in[0]*N]
  A=[]
  check=[False]*N
  while 1:
    if not check[now]:
      Nodes[now].append(len(A))
      A.append(change(C[now]))
      check[now]=True
    if children[now]:
      next=children[now].pop()
    elif parents[now]:
      Nodes[now].append(len(A))
      A.append(change(C[now]))
      next=parents[now][-1]
    else:
      Nodes[now].append(len(A))
      A.append(change(C[now]))
      break
    now=next
  
  seg=SegTree(myop,e,A)
  T_CNT=0
  for _ in[0]*Q:
    T,x,y=pin(3)
    assert(1<=T<=2)
    assert(1<=x<=N)
    if T==1:
      assert(0<=y<=MAX_C)
    else:
      T_CNT+=1
      assert(y==0)
    x-=1
    if T==1:
      l=Nodes[x][0]
      r=Nodes[x][1]
      L=seg.get(l)
      R=seg.get(r)
      seg.set(l,xor(L,change(y)))
      seg.set(r,xor(R,change(y)))
    else:
      l=Nodes[x][0]
      r=Nodes[x][1]
      P=seg.prod(l,r+1)
      print(calculate(P))
  assert(T_CNT>0)
  return

main()
0