結果

問題 No.3078 Difference Sum Query
コンテスト
ユーザー nikoro256
提出日時 2025-03-28 22:53:03
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 898 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 67,892 KB
最終ジャッジ日時 2025-03-28 22:53:07
合計ジャッジ時間 3,735 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.readline
from atcoder import segtree
def Sum(a,b):
    return a+b
N,Q=map(int,input().split())
A=list(map(int,input().split()))
A_s=A[::]
A_s.append(0)
for i in range(1,N):
    A_s[i]+=A_s[i-1]
d=[(A[i],0,i) for i in range(N)]
for i in range(Q):
    l,r,x=map(int,input().split())
    d.append((x,1,l-1,r-1,i))
d.sort()
st_s = segtree.SegTree(Sum,0,[0]*N)
st_c = segtree.SegTree(Sum,0,[0]*N)
ans=[0]*Q
#print(d)
for di in d:
    if len(di)==3:
        st_s.set(di[2],di[0])
        st_c.set(di[2],1)
        continue
    x,_,l,r,i=di
    all_sum = A_s[r]-A_s[l-1]
    down_sum = st_s.prod(l,r+1)
    up_sum = all_sum - down_sum
    all_count = r-l+1
    down_count = st_c.prod(l,r+1)
    up_count = all_count - down_count
    #print(f"down_sum{down_sum} down_count{down_count}")
    ans[i]=(x*down_count-down_sum)+(up_sum-x*up_count)
for i in range(Q):
    print(ans[i])
0