#555985 (PyPy3) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: 👑 Kazun
• 提出日時: 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

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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)))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX