結果
問題 |
No.3078 Difference Sum Query
|
ユーザー |
|
提出日時 | 2025-09-30 10:24:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 786 ms / 2,000 ms |
コード長 | 1,582 bytes |
コンパイル時間 | 457 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 116,556 KB |
最終ジャッジ日時 | 2025-09-30 10:24:35 |
合計ジャッジ時間 | 18,605 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
import sys sys.setrecursionlimit(10**7) def ii(): return int(input()) def mi(d=0): return map(lambda x:int(x)-d,input().split()) INF = float("inf") MOD = 998244353 def answer(s): print(s) exit() def cross(xy): x,y = xy return (x+1,y),(x-1,y),(x,y+1),(x,y-1) ################################################ class FenwickTree: def __init__(self,size): self.size = size self.arr = [0]*size self.count = [0]*size def sum(self,index): s = 0 index += 1 while index>0: s += self.arr[index-1] index -= index&(-index) return s def add(self,index,value): i = index+1 while i<=self.size: self.arr[i-1] += value self.count[i-1] += 1 i += i&(-i) def countRange(self,left,right): l,r = left+1,right+1 lc,rc = 0,0 while l > 0: lc += self.count[l-1] l -= l&(-l) while r > 0: rc += self.count[r-1] r -= r&(-r) return rc-lc n,q = mi() a = list(map(lambda x:(int(x[1]),x[0]),enumerate(input().split()))) rs = [0] for aa in a: rs.append(rs[-1] + aa[0]) a.sort() query = [] for qi in range(q): query.append((list(mi()),qi)) query.sort(key=lambda x:x[0][2]) # print(query) ai = 0 tree = FenwickTree(n) ans = [0]*q for qq,qi in query: l,r,x = qq while ai < n and a[ai][0] <= x: aa,index = a[ai] ai += 1 tree.add(index,aa) count = tree.countRange(l-2,r-1) small = tree.sum(r-1) - tree.sum(l-2) big = rs[r]-rs[l-1] - small # print(small,big,count) ans[qi] = x*count-small + big-x*(r-l+1-count) # print(tree.arr) for aa in ans: print(aa)