結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー flora
提出日時 2022-03-01 12:32:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 370 ms / 2,000 ms
コード長 10,907 bytes
記録
コンパイル時間 195 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 110,392 KB
最終ジャッジ日時 2024-07-07 18:18:03
合計ジャッジ時間 5,013 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# ref
# 実装は基本的に[2],[3]を参照。ただし0-indexedにしているところだけ違う
# [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

# 実装上の工夫：
# 非再帰（パフォーマンス（メモリ、時間ともに）上微妙にいい、stackで書いたものとかではない）
# nodeの数を平方数にしない（微妙にメモリ節約。あと無駄なものを持たなくていいので微妙に気持ちがいい）
# またnodeの数を平方数にしなくていいと、identityの指定が不要になり、うれしい（ただしidentityの指定を不要にするとqueryの実装はちょっとだけ複雑になる）。
# 交換法則は仮定しない（引き算とかもOK）
# 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)),クエリ 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])

		#print(self.tree)
		#edges, labels = tree_to_edges(self.tree)
		#visualize(edges, dir=False)


	# 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]








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

# 隣接行列を入力することで出力します。ただし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



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



##[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,identity=None)
#for com,x,y in query:
#	if com==0:
#		st.update(x,y)
#	else:
#		print(st.query(x,y+1))


#[t2]
#Q=int(input())




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