結果

問題 No.2065 Sum of Min
ユーザー 👑 Kazun
提出日時 2022-09-02 22:16:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 891 ms / 2,000 ms
コード長 4,198 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 122,784 KB
最終ジャッジ日時 2024-11-16 04:01:51
合計ジャッジ時間 16,006 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Binary_Indexed_Tree():
def __init__(self, L, calc, unit, inv, index=1):
""" calc N Binary Indexed Tree
calc: (2, )
unit: calc (x+e=e+x=xe)
inv : calc (1, x+inv(x)=inv(x)+x=e inv(x))
"""
self.calc=calc
self.unit=unit
self.inv=inv
self.index=index
N=len(L)
d=max(1,(N-1).bit_length())
k=2**d
X=[None]+[unit]*k
self.num=k
self.depth=d
if L:
for i in range(len(L)):
p=i+1
while p<=k:
X[p]=self.calc(X[p],L[i])
p+=p&(-p)
self.data=X
def index_number(self, k, index=1):
""" k .
k :
index:
"""
return self.sum(k,k,index)
def add(self, k, x, index=1):
""" k x , .
k :
x :
index:
"""
data=self.data; calc=self.calc
p=k+(1-index)
while p<=self.num:
data[p]=calc(self.data[p],x)
p+=p&(-p)
def update(self, k, x, index=1):
""" k x , .
k:
x:
"""
a=self.index_number(k,index)
y=self.calc(self.inv(a),x)
self.add(k,y,index)
def sum(self, From, To, index=1):
""" From To .
※From!=1使, .
From :
To :
index:
"""
alpha=max(1,From+(1-index))
beta=min(self.num,To+(1-index))
if alpha>beta:
return self.unit
elif alpha==1:
return self.__section(beta)
else:
return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))
def __section(self,x):
""" B[1]+...+B[x] . """
data=self.data; calc=self.calc
S=self.unit
while x>0:
S=calc(data[x],S)
x-=x&(-x)
return S
def all_sum(self):
return self.data[-1]
def binary_search(self, cond, index=1):
""" cond(B[1]+...+B[k]) k .
cond: 調
※ cond(unit)=True index-1
※ cond(B[1]+...+B[k]) k self.num+index
"""
if cond(self.unit):
return index-1
j=0
r=self.num
t=r
data=self.data; calc=self.calc
alpha=self.unit
for _ in range(self.depth+1):
if j+t<=self.num:
beta=calc(alpha,data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j+index
def __getitem__(self,index):
if isinstance(index,int):
return self.index_number(index,self.index)
else:
return [self.index_number(t,self.index) for t in index]
def __setitem__(self,index,val):
self.update(index,val,self.index)
#==================================================
from operator import add, itemgetter,neg
import sys
input=sys.stdin.readline
write=sys.stdout.write
N,Q=map(int,input().split())
A=[0]+list(map(int,input().split()))
AA=[(i,A[i]) for i in range(1,N+1)]
AA.sort(key=itemgetter(1))
Query=[]
for q in range(Q):
L,R,X=map(int,input().split())
Query.append((X,L,R,q))
Query.sort(key=itemgetter(0),reverse=True)
B0=Binary_Indexed_Tree(A.copy(),add,0,neg,0)
B1=Binary_Indexed_Tree([0]*(N+1), add, 0, neg, 0)
Ans=[0]*Q
for x,l,r,q in Query:
while bool(AA) and AA[-1][1]>x:
i,a=AA.pop()
B0.update(i,0,0)
B1.update(i,1,0)
Ans[q]=B0.sum(l,r,0)+x*B1.sum(l,r,0)
write("\n".join(map(str,Ans)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0