結果

問題 No.877 Range ReLU Query
ユーザー floraflora
提出日時 2022-03-02 23:46:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,090 ms / 2,000 ms
コード長 5,353 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 115,200 KB
最終ジャッジ日時 2024-11-08 10:42:49
合計ジャッジ時間 12,312 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,608 KB
testcase_01 AC 73 ms
68,992 KB
testcase_02 AC 68 ms
66,688 KB
testcase_03 AC 95 ms
76,288 KB
testcase_04 AC 48 ms
59,520 KB
testcase_05 AC 58 ms
62,464 KB
testcase_06 AC 59 ms
63,104 KB
testcase_07 AC 61 ms
61,568 KB
testcase_08 AC 105 ms
76,288 KB
testcase_09 AC 52 ms
59,904 KB
testcase_10 AC 73 ms
66,304 KB
testcase_11 AC 1,021 ms
113,040 KB
testcase_12 AC 885 ms
108,152 KB
testcase_13 AC 738 ms
101,624 KB
testcase_14 AC 768 ms
103,952 KB
testcase_15 AC 1,072 ms
115,200 KB
testcase_16 AC 1,024 ms
111,076 KB
testcase_17 AC 1,047 ms
112,148 KB
testcase_18 AC 1,044 ms
110,472 KB
testcase_19 AC 1,013 ms
111,152 KB
testcase_20 AC 1,090 ms
114,436 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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)
0