結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
![]() |
提出日時 | 2025-03-28 22:01:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,178 ms / 2,000 ms |
コード長 | 1,239 bytes |
コンパイル時間 | 322 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 171,616 KB |
最終ジャッジ日時 | 2025-03-28 22:02:04 |
合計ジャッジ時間 | 20,118 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
class segtree: def __init__(self,n): self.size=1 while self.size<n: self.size*=2 self.dat=[0]*(self.size*2) def update(self,x,a): x+=self.size self.dat[x]+=a while x>1: x//=2 self.dat[x]=(self.dat[2*x]+self.dat[2*x+1]) def querry(self,u,v): u+=self.size v+=self.size score=0 while u<v: if u&1: score+=self.dat[u] u+=1 if v&1: v-=1 score+=self.dat[v] u//=2 v//=2 return score N,Q=map(int,input().split()) A=list(map(int,input().split())) L=[] G=[[] for i in range(N+1)] D=set() for i in range(N): D.add(A[i]) for i in range(Q): l,r,x=map(int,input().split()) G[l-1].append((i,x,-1)) G[r].append((i,x,1)) D.add(x) result=[0]*Q T={} M=len(D) D=list(D) D.sort() for i in range(M): T[D[i]]=i Zcount=segtree(M+1) Zsum=segtree(M+1) for i in range(1,N+1): z=A[i-1] pos=T[z] Zsum.update(pos,z) Zcount.update(pos,1) for B in G[i]: e,x,t=B[:] pos=T[x] p=0 c1=Zcount.querry(pos,M) w1=Zsum.querry(pos,M) p=w1-c1*x c2=Zcount.querry(0,pos) w2=Zsum.querry(0,pos) p+=c2*x-w2 if t==1: result[e]+=p else: result[e]-=p for i in range(Q): print(result[i])