結果

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

ソースコード

diff # 

(n,q),a,*e=[[*map(int,s.split())]for s in open(0)]
import typing
class FenwickTree:
    '''Reference: https://en.wikipedia.org/wiki/Fenwick_tree'''
    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.data = [0] * n
    def add(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    def sum(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        return self._sum(right) - self._sum(left)
    def _sum(self, r: int) -> typing.Any:
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

def Add(i):
  global s,t
  s.add(d[a[i]],a[i])
  t.add(d[a[i]],1)

def Del(i):
  global s,t
  s.add(d[a[i]],-a[i])
  t.add(d[a[i]],-1)

N=2*10**5+10 
M=int(q**0.5)+1
bucket=[[] for i in range(M)]
for i,(l,r,x)in enumerate(e):
  bucket[l*M//n]+=(l-1,r-1,x,i),

for i in range(M):
  if i&1:
    bucket[i].sort(key=lambda x:-x[1])
  else:
    bucket[i].sort(key=lambda x:x[1])

sa={*a}|{x for l,r,x in e}
d={j:i for i,j in enumerate(sorted(sa))}
m=len(d)
s=FenwickTree(m)
t=FenwickTree(m)
ans=[0]*q
L=R=res=0
Add(0)
  
for b in bucket:
  for l,r,x,i in b:
    while R<r:R+=1;Add(R)
    while L>l:L-=1;Add(L)
    while R>r:Del(R);R-=1
    while L<l:Del(L);L+=1
    y=d[x]
    ans[i]=t.sum(0,y)*x-s.sum(0,y)+s.sum(y,m)-t.sum(y,m)*x
print(*ans,sep='\n')
0