結果

問題 No.1234 典型RMQ
ユーザー 👑 KazunKazun
提出日時 2020-09-20 04:02:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,696 ms / 2,000 ms
コード長 3,434 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 120,108 KB
最終ジャッジ日時 2024-11-09 02:16:52
合計ジャッジ時間 32,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,608 KB
testcase_01 AC 43 ms
52,480 KB
testcase_02 AC 44 ms
52,480 KB
testcase_03 AC 44 ms
52,608 KB
testcase_04 AC 44 ms
52,864 KB
testcase_05 AC 44 ms
52,480 KB
testcase_06 AC 1,696 ms
118,736 KB
testcase_07 AC 1,167 ms
102,500 KB
testcase_08 AC 1,687 ms
120,108 KB
testcase_09 AC 1,524 ms
114,168 KB
testcase_10 AC 1,670 ms
119,900 KB
testcase_11 AC 1,598 ms
117,232 KB
testcase_12 AC 1,472 ms
112,364 KB
testcase_13 AC 1,199 ms
102,752 KB
testcase_14 AC 1,458 ms
112,320 KB
testcase_15 AC 1,456 ms
110,712 KB
testcase_16 AC 1,622 ms
119,368 KB
testcase_17 AC 1,469 ms
112,828 KB
testcase_18 AC 1,225 ms
99,396 KB
testcase_19 AC 1,672 ms
119,848 KB
testcase_20 AC 781 ms
101,760 KB
testcase_21 AC 1,614 ms
117,536 KB
testcase_22 AC 1,322 ms
106,240 KB
testcase_23 AC 1,190 ms
106,112 KB
testcase_24 AC 1,229 ms
106,112 KB
testcase_25 AC 1,134 ms
106,240 KB
testcase_26 AC 1,205 ms
105,984 KB
testcase_27 AC 44 ms
52,736 KB
testcase_28 AC 44 ms
52,864 KB
testcase_29 AC 44 ms
52,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)

    def eval(self,k):
        if self.lazy[k]==self.id: #単位元だったら終了
            return

        if k<self.num-1: #葉でなければ子に伝搬
            self.lazy[(k<<1)+1]=self.comp(self.lazy[k],self.lazy[(k<<1)+1])
            self.lazy[(k<<1)+2]=self.comp(self.lazy[k],self.lazy[(k<<1)+2])

        #自身を更新(作用)
        self.data[k]=self.op(self.lazy[k],self.data[k])
        self.lazy[k]=self.id
        return

    def get(self,k,index=0):
        return self.product(k,k,index)

    def operate(self,From,To,alpha,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__operate_second(A,B+1,alpha,0,0,self.num)

    def __operate_second(self,a,b,alpha,k,l,r):
        self.eval(k)
        if (a<=l) and (r<=b): #完全に内側のとき
            self.lazy[k]=self.comp(alpha,self.lazy[k])
            self.eval(k)
        elif (a<r) and (l<b): #一部がかぶるとき
            self.__operate_second(a,b,alpha,(k<<1)+1,l,(l+r)>>1) #左の子
            self.__operate_second(a,b,alpha,(k<<1)+2,(l+r)>>1,r) #右の子
            self.data[k]=self.calc(self.data[(k<<1)+1],self.data[(k<<1)+2])

    def update(self,k,x):
        pass

    def product(self,From,To,index=0,left_closed=True,right_closed=True):
        A=From-index+(not left_closed)
        B=To-index-(not right_closed)

        return self.__product_second(A,B+1,0,0,self.num)

    def __product_second(self,a,b,k,l,r):
        self.eval(k)
        if r<=a or b<=l:
            return self.unit
        elif a<=l and r<=b:
            return self.data[k]
        else:
            alpha=self.__product_second(a,b,(k<<1)+1,l,(l+r)>>1)
            beta=self.__product_second(a,b,(k<<1)+2,(l+r)>>1,r)
            return self.calc(alpha,beta)
#================================================
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)))
0