結果

問題 No.1234 典型RMQ
ユーザー 👑 KazunKazun
提出日時 2020-09-20 04:08:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,650 ms / 2,000 ms
コード長 3,427 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 119,692 KB
最終ジャッジ日時 2024-11-09 02:18:58
合計ジャッジ時間 31,182 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,736 KB
testcase_01 AC 44 ms
52,864 KB
testcase_02 AC 44 ms
52,608 KB
testcase_03 AC 43 ms
52,480 KB
testcase_04 AC 43 ms
52,736 KB
testcase_05 AC 43 ms
53,248 KB
testcase_06 AC 1,567 ms
118,580 KB
testcase_07 AC 1,152 ms
102,892 KB
testcase_08 AC 1,563 ms
119,692 KB
testcase_09 AC 1,437 ms
113,260 KB
testcase_10 AC 1,648 ms
119,264 KB
testcase_11 AC 1,506 ms
117,608 KB
testcase_12 AC 1,388 ms
111,660 KB
testcase_13 AC 1,127 ms
102,700 KB
testcase_14 AC 1,395 ms
112,044 KB
testcase_15 AC 1,377 ms
110,900 KB
testcase_16 AC 1,609 ms
119,364 KB
testcase_17 AC 1,440 ms
112,296 KB
testcase_18 AC 1,230 ms
99,680 KB
testcase_19 AC 1,650 ms
119,408 KB
testcase_20 AC 823 ms
102,784 KB
testcase_21 AC 1,579 ms
117,668 KB
testcase_22 AC 1,290 ms
103,936 KB
testcase_23 AC 1,147 ms
103,552 KB
testcase_24 AC 1,097 ms
103,680 KB
testcase_25 AC 1,090 ms
103,808 KB
testcase_26 AC 1,168 ms
103,808 KB
testcase_27 AC 43 ms
52,352 KB
testcase_28 AC 43 ms
52,480 KB
testcase_29 AC 44 ms
52,736 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=1<<64
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