結果
問題 | No.3078 Difference Sum Query |
ユーザー |
👑 |
提出日時 | 2025-02-24 19:13:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,768 ms / 2,000 ms |
コード長 | 1,538 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 82,684 KB |
実行使用メモリ | 121,064 KB |
最終ジャッジ日時 | 2025-02-24 22:54:58 |
合計ジャッジ時間 | 23,447 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
def rec_str(a):return"".join(["[",", ".join(rec_str(x)for x in a),"]"])if isinstance(a,list)else str(a) class BIT: def __init__(self,x): if isinstance(x,int): self.N=x self.F=[0]*(x+1) else: self.N=len(x) self.F=[0]*(self.N+1) for j in R(1,self.N+1): i=j-1 self.F[j]=x[i] k=j-(j&-j) while i>k: self.F[j]+=self.F[i] i-=i&-i def copy(self): a=__class__([]) a.N=__self__.N a.F=__self__.F[:] return a def Add(self,i,u): i+=1 while i<=self.N: self.F[i]+=u i+=i&-i def Set(self,i,u):self.Add(i,u-self.Get(i)) def Get(self,i):return self.IntervalSum(i,i) def InitialSegmentSum(self,r): assert(r>-2) a=0 i=min(r+1,self.N) while i: a+=self.F[i] i-=i&-i return a def IntervalSum(self,l,r):return self.InitialSegmentSum(r)-self.InitialSegmentSum(l-1) def list(self):return[self.Get(i)for i in R(self.N)] def __str__(self):return rec_str(self.list()) def Search(self,u):#Computing minimum of j such that InitialSegmentSum(j)>=u or j==N j=s=n=0 p=1<<17 #131072 while p: k=j|p p>>=1 if k<=self.N: n+=self.F[k] if n<u:s,j=n,k else:n=s return j import heapq R=range J=lambda:list(map(int,input().split())) N,Q=J() A=J() B=[J()for q in R(Q)] E=[] for i in R(N):heapq.heappush(E,(A[i],i,0)) for q in R(Q):heapq.heappush(E,(B[q][2],q,1)) bitA=BIT(A) bitX=BIT([-1]*N) C=[0]*Q while E: x,i,t=heapq.heappop(E) if t:l,r,X=B[i];C[i]=bitA.IntervalSum(l-1,r-1)+X*bitX.IntervalSum(l-1,r-1) else:bitA.Set(i,-x);bitX.Set(i,1) for c in C:print(c)