結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0