結果

問題 No.877 Range ReLU Query
ユーザー floraflora
提出日時 2022-03-07 20:40:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,102 ms / 2,000 ms
コード長 8,711 bytes
コンパイル時間 332 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 114,908 KB
最終ジャッジ日時 2024-04-25 22:35:50
合計ジャッジ時間 11,984 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
52,672 KB
testcase_01 AC 61 ms
72,000 KB
testcase_02 AC 57 ms
69,932 KB
testcase_03 AC 76 ms
76,892 KB
testcase_04 AC 43 ms
61,832 KB
testcase_05 AC 47 ms
63,224 KB
testcase_06 AC 50 ms
67,280 KB
testcase_07 AC 46 ms
63,488 KB
testcase_08 AC 81 ms
76,840 KB
testcase_09 AC 44 ms
62,424 KB
testcase_10 AC 55 ms
67,768 KB
testcase_11 AC 991 ms
114,092 KB
testcase_12 AC 886 ms
109,320 KB
testcase_13 AC 715 ms
102,444 KB
testcase_14 AC 761 ms
104,576 KB
testcase_15 AC 1,044 ms
114,908 KB
testcase_16 AC 1,014 ms
111,732 KB
testcase_17 AC 1,038 ms
113,608 KB
testcase_18 AC 1,035 ms
112,664 KB
testcase_19 AC 1,037 ms
111,300 KB
testcase_20 AC 1,102 ms
114,828 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
# [t4]https://yukicoder.me/problems/no/877
# [t5]https://atcoder.jp/contests/arc033/tasks/arc033_3
# [t6]https://yukicoder.me/problems/no/877

# BinaryIndexedTreeです。
# 区間和をO(log(N))で求めることができます。また数列に要素を加算することができます。
# 同じことがセグメント木でもできますが、こっちのほうが速いので、区間和を求めたいときはこっちを使いましょう。updateも実はできて、updateしたいときでもセグメント木よりかなりはやいです。
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)

	# 半開区間[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))
	# 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))
	#a[k]をxに変更します。a[k]=x
	def update(self,k,x):
		#BITだとストレートにupdateできないが、getしてからaddするという方法でできる。#いまのxを打ち消すような値を追加する
		self.add(k,x-self.get(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))


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

# [t2]
"""
N=int(input())
a=list(map(int,input().split()))
#数列の反転数がBITを用いてO(N*log(N))で求められることは暗記しておきましょう。
#いまmax(a[i])が大きく、そのサイズのbitを用意できないので、座標圧縮する
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

a2comp=coordinate_comp(a)
a=[a2comp[ai] for ai in a]
#bitは[min(a),max(a)]の範囲を用意する。いまは座標圧縮したので[0,len(a)]
bit=BinaryIndexedTree([0]*N)
#転倒数
les=0
for j in range(N):
	les+=j-bit.sum(None,a[j])
	bit.add(a[j],1)
print(les)
"""

# [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])
"""


# [t4]
"""
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
		#このときはセグメント木をadd。iはユニークなのでaddでもupdateでもいい
		sumbit.add(i,a)
		cntbit.add(i,1)

les.sort()
for _,d in les:
	print(d)
"""


#[t5]
"""
Q = int(input())
query = []
for _ in range(Q):
	query.append(tuple(map(int, input().split())))

bit=BinaryIndexedTree([0]*200001)
for t,x in query:
	if t==1:
		#なぜかupdateでも通ったけどaddにするのがただしいと思う
		bit.add(x,1)
	else:
		left=0
		right=200001
		while left+1<right:
			mid=left+(right-left)//2
			if bit.sum(0,mid)>=x:
				#このときは左による
				right=mid
			else:
				left=mid
		#leftの削除も必要です。いまの場合削除とは0にすることにほかならないので
		bit.update(left,0)
		print(left)
"""





#[t6]
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)
numbit=BinaryIndexedTree([0]*N)

les=[]
for q in query:
	if len(q)==4:
		x,l,r,i=q
		#このとき区間の和を求める。和から要素数*xを引きます
		les.append([i,sumbit.sum(l-1,r)-x*numbit.sum(l-1,r)])
	else:
		a,i=q
		#このときはセグメント木をupdate
		sumbit.update(i,a)
		numbit.update(i,1)

les.sort()
for _,d in les:
	print(d)
0