結果

問題 No.3078 Difference Sum Query
コンテスト
ユーザー PNJ
提出日時 2025-03-28 23:03:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,299 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 54,616 KB
最終ジャッジ日時 2025-03-28 23:03:16
合計ジャッジ時間 5,723 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
  # 長さN+1の配列を初期化
  def __init__(self, N):
    self.size = N
    self.bit = [0]*(N+1)

    # i番目までの和を求める
  def sum(self, i):
    if i == 0:
      return 0
    res = 0
    while i > 0:
      res += self.bit[i] # フェニック木のi番目の値を加算
      i -= -i & i # 最も右にある1の桁を0にする
    return res

    # i番目の値にxを足して更新する
  def add(self, i, x):
    while i <= self.size:
      self.bit[i] += x # フェニック木のi番目にxを足して更新
      i += -i & i # 最も右にある1の桁に1を足す
  
N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = set()
query = []
for i in range(Q):
  l, r, x = map(int, input().split())
  query.append((l - 1, r, x))
  S.add(x)
for a in A:
  S.add(a)
S = list(S)
S.sort()
d = {}
for i in range(len(S)):
  d[S[i]] = i + 1
M = len(S)
B = [0 for _ in range(N)]
for i in range(N):
  B[i] = d[A[i]]

for i in range(Q):
  l, r, x = query[i]
  x = d[x]
  query[i] = (l, r, x)

def Mo_algorithm(N, Query):
  Q = len(Query)

  # ブロックの長さを決める,(ブロック順, r, l)の順にソート
  W = int(max(1, N / (((2 * Q) / 3) ** 0.5)))
  data = [0 for i in range(Q)]
  query = [0 for i in range(Q)]
  X = [0 for _ in range(Q)]
  for i in range(Q):
    l, r, x = Query[i]
    block = l // W
    data[i] = (l << 20) | r
    query[i] = (block << 40) | (r << 20) | i
    if block & 1:
      query[i] = (block << 40) + ((-r) << 20) + i
    X[i] = x
  query.sort()

  # 必要な初期解,テーブルなど
  C = BIT(M)
  seg = BIT(M)
  def Mo_add(l):
    i = B[l]
    C.add(i, 1)
    seg.add(i, S[i - 1])
  def Mo_del(l):
    i = B[l]
    C.add(i, -1)
    seg.add(i, -S[i - 1])

  # query処理
  nl, nr = 0, 0
  mask = (1 << 20) - 1
  ans = [0 for _ in range(Q)]
  for que in query:
    i = que & mask
    l = data[i] >> 20
    r = data[i] & mask
    x = X[i]
    while nl > l:
      nl -= 1
      Mo_add(nl)
    while nr < r:
      Mo_add(nr)
      nr += 1
    while nl < l:
      Mo_del(nl)
      nl += 1
    while nr > r:
      nr -= 1
      Mo_del(nr)
    res = seg.sum(M) - 2 * seg.sum(x) - S[x - 1] * (C.sum(M) - 2 * C.sum(x)) 
    ans[i] = res
  return ans

ans = Mo_algorithm(N, query)
for res in ans:
  print(res)
0