結果

問題 No.877 Range ReLU Query
ユーザー floraflora
提出日時 2022-03-01 19:40:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,768 ms / 2,000 ms
コード長 14,756 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 173,092 KB
最終ジャッジ日時 2024-11-08 10:40:45
合計ジャッジ時間 18,634 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
52,736 KB
testcase_01 AC 95 ms
76,032 KB
testcase_02 AC 88 ms
73,856 KB
testcase_03 AC 112 ms
76,672 KB
testcase_04 AC 56 ms
61,824 KB
testcase_05 AC 66 ms
65,024 KB
testcase_06 AC 73 ms
68,096 KB
testcase_07 AC 66 ms
65,536 KB
testcase_08 AC 112 ms
76,544 KB
testcase_09 AC 56 ms
61,696 KB
testcase_10 AC 86 ms
71,552 KB
testcase_11 AC 1,638 ms
157,908 KB
testcase_12 AC 1,417 ms
149,676 KB
testcase_13 AC 1,133 ms
134,584 KB
testcase_14 AC 1,178 ms
134,668 KB
testcase_15 AC 1,768 ms
169,700 KB
testcase_16 AC 1,681 ms
167,504 KB
testcase_17 AC 1,760 ms
169,848 KB
testcase_18 AC 1,699 ms
167,844 KB
testcase_19 AC 1,590 ms
164,272 KB
testcase_20 AC 1,721 ms
173,092 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# ref
# 実装は基本的に[2],[3]を参照。ただし0-indexedにしているところとidentityの指定を不要にしているところだけ少し違う
# [1]https://qiita.com/R_olldIce/items/32cbf5bc3ffb2f84a898
# [2]https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B71
# [3]https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf
# テストケース。以下はぜんぶ通しました。
# [t1]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp
# [t2]https://atcoder.jp/contests/arc033/tasks/arc033_3
# [t3]https://judge.yosupo.jp/problem/staticrmq
# [t4]https://yukicoder.me/problems/no/875
# [t5]https://yukicoder.me/problems/no/877

# 実装上の工夫：
# 非再帰（パフォーマンス（メモリ、時間ともに）上微妙にいい、stackで書いたものとかではない）
# nodeの数を2のべきにしない（微妙にメモリ節約。あと無駄なものを持たなくていいので微妙に気持ちがいい）
# またnodeの数を2のべきにしなくていいと、identityの指定が不要になり、うれしい（ただしidentityの指定を不要にするとqueryの実装はちょっとだけ複雑になる）。
# 交換法則は仮定しない（ただし結合法則は仮定される、例えば引き算や割り算は結合法則が満たされないためだめ、行列の積とかはいける）
# 0-indexed（[3]に0-indexedだと親子の添字を求めるのが面倒とあるがそんなことはない。ただbitシフトだけではできないのでかすかにパフォーマンスが下がる可能性はある）


# よく使うoperatorと単位元のリスト。
"""
最小値
operator=min, identity=float('inf')
最大値
operator=max, identity = -float('inf')
区間和
operator=lambda x, y: x + y,identity = 0
区間積
operator=lambda x, y: x * y, identity = 1
最大公約数
operator=math.gcd, identity = 0
"""


# セグメント木のクラス。構築O(N),update O(log(N)),query O(log(N))
class SegmentTree:
	# O(N)
	# 初期化です。デフォルトはRMQにしてあります。適切なoperatorを指定してください。
	def __init__(self, A, operator=min):
		"""
		A:いま扱う配列
		operator:いま考える二項間演算子。交換法則は仮定しない
		identity:operatorに対応する単位元
		"""

		# ちなみに0-indexでnode iの親:(i-1)//2,左の子:2*i+1,右の子:2*i+2です。
		# ほとんど意味はないと思うが、bit演算のほうがかすかに速いきがするので、親:(i-1)>>1,左の子:i<<1|1,右の子(i<<1)+2と書くことにする。
		# セグメント木は完全二分木ですから、リストで木の要素を管理することができます。
		# 要素数
		self.N = len(A)
		# operator
		self.operator = operator
		# 木を成すサイズ2N-1の配列を作る。このときidentityで初期化する
		self.tree = [None] * (2 * self.N - 1)
		# 初期化は葉、すなわちtreeの後ろからN個の部分にAの値を配置する。
		for i, a in enumerate(A, self.N - 1):
			self.tree[i] = a
		# たつの子にoperatorを作用したものを親にするという操作を繰り返す。ここでindexの大きい方からやっていけば葉から上にたどることができる。
		for i in range(self.N - 2, -1, -1):
			# [0,N-2]の逆順ループ。親の値をふたつの子のoperatorから決めます。ここで左右という順番でいれないとだめなことには注意ね。
			self.tree[i] = self.operator(self.tree[i << 1 | 1], self.tree[(i << 1) + 2])


	# O(log(N))
	# Aのk番目の値をxに変更します。
	def update(self, k, x):
		# A[k]に対応するのはtree[k+self.N-1]ですので、そこから初めてrootに到達するまで親に向かいます
		k += self.N - 1
		# 更新
		self.tree[k] = x
		# rootはk=0ですので正である間ループすればOKです
		while k > 0:
			# 親のindex。
			k = (k - 1) >> 1
			# 親の値を書き直す
			self.tree[k] = self.operator(self.tree[k << 1 | 1], self.tree[(k << 1) + 2])


	# O(log(N))
	# 半開区間[left,right)において、operatorで指定された演算の値を返します。
	def query(self, left, right):
		# left,rightに対応するtreeのindex
		left += self.N - 1
		right += self.N - 1
		# 左右の値
		vl = None
		vr = None
		# 非再帰の実装ではleaf側からrootに向かっていくのがポイントです。[2]の図がわかりやすいです。
		# [left,right)の外側から値を確定させていくイメージ。どんどん内側によせていき、leftとrightが重なったら終わり
		while left < right:
			if left & 1 == 0:
				# leftが偶数なら、その区間を確定させる
				if vl is None:
					# 何もなければその値自体を入れる
					vl = self.tree[left]
				else:
					# あればもとの値と演算
					vl = self.operator(vl, self.tree[left])
				# 次は右の親に移動するのでLを足しておく
				left += 1

			if right & 1 == 0:
				# rightが偶数なら、-1してから確定させる
				right -= 1
				if vr is None:
					vr = self.tree[right]
				else:
					# 積の順番には注意ね
					vr = self.operator(self.tree[right], vr)
			# 親を見る
			left = (left - 1) >> 1
			right = (right - 1) >> 1

		# 最後にvlとvrの演算を返す。ただしどちらもNoneなら、区間が空集合になっているのでNoneを返す。片側がNoneならNoneじゃないほうを返すことにする。
		if vl is None and vr is None:
			return None
		elif vl is None:
			return vr
		elif vr is None:
			return vl
		else:
			# ここでも演算の順番に注意
			return self.operator(vl, vr)

	# O(1)
	# A[k]と同じ。もとのAのk番目の値を取得します。
	def get(self, k):
		return self.tree[k + self.N - 1]

	# O(1)
	# もとのAはself.treeのself.tree[self.N-1: 2*self.N-1]の部分に埋め込まれています。
	# その範囲を半開区間で返します
	def original_range(self):
		return self.N - 1, 2 * self.N - 1


############################################################
################以下はテスト用のコード########################
############################################################

# 隣接行列を入力することで出力します。ただしweightがTrueのときはweightを出力します。
def visualize(edges, dir, weight=False, root=0, labels=None, idx_perm=(0, 1)):
	"""
	edges: 隣接リスト。ただしweight=Trueのときは[weight,node]という風に入っている必要がある
	dir: 有向グラフかどうか
	weight:グラフの重みを出力するかどうか
	root:木構造のときにはrootで設定したnodeがrootになるように出力します。ただし無向グラフのときのみ意味を持つ
	labels:大きさNの配列で各node番号に対してこのリストの名前で表示される。指定しない場合はnode番号がそのまま表示される
	idx_perm:隣接リストに[weight,node]という順番で入っているなら(0,1)にして逆なら(1,0)にします。その他の場合にもidx_perm[0]をweightのindex,idx_perm[1]をnode番号のidxにします。

	"""
	# importを函数内で実行することで、visualize函数を書いたまま提出してもREがでなくなります。もちろん実行したらREになります。
	import graphviz
	# dirをみてDigraphかGraphかを決める
	if dir:
		G = graphviz.Digraph(format='png')
	else:
		G = graphviz.Graph(format='png')

	# labelsがNoneなら
	if labels is None:
		labels = [str(i) for i in range(len(edges))]

	# nodeの形状を決めちゃう。
	G.attr('node', style='filled', color='orange')

	# nodeを作る。edgeを作ればかってにできるが、labelsをいれるために必要。
	for i, label in enumerate(labels):
		G.node(str(i), label=label)

	w_idx, n_idx = idx_perm
	# edgeを作る。nodeはedgeを作ると自動的に生成されるので明示的に作る必要はない
	if dir:
		# 有向グラフ
		if weight:
			# このときは[weight,node]というふうに入っている前提です
			for u, edge in enumerate(edges):
				for e in edge:
					weight, v = e[w_idx], e[n_idx]
					# uからvにひく
					G.edge(str(u), str(v), label=str(weight))
		else:
			# このときは[node]と入っているか[weight]と入っているかは区別分岐させます。
			for u, edge in enumerate(edges):
				for v in edge:
					if isinstance(v, (list, tuple)):
						# このときはnodeのほうを取ります
						v = v[n_idx]
					G.edge(str(u), str(v))
	else:
		# 無効グラフの場合はu,vとv,uがどっちも隣接リストに入っているので、二回入れないように気をつけます
		seen = [False] * len(edges)
		# rootから深さ優先で下っていくような感じでedgeにいれていく必要があります。そうしないと表示が綺麗な木にならないので

		def dfs(n):
			seen[n] = True
			for next in edges[n]:
				if weight:
					# 重みも出力する場合です
					if not seen[next[n_idx]]:
						G.edge(str(n), str(next), label=str(next[w_idx]))
						# 再帰実行
						dfs(next[n_idx])
				else:
					# 重みは出さない場合です。
					if isinstance(next, (list, tuple)):
						next = next[n_idx]
					if not seen[next]:
						# n->nextとedgeを作る必要がある
						G.edge(str(n), str(next))
						# 再帰実行
						dfs(next)
		# rootから実行
		dfs(root)

	# 間違えてこのまま提出しないように
	print("debug mode")
	# 表示
	G.view()


# visualizeを使うためにtreeからedgesとlabelsを求めるメソッドです。graphvizだと先にいれたほうが左の個になるので、そうなるようにする
def tree_to_edges(tree):
	edges = [[] for _ in range(len(tree))]
	for i in range((len(tree) + 1) // 2 - 1):
		left, right = 2 * i + 1, 2 * i + 2
		edges[i].append(left)
		edges[i].append(right)

	labels = [str(t) for t in tree]

	return edges, labels

# 以下のようにvisualizeできます
#edges, labels = tree_to_edges(st.tree)
#visualize(edges, dir=False,labels=labels)


##############################################
# テストの実行
##############################################


# [t1]
# n,q=map(int,input().split())
# query=[]
# for _ in range(q):
#	query.append(list(map(int,input().split())))


# A=[2**31-1]*n
# st=SegmentTree(A,operator=min)
# for com,x,y in query:
#	if com==0:
#		st.update(x,y)
#	else:
#		print(st.query(x,y+1))


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

# 累積和のセグメント木を考えます
# SにXを追加することをupdate(X,1)とします。するとSにある数字でX番目に小さい数は二分探索でも求まります。
# なぜならx番目に小さい数字はst.query(0,i)をiの配列と思ったときにxをbisect_left的に二分探索して、そのときのiが答えになっているからです
# 最初は[0]の配列をいれておく
#st=SegmentTree([0]*200001,operator=lambda x,y:x+y)
# for t,x in query:
#	if t==1:
#		st.update(x,1)
#	else:
#		left=0
#		right=200001
#		while left+1<right:
#			mid=left+(right-left)//2
#			if st.query(0,mid)>=x:
#				#このときは左による
#				right=mid
#			else:
#				left=mid
#		#leftの削除も必要です。いまの場合削除とは0にすることにほかならないので
#		st.update(left,0)
#		print(left)


# [t3]
# N,Q=map(int,input().split())
# a=list(map(int,input().split()))
# query=[]
# for _ in range(Q):
#	query.append(tuple(map(int,input().split())))

# st=SegmentTree(a,min)
# for l,r in query:
#	print(st.query(l,r))


# [t4]
# N,Q=map(int,input().split())
# A=list(map(int,input().split()))
# query=[]
# for _ in range(Q):
#	query.append(tuple(map(lambda x:int(x)-1,input().split())))

# aはすべて異なるので、ある数字の場所を別に覚えておけばいい
# pos={}
# for i,a in enumerate(A):
#	pos[a]=i

# セグメント木
# st=SegmentTree(A,operator=min)
# for flag,l,r in query:
#	if flag==0:
#		#このときl,rを交換する。posも交換しないといけないことに注意
#		pos[st.get(l)],pos[st.get(r)]=pos[st.get(r)],pos[st.get(l)]
#		#セグメント木でも交換する
#		work=st.get(l)
#		st.update(l,st.get(r))
#		st.update(r,work)
#	else:
#		#最小値は
#		print(pos[st.query(l,r+1)]+1)


#[t5]
#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)
##区間和のセグメント木と区間の要素数のセグメント木をどちらも用意します
#sumst=SegmentTree([0]*N,operator=lambda x,y:x+y)
#numst=SegmentTree([0]*N,operator=lambda x,y:x+y)

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

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

#[t5_2]
#t5の別解です。ふたつセグメント木を用意しないで、nodeにリストをもたせる。
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)
#リストの加算を定義する
def sumvec(A,B):
	return [A[0]+B[0],A[1]+B[1]]

#リストを要素として初期化し、operatorにはsumvecをセットする。[0]を要素のvalueで[1]を要素数のカウントのために使うやつだとする。
st=SegmentTree([[0,0] for _ in range(N)],operator=sumvec)

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

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