結果
| 問題 | No.877 Range ReLU Query |
| コンテスト | |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-02 23:47:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,268 ms / 2,000 ms |
| コード長 | 5,353 bytes |
| 記録 | |
| コンパイル時間 | 309 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 114,816 KB |
| 最終ジャッジ日時 | 2024-11-08 10:43:03 |
| 合計ジャッジ時間 | 13,953 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 |
ソースコード
#ref
#[1]蟻本
#[2]http://hos.ac/slides/20140319_bit.pdf
#テストケース
# [t1]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp
# [t2]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp
# [t3]https://atcoder.jp/contests/abc241/tasks/abc241_d
#BinaryIndexedTreeです。
class BinaryIndexedTree:
#O(N*log(N))
#実は初期化はセグメント木より遅い（0じゃない値で初期化する場合には）
#ただしAを全部0にすることもでき、その場合にはO(N)で初期化できるように実装してあります。ただしNのループは回るので定数倍だけ[0]で初期化するよりも遅くなりますが……。
def __init__(self,A):
"""
A: 初期化する配列
"""
#要素数
self.N=len(A)
#BITを管理する木、1-indexedにするので要素数はN+1
self.tree=[0]*(self.N+1)
#Aでtreeを初期化します。このとき0ではaddを実行しないようにします。これにより配列が全部0ならO(N)で初期化できます。
for k,a in enumerate(A):
if a!=0:
self.add(k,a)
#O(log(N))
#a[k]にxを加算します、すなわちa[k]+=xと同じ操作
def add(self,k,x):
#self.treeは1-indexedなので1を足しておく必要がある
k+=1
while k<=self.N:
self.tree[k]+=x
k+=k&-k
#O(log(N))
#半開区間[left,right)の和を求めます。ただし、区間が空集合のときはErrorを吐きます
#ただしleft,rightにNoneを入力すると、例えばleft=Noneにするといまありうる一番左を指定します
def sum(self,left,right):
#Noneなら持ち変える
if left is None:
left=0
if right is None:
right=self.N
if 0<=left<=right<=self.N:
return self._sum(right)-self._sum(left)
else:
raise ValueError("半開区間[{},{})が空集合、もしくはIndex out of rangeです。".format(left,right))
#半開区間[0,i)の和を求めます
def _sum(self,i):
#半開区間であることと0-indexedであることがうまく相殺して蟻本と完全に同じ実装になる。
#sumです
s=0
while i>0:
s+=self.tree[i]
i-=i&-i
return s
#O(log(N))
#セグメント木と違って定数オーダーではないので注意してください。もとの全部の要素を持ってないので、sumで取り出す必要があるからです。
#これを何回も使う場合はセグメント木を使うべきである。
def get(self,k):
return self.sum(k,k+1)
#[t1]
"""
n,q=map(int,input().split())
query=[]
for _ in range(q):
query.append(list(map(int,input().split())))
bit=BinaryIndexedTree([0]*n)
for com,x,y in query:
if com==0:
bit.add(x-1,y)
else:
print(bit.sum(x-1,y))
"""
#[t3]
"""
Q=int(input())
queries=[]
X=[]
for _ in range(Q):
q=tuple(map(int,input().split()))
queries.append(q)
X.append(q[1])
#座標圧縮
def coordinate_comp(A, comp_to_original=False):
if not comp_to_original:
return {a: c for c, a in enumerate(sorted(set(A)))}
else:
comp_to_A, A_to_comp = {}, {}
for c, a in enumerate(sorted(set(A))):
comp_to_A[c]=a
A_to_comp[a]=c
return A_to_comp,comp_to_A
x2comp,comp2x=coordinate_comp(X,comp_to_original=True)
bit=BinaryIndexedTree([0]*(len(x2comp)+1))
#セグメント木の言葉でいうと、まず全要素のうちk番目に小さい要素とは、区間和[0,i]がkになるような最小のiということになります。
#なのでx以上の要素のうち大きい方からk番目の値とは区間和[x,i]がkになるようなiのうち最小の値となります。
for query in queries:
if query[0]==1:
bit.add(x2comp[query[1]],1)
elif query[0]==2:
_,x,k=query
x=x2comp[x]
#区間和[i,x+1)がkになるようなiのうち最大のiを求める
if bit.sum(None,x+1)<k:
print(-1)
else:
left=0
right=x+1
while left+1<right:
mid=left+(right-left)//2
if bit.sum(mid,x+1)>=k:
left=mid
else:
right=mid
#leftが答えです
print(comp2x[left])
else:
_,x,k=query
x=x2comp[x]
#区間和[x,i]がkになるような最小のiを二分探索します
if bit.sum(x,None)<k:
#このとき存在しない
print(-1)
else:
left=x
right=len(x2comp)+1
while left+1<right:
mid=left+(right-left)//2
if bit.sum(x,mid)>=k:
#このときは左による
right=mid
else:
left=mid
#leftが答えです
print(comp2x[left])
"""
N,Q=map(int,input().split())
a=list(map(int,input().split()))
query=[]
for i in range(Q):
#ソートの関係で順番はちょっとかわっている
_,l,r,x=map(int,input().split())
query.append((x,l,r,i))
#a[i]がxよりも小さいならそれは和に寄与しないので、入れておく必要がありません。よってa,xを同時に大きい順にソートして答えればいい。
#クエリにaもいれる
for i in range(N):
query.append((a[i],i))
#ソート
query.sort(reverse=True)
sumbit=BinaryIndexedTree([0]*N)
cntbit=BinaryIndexedTree([0]*N)
les=[]
for q in query:
if len(q)==4:
x,l,r,i=q
#このとき区間の和を求める。和から要素数*xを引きます
sumv,cntv=sumbit.sum(l-1,r),cntbit.sum(l-1,r)
les.append([i,sumv-x*cntv])
else:
a,i=q
#このときはセグメント木をupdate
sumbit.add(i,a)
cntbit.add(i,1)
les.sort()
for _,d in les:
print(d)