結果
| 問題 |
No.1234 典型RMQ
|
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2020-09-20 20:15:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,230 bytes |
| コンパイル時間 | 156 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 106,624 KB |
| 最終ジャッジ日時 | 2024-07-20 01:05:03 |
| 合計ジャッジ時間 | 16,403 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 WA * 22 |
ソースコード
class Lazy_Evaluation_Tree():
def __init__(self,L,calc,unit,op,comp,id):
"""calcを演算,opを作用とするリストLのSegment Treeを作成
calc:演算
unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
op:作用素
comp:作用素の合成
id:恒等写像
[条件] M:Monoid,F={f:F x M→ M:作用素}に対して,以下が成立する.
Fは恒等写像 id を含む.つまり,任意の x in M に対して id(x)=x
Fは写像の合成に閉じている.つまり,任意の f,g in F に対して, comp(f,g) in F
任意の f in F, x,y in M に対して,f(xy)=f(x)f(y)である.
[注記]
作用素は左から掛ける.更新も左から.
"""
self.calc=calc
self.unit=unit
self.op=op
self.comp=comp
self.id=id
N=len(L)
d=max(1,(N-1).bit_length())
k=1<<d
X=[unit]*(k-1)+L+[unit]*(k-len(L))
self.num=k
self.depth=d
for i in range(k-2,-1,-1):
X[i]=calc(X[(i<<1)+1],X[(i<<1)+2])
self.data=X
self.lazy=[self.id]*((k<<1)-1)
#配列の第k要素の真上を伝搬
def propagation(self,k,index=0):
x=k
V=[k]
while x:
x=(x-1)>>1
V.append(x)
for x in V[::-1]:
if self.lazy[x]==self.id:
continue
self.data[x]=self.op(self.lazy[x],self.data[x])
if x<self.num-1:
self.lazy[(x<<1)+1]=self.comp(self.lazy[x],self.lazy[(x<<1)+1])
self.lazy[(x<<1)+2]=self.comp(self.lazy[x],self.lazy[(x<<1)+2])
self.lazy[x]=self.id
def recalculate(self,k,index=0):
x=k-index
while True:
x=(x-1)>>1
if x<0:
break
lc=(x<<1)+1
rc=(x<<1)+2
if self.lazy[lc]==self.id:
a=self.data[lc]
else:
a=self.op(self.lazy[lc],self.data[lc])
if self.lazy[rc]==self.id:
b=self.data[rc]
else:
b=self.op(self.lazy[rc],self.data[rc])
self.data[x]=self.calc(a,b)
def get(self,k,index=0):
""" 第k要素を取得
"""
m=(k-index)+(self.num-1)
self.propagation(m,0)
self.recalculate(m,0)
return self.data[m]
def operate(self,From,To,alpha,index=0,left_closed=True,right_closed=True):
L=From-index+(not left_closed)+self.num-1
R=To-index-(not right_closed)+self.num-1
L0=R0=None
X=L
Y=R
while X<Y:
if X&1==0:
if L0==None:
L0=X
X+=1
if Y&1:
if R0==None:
R0=Y
Y-=1
X=(X-1)>>1
Y=(Y-1)>>1
if L0==None:
L0=X
if R0==None:
R0=Y
self.propagation(L0)
self.propagation(R0)
while L<R:
if L&1==0:
self.lazy[L]=self.comp(alpha,self.lazy[L])
L+=1
if R&1:
self.lazy[R]=self.comp(alpha,self.lazy[R])
R-=1
L=(L-1)>>1
R=(R-1)>>1
if L==R:
self.lazy[L]=self.comp(alpha,self.lazy[L])
self.recalculate(L0)
self.recalculate(R0)
def update(self,k,beta,index=0):
""" 第k要素をbetaに変更する.
"""
m=(k-index)+(self.num-1)
self.propagation(m,0)
self.lazy[m]=self.id
self.data[m]=beta
self.recalculate(m,0)
def product(self,From,To,index=0,left_closed=True,right_closed=True):
L=From-index+(not left_closed)+self.num-1
R=To-index-(not right_closed)+self.num-1
L0=R0=None
X=L
Y=R
while X<Y:
if X&1==0:
if L0==None:
L0=X
X+=1
if Y&1:
if R0==None:
R0=Y
Y-=1
X=(X-1)>>1
Y=(Y-1)>>1
if L0==None:
L0=X
if R0==None:
R0=Y
self.propagation(L0)
self.propagation(R0)
vL=self.unit
vR=self.unit
while L<R:
if L&1==0:
vL=self.calc(vL,self.data[L])
L+=1
if R&1:
vR=self.calc(self.data[R],vR)
R-=1
L=(L-1)>>1
R=(R-1)>>1
if L==R:
return self.calc(self.calc(vL,self.data[L]),vR)
else:
return self.calc(vL,vR)
def product_all(self):
return self.product(0,self.num-1)
#================================================
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
calc=lambda x,y:min(x,y)
unit=float("inf")
op=lambda a,x:a+x
comp=lambda a,b:a+b
id=0
S=Lazy_Evaluation_Tree(A,calc,unit,op,comp,id)
X=[]
for _ in range(Q):
k,l,r,c=map(int,input().split())
if k==1:
S.operate(l,r,c,1)
else:
X.append(S.product(l,r,1))
print("\n".join(map(str,X)))