結果
| 問題 |
No.1641 Tree Xor Query
|
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2021-06-21 00:40:58 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,474 bytes |
| コンパイル時間 | 92 ms |
| コンパイル使用メモリ | 13,568 KB |
| 実行使用メモリ | 168,220 KB |
| 最終ジャッジ日時 | 2024-09-17 00:51:40 |
| 合計ジャッジ時間 | 15,198 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 TLE * 1 |
ソースコード
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)
C=pin(N,int,True)
depth=[0]*N
d=[[]for _ in[0]*N]
for _ in[0]*(N-1):
a,b=pin(2)
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)
for _ in[0]*Q:
T,x,y=pin(3)
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))
return
main()