結果
問題 | No.2065 Sum of Min |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
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=xを満たすe)inv : 群 calc の逆元 (1変数関数, x+inv(x)=inv(x)+x=e をみたす inv(x))"""self.calc=calcself.unit=unitself.inv=invself.index=indexN=len(L)d=max(1,(N-1).bit_length())k=2**dX=[None]+[unit]*kself.num=kself.depth=dif L:for i in range(len(L)):p=i+1while p<=k:X[p]=self.calc(X[p],L[i])p+=p&(-p)self.data=Xdef 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.calcp=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.unitelif 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.calcS=self.unitwhile x>0:S=calc(data[x],S)x-=x&(-x)return Sdef 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-1j=0r=self.numt=rdata=self.data; calc=self.calcalpha=self.unitfor _ in range(self.depth+1):if j+t<=self.num:beta=calc(alpha,data[j+t])if not cond(beta):alpha=betaj+=tt>>=1return j+indexdef __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,negimport sysinput=sys.stdin.readlinewrite=sys.stdout.writeN,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]*Qfor 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)))