#555170 (PyPy3) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: titia
• 提出日時: 2020-09-18 22:27:16
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 390 ms / 2,000 ms
• コード長: 2,985 bytes
• コンパイル時間: 177 ms
• コンパイル使用メモリ: 82,432 KB
• 実行使用メモリ: 94,464 KB
• 最終ジャッジ日時: 2024-11-09 01:58:24
• 合計ジャッジ時間: 9,915 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
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
116
117
118
119
120
121
122
123
124
125
126
127
128
import sys
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
# 非再帰遅延伝搬セグ木（範囲加算, 範囲最小値出力）
# 高々N点を更新
seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[1<<60]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]=A[i]
for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=min(SEG[i*2],SEG[i*2+1])
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
def indexes(L,R): # 遅延伝搬すべきノードのリストを下から上の順に返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]
    R-=1
    
    L>>=1
    R>>=1
    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1
    while L!=0:
        INDLIST.append(L)
        L>>=1
    return INDLIST
        
def adds(l,r,x): # 区間[l,r)を +x 更新
        
    L=l+seg_el
    R=r+seg_el
    L//=(L & (-L))
    R//=(R & (-R))
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬. 上から更新していく. （ただし, 今回はうまくやるとこの部分を省ける. addはクエリの順番によらないので. 
        addではなく, updateの場合必要）
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
    
    while L!=R:
        if L > R:
            SEG[L]+=x
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))
        else:
            R-=1
            SEG[R]+=x
            LAZY[R]+=x
            R//=(R & (-R))
    for ind in UPIND:
        SEG[ind]=min(SEG[ind<<1],SEG[1+(ind<<1)]) # 最初の遅延伝搬を省いた場合, ここを変える
        
def getvalues(l,r): # 区間[l,r)に関するminを調べる
    L=l+seg_el
    R=r+seg_el
    L//=(L & (-L))
    R//=(R & (-R))
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
            
    ANS=1<<60
    while L!=R:
        if L > R:
            ANS=min(ANS , SEG[L])
            L+=1
            L//=(L & (-L))
        else:
            R-=1
            ANS=min(ANS , SEG[R])
            R//=(R & (-R))
    return ANS
Q=int(input())
for queries in range(Q):
    k,l,r,c=map(int,input().split())
    if k==1:
        adds(l-1,r,c)
    else:
        print(getvalues(l-1,r))
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX