結果
| 問題 |
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)