結果

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

ソースコード

diff # 

(n,q),a,*e=[[*map(int,s.split())]for s in open(0)]
class segtree():
 n,size,log,d,op,e=1,1,2,[0],None,10**15
 def __init__(self,V,OP,E):
  self.n=len(V);self.op=OP;self.e=E
  self.log=(self.n-1).bit_length()
  self.size=1<<self.log
  self.d=[E for i in range(2*self.size)]
  for i in range(self.n):self.d[self.size+i]=V[i]
  for i in range(self.size-1,0,-1):self.update(i)
 def set(self,p,x):
  assert 0<=p and p<self.n
  p+=self.size;self.d[p]=x
  for i in range(1,self.log+1):self.update(p>>i)
 def get(self,p):
  assert 0<=p and p<self.n
  return self.d[p+self.size]
 def prod(self,l,r):
  assert 0<=l and l<=r and r<=self.n
  sml,smr=self.e,self.e
  l+=self.size;r+=self.size
  while l<r:
   if l&1:sml=self.op(sml,self.d[l]);l+=1
   if r&1:smr=self.op(self.d[r-1],smr);r-=1
   l>>=1
   r>>=1
  return self.op(sml,smr)
 def all_prod(self):
  return self.d[1]
 def max_right(self,l,f):
  assert 0<=l and l<=self.n
  assert f(self.e)
  if l==self.n:return self.n
  l+=self.size;sm=self.e
  while 1:
   while l%2==0:l>>=1
   if not(f(self.op(sm,self.d[l]))):
    while(l<self.size):
     l=2*l
     if f(self.op(sm,self.d[l])):sm=self.op(sm,self.d[l]);l+=1
    return l-self.size
   sm=self.op(sm,self.d[l]);l+=1
   if (l&-l)==l:break
  return self.n
 def min_left(self,r,f):
  assert 0<=r and r<=self.n
  assert f(self.e)
  if r==0:return 0
  r+=self.size;sm=self.e
  while 1:
   r-=1
   while r>1 and r%2:r>>=1
   if not(f(self.op(self.d[r],sm))):
    while r<self.size:
     r=(2*r+1)
     if f(self.op(self.d[r],sm)):sm=self.op(self.d[r],sm);r-=1
    return r+1-self.size
   sm=self.op(self.d[r],sm)
   if (r&-r)==r:break
  return 0
 def update(self,k):
  self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
 def __str__(self):
  return str([self.get(i) for i in range(self.n)])

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

def Del(i):
  global s,t
  s.set(d[a[i]],s.get(d[a[i]])-a[i])
  t.set(d[a[i]],t.get(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=segtree([0]*m,lambda x,y:x+y,0)
t=segtree([0]*m,lambda x,y:x+y,0)
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.prod(0,y)*x-s.prod(0,y)+s.prod(y,m)-t.prod(y,m)*x
print(*ans,sep='\n')
0