結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 ああいい
|
| 提出日時 | 2022-02-25 16:36:43 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,390 ms / 2,000 ms |
| コード長 | 9,216 bytes |
| コンパイル時間 | 515 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 126,684 KB |
| 最終ジャッジ日時 | 2024-12-26 22:22:01 |
| 合計ジャッジ時間 | 8,801 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
base = 30
#頂点は1-index,下段は0-index
class LazySegTree:
#単位元と結合と作用をここで定義
Xunit = ((1<<(3*base))+1)<<base
Aunit = None
def Xf(self,x,y):
return (seki(x>>base,y>>base) << base) + (x&mask+y&mask)
#Xf = max
def Af(self,a,b):
if b == self.Aunit:
return a
return b
#AのXへの作用
def operate(self,x,a):
if a == self.Aunit:
return x
num = x & mask
tmp = _pow(a,num)
return (tmp<<base)+num
def __init__(self,N):
self.N = N
self.X = [self.Xunit] * (N + N)
self.A = [self.Aunit] * (N + N)
def build(self,seq):
for i,x in enumerate(seq,self.N):
self.X[i] = x
for i in range(self.N-1,0,-1):
self.X[i] = self.Xf(self.X[i<<1],self.X[i<<1 | 1])
def eval_at(self,i):
return self.operate(self.X[i],self.A[i])
def propagate_at(self,i):
self.X[i] = self.eval_at(i)
self.A[i<<1] = self.Af(self.A[i<<1],self.A[i])
self.A[i<<1 | 1] = self.Af(self.A[i<<1 | 1],self.A[i])
self.A[i] = self.Aunit
def propagate_above(self,i):
H = i.bit_length() - 1
for h in range(H,0,-1):
self.propagate_at(i >> h)
def recalc_above(self,i):
while i > 1:
i >>= 1
self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
def update(self,i,x):
i += self.N
self.propagate_above(i)
self.X[i] = x
self.A[i] = self.Aunit
self.recalc_above(i)
def fold(self,L = 0,R = -1):
if R == -1:R = self.N
L += self.N
R += self.N
self.propagate_above(L // (L & -L))
self.propagate_above(R // (R & -R) -1)
vL = self.Xunit
vR = self.Xunit
while L < R:
if L & 1:
vL = self.Xf(vL,self.eval_at(L))
L += 1
if R & 1:
R -= 1
vR = self.Xf(self.eval_at(R),vR)
L >>= 1
R >>= 1
return self.Xf(vL,vR)
def operate_range(self,L,R,x):
#区間全体に作用させる
L += self.N
R += self.N
L0 = L // (L & -L)
R0 = R // (R & -R) - 1
self.propagate_above(L0)
self.propagate_above(R0)
while L < R:
if L & 1:
self.A[L] = self.Af(self.A[L],x)
L += 1
if R & 1:
R -= 1
self.A[R] = self.Af(self.A[R],x)
L >>= 1
R >>= 1
self.recalc_above(L0)
self.recalc_above(R0)
def write(self):
print(self.X)
def change(self,Xf,Xunit,Af,Aunit,operate):
self.Xf = Xf
self.Xunit = Xunit
self.Af = Af
self.Aunit = Aunit
self.operate = operate
#HL分解
class HL:
#u,vを結ぶpathへのクエリはここにでも
# f は区間 [l,r)に対するクエリ
def f(self,l,r):
pass
def merge(self,x,y):
return x + y
def __init__(self,G,root):
self.G = G
self.root = root
self.N = len(G)
self.size = [1] * self.N #部分木のサイズ
self.p = [0] * self.N #親頂点
self.H = [None] * self.N #Heavy_edgeでつながる子頂点。葉ではNoneが入ってる
self._in = [-1] * self.N #最初に探索したときの位置
self.out = [-1] * self.N #部分木をでるタイミング。オイラーとはちょっと違う。
#開区間 [_in[i],out[i]) がiの部分木に対応
self.pathtop = [0] * self.N #iの属するpathの中で最も根に近い頂点。代表にする
self.build()
self.build_path()
def build(self):
stack = [(~self.root,-1),(self.root,-1)]
G = self.G
size = self.size
H = self.H
while stack:
now,parent = stack.pop()
if now < 0:
now = ~now
_max = 0
for v in G[now]:
if v == parent:continue
size[now] += size[v]
if size[v] > _max:
_max = size[v]
H[now] = v
else:
for v in G[now]:
if v == parent:continue
self.p[v] = now
stack.append((~v,now))
stack.append((v,now))
def build_path(self):
stack = [(~self.root,-1,self.root),(self.root,-1,self.root)]
count = 0
G = self.G
H = self.H
while stack:
now,parent,top = stack.pop()
if now >= 0:
self._in[now] = count
count += 1
self.pathtop[now] = top
h = H[now]
if h is None:continue
for v in G[now]:
if v == parent or v == h:continue
stack.append((~v,now,v))
stack.append((v,now,v))
stack.append((~h,now,top))
stack.append((h,now,top))
else:
now = ~now
self.out[now] = count
def lca(self,a,b):
#最近共通先祖
pathtop = self.pathtop
_in = self._in
pa = pathtop[a]
pb = pathtop[b]
while pa != pb:
if _in[pa] > _in[pb]:
a = self.p[pa]
pa = pathtop[a]
else:
b = self.p[pb]
pb = pathtop[b]
return a if _in[a] < _in[b] else b
def subtree_query(self,a,f = None):
#if f is None:f = self.f
return f(self._in[a],self.out[a])
def subtree_array(self,a):
return (self._in[a],self.out[a])
#下のpath_arrayとほぼ同じ。タプルを一つだけ返す
#f = lambda l,r:seg.fold(l,r) とか
#f = lambda l,r:seg.oparete_range(l,r,x) とか
#代入して使う
def path_query(self,a,b,f = None,merge = None):
#if f is None:f = self.f
#if merge is None:merge = self.merge
pathtop = self.pathtop
p = self.p
_in = self._in
pa = pathtop[a]
pb = pathtop[b]
ans = 0
while pa != pb:
if _in[pa] > _in[pb]:
ans = merge(ans,f(_in[pa],_in[a]+1))
a = p[pa]
pa = pathtop[a]
else:
ans = merge(ans,f(_in[pb],_in[b]+1))
b = p[pb]
pb = pathtop[b]
if _in[a] > _in[b]:
a,b = b,a
ans = merge(ans,f(_in[a],_in[b]+1))
return ans
def path_array(self,a,b):
# a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも
#半開区間 [l,r) の集まりを返す
#現状順番は適当
#こっちのほうが早かった
pathtop = self.pathtop
p = self.p
_in = self._in
ans = []
pa = pathtop[a]
pb = pathtop[b]
while pa != pb:
if _in[pa] > _in[pb]:
ans.append((_in[pa],_in[a]+1))
a = p[pa]
pa = pathtop[a]
else:
ans.append((_in[pb],_in[b]+1))
b = p[pb]
pb = pathtop[b]
if _in[a] > _in[b]:
a,b = b,a
ans.append((_in[a],_in[b]+1))
return ans
P = 10 ** 9 + 7
base = 30
unit = (1<<(3*base))+1
mask = (1 << base) - 1
def seki(x,y):
d = x & mask
x >>= base
c = x & mask
x >>= base
b = x & mask
a = x >> base
h = y & mask
y >>= base
g = y & mask
y >>= base
f = y & mask
e = y >> base
i = (a * e + b * g) % P
j = (a * f + b * h) % P
k = (c * e + d * g) % P
l = (c * f + d * h) % P
return (i<<(3*base))+(j<<(2*base))+(k<<base)+l
def make(t):
a,b,c,d = t
ans = (a << (3*base)) + (b << (2*base)) + (c << base) + d
return (ans<<base)+1
def _pow(x,n):
tmp = unit
while n:
if n & 1:
tmp = seki(tmp,x)
x = seki(x,x)
n >>= 1
return tmp
import sys
rr = sys.stdin.buffer
n = int(rr.readline())
G = [[] for _ in range(n)]
edge = []
taiou = []
for _ in range(n-1):
a,b = map(int,rr.readline().split())
G[a].append(b)
G[b].append(a)
edge.append((a,b))
hl = HL(G,0)
for a,b in edge:
if hl.p[a] == b:
taiou.append(a)
else:
taiou.append(b)
seg = LazySegTree(n)
seq = [(unit<<base)+1] * n
seg.build(seq)
q = int(rr.readline())
for _ in range(q):
s,*t = input().split()
t = list(map(int,t))
if s == "x":
seg.update(hl._in[taiou[t[0]]],make(t[1:]))
else:
i,j = t
ans = unit
L = hl.path_array(i,j)
u,v = L.pop()
for l,r in L:
ans = seki(seg.fold(l,r)>>base,ans)
ans = seki(seg.fold(u+1,v)>>base,ans)
d = ans & mask
ans >>= base
c = ans & mask
ans >>= base
b = ans & mask
a = ans >> base
print(a,b,c,d)