結果

問題 No.877 Range ReLU Query
ユーザー floraflora
提出日時 2022-03-07 20:40:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,355 ms / 2,000 ms
コード長 8,711 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 115,428 KB
最終ジャッジ日時 2024-11-08 10:42:34
合計ジャッジ時間 14,635 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
52,480 KB
testcase_01 AC 80 ms
71,424 KB
testcase_02 AC 77 ms
69,376 KB
testcase_03 AC 102 ms
76,544 KB
testcase_04 AC 56 ms
61,440 KB
testcase_05 AC 62 ms
62,720 KB
testcase_06 AC 67 ms
65,408 KB
testcase_07 AC 63 ms
63,232 KB
testcase_08 AC 108 ms
76,800 KB
testcase_09 AC 59 ms
61,696 KB
testcase_10 AC 73 ms
66,944 KB
testcase_11 AC 1,255 ms
113,708 KB
testcase_12 AC 1,105 ms
109,056 KB
testcase_13 AC 893 ms
101,928 KB
testcase_14 AC 913 ms
104,708 KB
testcase_15 AC 1,336 ms
115,428 KB
testcase_16 AC 1,252 ms
111,728 KB
testcase_17 AC 1,277 ms
112,968 KB
testcase_18 AC 1,282 ms
112,284 KB
testcase_19 AC 1,239 ms
110,920 KB
testcase_20 AC 1,355 ms
114,824 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