結果

問題 No.1234 典型RMQ
ユーザー floraflora
提出日時 2022-03-07 13:26:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,479 ms / 2,000 ms
コード長 24,783 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 223,836 KB
最終ジャッジ日時 2024-07-22 07:57:12
合計ジャッジ時間 12,872 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,632 KB
testcase_01 AC 39 ms
53,120 KB
testcase_02 AC 40 ms
53,504 KB
testcase_03 AC 38 ms
53,248 KB
testcase_04 AC 39 ms
53,376 KB
testcase_05 AC 38 ms
53,376 KB
testcase_06 AC 1,268 ms
207,068 KB
testcase_07 AC 822 ms
144,812 KB
testcase_08 AC 1,391 ms
223,536 KB
testcase_09 AC 1,182 ms
191,948 KB
testcase_10 AC 1,364 ms
216,456 KB
testcase_11 AC 1,281 ms
205,052 KB
testcase_12 AC 1,154 ms
186,296 KB
testcase_13 AC 839 ms
151,476 KB
testcase_14 AC 1,148 ms
188,000 KB
testcase_15 AC 1,128 ms
177,544 KB
testcase_16 AC 1,438 ms
216,184 KB
testcase_17 AC 1,171 ms
187,836 KB
testcase_18 AC 662 ms
120,724 KB
testcase_19 AC 1,479 ms
223,836 KB
testcase_20 AC 549 ms
128,644 KB
testcase_21 AC 1,340 ms
206,440 KB
testcase_22 AC 604 ms
118,296 KB
testcase_23 AC 577 ms
117,968 KB
testcase_24 AC 596 ms
117,936 KB
testcase_25 AC 601 ms
117,996 KB
testcase_26 AC 634 ms
118,164 KB
testcase_27 AC 37 ms
53,212 KB
testcase_28 AC 36 ms
53,740 KB
testcase_29 AC 37 ms
54,076 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# ref
# [1]https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b72#toc4
# [2]https://smijake3.hatenablog.com/entry/2018/11/03/100133
# [3]https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree/lazy_segment_tree
# [4]https://betrue12.hateblo.jp/entry/2020/09/22/194541
# テストケース。以下はテストケースは確認しました。TLEが多いですがどうしようもないです。AOJはpypy3が使えないですが、pypy3が使えるなら通ると思っていいと思います。
# [t1]https://atcoder.jp/contests/arc033/tasks/arc033_3　TLE
# [t2]https://yukicoder.me/problems/no/875 TLE
# [t3]https://yukicoder.me/problems/no/877 TLE
# [t4]https://atcoder.jp/contests/abc241/tasks/abc241_d TLE
# 加えて遅延セグ木特有のテストは以下。特にt5はたくさんの基本的問題が含まれていますので、重要です。
# [t5]https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2
# [t6]https://yukicoder.me/problems/no/1234
# [t7]https://yukicoder.me/problems/no/1099
# [t8]https://yukicoder.me/problems/no/230

# 実装上の工夫：
# 基本的な実装は普通のセグメント木のときと同じになります。つまり[1]を一番参考にしています。ただ[3],[4]についてもアイデアを参考にしている箇所があります。
# lazyは区間長をかけないで管理しています。すなわちlazy[k]はkが管理する区間のひとマスずつの値が入っています。これをtreeに反映するときにlengthをかけます。treeへの反映はmappingでのみ起こって、lengthはmappingの引数で与えています。これは[3]のアイデアです。
#　operatorと単位元は2セットあることに注意してください。すなわち、通常のセグ木におけるoperatorとidentityの組と、作用素lazyの演算及びidentityの組です
#　例えば最小値を求めるクエリで、区間更新が加算の場合には(operator=min,identity=inf),(lazy_operator=足し算,identity=0)となります。
#　自由度は下がるがパフォーマンス優先でここではlazy_operator,lazy_identityは決め打ちします

#演算が三種類あることは重要です。要素をs,作用素をfとする。sはself.treeの要素で、fはself.lazyの要素と思いましょう。
#1. s間の演算。これはself.operatorで決めたもの
#2. f間の演算。これは上書きであればfを置き換え、加算であればfの和を求めます。[3]でいうcomposition
#3. 要素sに作用素fを作用させる演算。これは上書きならsをfで置き換え、加算ならsとfの和を求めます。[3]でいうmapping
#実装上は1.は引数で与え

# よく使うoperatorと単位元,required_lengthのリスト。
"""
最小値
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
複数の要素をもたせたいときの区間和。ベクトルの和にする。このときはupdate(k,x)のxにも同じ次元のリストを入れます。
operator=lambda A, B: [a+b for a,b in zip(A,B)]
"""


# 遅延伝搬セグメント木のクラス。
# 通常のセグメント木では区間更新、つまりある区間[left,right)の値をxにupdateしたり、xを加算したりするのにはO((right-left)*log(N))かかりますが、この遅延伝搬セグメント木ではO(log(N))で実行が可能です。
# 構築O(N), update O(log(N)), query O(log(N)), 区間更新O(log(N))
class LazySegmentTree:
	# O(N)
	# 初期化です。適切なoperatorを指定してください。また遅延伝搬セグメント木ではidentityの指定が必須になります。
	def __init__(self, A, operator, identity,required_length):
		"""
		A:いま扱う配列
		operator:いま考える二項間演算子。交換法則は仮定しない
		identity:operatorに対応する単位元
		"""
		# 1-indexedで、親:i>>1,左の子:i<<1,右の子i<<1|1です。
		# 要素数
		self.N = len(A)
		# operator,identity
		self.operator = operator
		self.identity = identity
		# 木を成すサイズ2Nの配列を作る。
		self.tree = [None] * (self.N + self.N)
		# 遅延伝搬用の配列を用意します。treeと同じサイズで、同じindexは対応します。こちらは最初にidentityで初期化しておく
		# またlazyはふたつめに上書きフラグを持ちます。これはupdateが入ったときはTrueにして、addのときはFalseになります。
		#つまりlazy[k]=[x,True]なら、kがxになることを意味し、lazy[k]=[x,False]ならkにxが加算されていることを意味する。
		self.lazy = [[0, False] for _ in range(self.N + self.N)]
		# 区間長管理専用のリスト。これは__init__で生成されてから今後変更されません。区間長は全部を1にした数列の区間和と考えればよいです。
		self.length = [1] * (self.N + self.N)
		# 初期化は葉、すなわちtreeの後ろからN個の部分にAの値を配置する。このときふたつ目の要素に区間長を持たせます。
		# すなわちself.tree[i]=[iの要素,iが管理する区間の長さ]となります。
		for i, a in enumerate(A, self.N):
			self.tree[i] = a
		# ふたつの子にoperatorを作用したものを親にするという操作を繰り返す。ここでindexの大きい方からやっていけば葉から上にたどることができる。
		for i in range(self.N - 1, 0, -1):
			# [1,N-1]の逆順ループ。親の値をふたつの子のoperatorから決めます。ここで左右という順番でいれないとだめなことには注意ね。
			# 区間長さは明らかに子の区間の和になります
			self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])
			#required_lengthがTrueのときは長さをいれて、不要のときは全部1にする。
			if required_length:
				self.length[i] = self.length[i << 1] + self.length[i << 1 | 1]

	#mappingは作用fを要素sに作用させるメソッドです。f:s->r。上書きフラグを見て返す値を決めます。fにはself.lazy,sにはself.treeの要素が入る想定になっています。
	#length_fは作用素fの区間長です。fにはこれをかけます。
	def _mapping(self,f,s,length_f):
		"""
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		じゃいお；ｓｇじゃｌ；ｋｇじゃ；ｌｒｋｇじゃお；ｗｇｊ；あぇｊが；ｇじゃｋｌ；ｆｊｋｌ；あｄｓｊ
		"""
		if f[1]:
			#上書きならfで上書き
			return f[0]*length_f
		else:
			#この場合は和
			return f[0]*length_f+s

	#f,gの合成。作用順はf->g。つまりgの上書きflagで判断する
	def _composition(self,f,g):
		if not g[1]:
			return [f[0]+g[0],f[1]]
		else:
			return g


	#kの値を返します。これは上からちゃんと順番に見ていって初めて意味があるので、get(k)とは違うことに注意してください。
	def _evaluate_at(self,k):
		return self._mapping(self.lazy[k],self.tree[k],self.length[k])

	# iで指定されたnodeの上を見て、lazyを伝搬させてきます。
	def _propagate_from_above(self, i):
		# i>>hがiの親のindexになります。逆順にして、上から下の順番に計算するようにします。
		for h in range(i.bit_length() - 1, 0, -1):
			# 逆順ループなのでi>>=1みたいにしてはいけません
			k = i >> h
			# kを伝搬します。treeにいれるときにlengthをかけることに注意してね
			# lazyを子に伝搬させる。上書きフラグを見て更新します。booleanと掛け算できることに注意してね。
			#self.tree[k] = self.operator(self.tree[k] * (not self.lazy[k][1]), self.lazy[k][0] * self.length[k])
			self.tree[k]=self._evaluate_at(k)
			#lazyを子に伝搬させるときは、上書きフラグも伝搬させます。
			self.lazy[k<<1]=self._composition(self.lazy[k<<1],self.lazy[k])
			self.lazy[k<<1|1]=self._composition(self.lazy[k<<1|1],self.lazy[k])
			#self.lazy[k << 1 | 1] = [self.lazy[k << 1 | 1][0] * (not self.lazy[k][1]) + self.lazy[k][0],self.lazy[k<<1|1][1]]
			# 足したlazyはリセットする。上書きflagはFalseに
			self.lazy[k] = [0, False]

	#iの上部を再計算します。
	def _recalc_above(self,i):
		while i > 1:
			i >>= 1
			self.tree[i] = self.operator(self._evaluate_at(i<<1),self._evaluate_at(i<<1|1))

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

	# O(log(N))
	# Aのk番目の値A[k]にxを加算します。すなわちA[k]+=xと同じ操作です。
	# 実装はupdateとほぼ同じ。
	def add(self, k, x):
		k += self.N
		# 加算
		self.tree[k] += x
		while k > 1:
			k >>= 1
			self.tree[k] = self.operator(self.tree[k << 1], self.tree[k << 1 | 1])

	# O(log(N))
	# Aの[left,right)の部分をxに変更します。
	def update_range(self, left, right, x):
		if left is None:
			left = 0
		if right is None:
			right = self.N
		left += self.N
		right += self.N
		L0 = left // (left & -left)
		R0 = right // (right & -right) - 1
		# updateクエリでは最初にpropagateが必要です。
		self._propagate_from_above(L0)
		self._propagate_from_above(R0)
		# lazyを更新する。クエリと同じような感じです。
		while left < right:
			if left & 1:
				#print(self.lazy[left])
				self.lazy[left] = self._composition(self.lazy[left],[x,True])
				left += 1
			if right & 1:
				right -= 1
				self.lazy[right] = self._composition(self.lazy[right],[x,True])
			left >>= 1
			right >>= 1

		# lazyを計算したら上部の再計算が必要です。これは単にL0,R0からスタートして、親に向かって更新していくだけです。
		self._recalc_above(L0)
		self._recalc_above(R0)

	# O(log(N))
	# Aの区間[left:right)の部分に一括でxを加算します。
	def add_range(self, left, right, x):
		if left is None:
			left = 0
		if right is None:
			right = self.N
		left += self.N
		right += self.N
		L0 = left // (left & -left)
		R0 = right // (right & -right) - 1
		# addの場合は再計算のところでlazyを反映させればいいので、最初にpropagateは不要です。
		# ただしupdate_rangeとadd_rangeがまざる場合は必要？
		#self._propagate_from_above(L0)
		#self._propagate_from_above(R0)
		# lazyを更新する。クエリと同じような感じです。
		while left < right:
			if left & 1:
				self.lazy[left] = self._composition(self.lazy[left],[x,False])
				left += 1
			if right & 1:
				right -= 1
				self.lazy[right] = self._composition(self.lazy[right],[x,False])
			left >>= 1
			right >>= 1

		# lazyを計算したら上部の再計算が必要です。これは単にL0,R0からスタートして、親に向かって更新していくだけです。
		self._recalc_above(L0)
		self._recalc_above(R0)

	# O(log(N))
	# 半開区間[left,right)において、operatorで指定された演算の値を返します。
	# ただしleft,rightにNoneを入力すると、例えばleft=Noneにするといまありうる一番左を指定します
	def query(self, left, right):
		if left is None:
			left = 0
		if right is None:
			right = self.N
		# left,rightに対応するtreeのindex
		left += self.N
		right += self.N
		# queryを実行する前に、lazyを上から持ってきます。
		self._propagate_from_above(left // (left & -left))
		self._propagate_from_above(right // (right & -right) - 1)
		# 左右の値
		vl = self.identity
		vr = self.identity
		# 非再帰の実装ではleaf側からrootに向かっていくのがポイントです。[2]の図がわかりやすいです。
		# [left,right)の外側から値を確定させていくイメージ。どんどん内側によせていき、leftとrightが重なったら終わり
		while left < right:
			if left & 1:
				# leftが奇数なら、その区間を確定させる。
				vl = self.operator(vl, self._evaluate_at(left))
				# 次は右の親に移動するのでLを足しておく
				left += 1
			if right & 1:
				# rightが奇数なら、-1してから確定させる
				right -= 1
				# 順番には注意ね
				vr = self.operator(self._evaluate_at(right), vr)
			# 親を見る
			left >>= 1
			right >>= 1

		# 最後にvlとvrの演算を返す。ここでも演算の順番に注意
		return self.operator(vl, vr)

	# O(log(N))
	# A[k]と同じ。もとのAのk番目の値を取得します。ふつうのセグメント木と違ってO(log(N))なので注意。
	def get(self, k):
		#propagateした上でevaluate_atで取得する必要がある。
		k+=self.N
		self._propagate_from_above(k)
		return self._evaluate_at(k)



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

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

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

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

pos={}
for i,a in enumerate(A):
	pos[a]=i

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


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

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

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


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

lst = LazySegmentTree([0] * (len(x2comp) + 1), operator=lambda x, y: x + y, identity=0, required_length=True)

# セグメント木の言葉でいうと、まず全要素のうちk番目に小さい要素とは、区間和[0,i]がkになるような最小のiということになります。
# なのでx以上の要素のうち大きい方からk番目の値とは区間和[x,i]がkになるようなiのうち最小の値となります。
for query in queries:
    if query[0] == 1:
        lst.add(x2comp[query[1]], 1)
    elif query[0] == 2:
        _, x, k = query
        x = x2comp[x]
        # 区間和[i,x+1)がkになるようなiのうち最大のiを求める
        if lst.query(None, x + 1) < k:
            print(-1)
        else:
            left = 0
            right = x + 1
            while left + 1 < right:
                mid = left + (right - left) // 2
                if lst.query(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 lst.query(x, None) < k:
            # このとき存在しない
            print(-1)
        else:
            left = x
            right = len(x2comp) + 1
            while left + 1 < right:
                mid = left + (right - left) // 2
                if lst.query(x, mid) >= k:
                    # このときは左による
                    right = mid
                else:
                    left = mid
            # leftが答えです
            print(comp2x[left])
"""

# [t5]RMQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([(1<<31)-1]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
	if q[0]==0:
		_,i,x=q
		lst.update(i,x)
	else:
		_,s,t=q
		print(lst.query(s,t+1))
"""

# [t5]RSQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
	if q[0]==0:
		_,i,x=q
		lst.add(i-1,x)
	else:
		_,s,t=q
		print(lst.query(s-1,t))
"""

# [t5]RUQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([(1<<31)-1]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
	if q[0]==0:
		_,s,t,x=q
		lst.update_range(s,t+1,x)
	else:
		_,i=q
		print(lst.get(i))
"""

# [t5]RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([0]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
	if q[0]==0:
		_,s,t,x=q
		lst.add_range(s-1,t,x)
	else:
		_,i=q
		print(lst.get(i-1))
"""

#[t5]RMQ and RUQ
"""
n, q = map(int, input().split())
queries = []
for _ in range(q):
	queries.append(list(map(int, input().split())))

lst = LazySegmentTree([2**31-1] * n, operator=min, identity=float('inf'),required_length=False)
for q in queries:
	if q[0] == 0:
		_, s, t, x = q
		lst.update_range(s, t + 1, x)
	else:
		_, s, t = q
		print(lst.query(s, t + 1))
"""

#[t5]RSQ and RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
	if q[0]==0:
		_,s,t,x=q
		lst.add_range(s-1,t,x)
	else:
		_,s,t=q
		print(lst.query(s-1,t))
"""

#[t5]RMQ and RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([0]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
	if q[0]==0:
		_,s,t,x=q
		lst.add_range(s,t+1,x)
	else:
		_,s,t=q
		print(lst.query(s,t+1))
"""

#[t5]RSQ and RUQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
	queries.append(list(map(int,input().split())))

lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
	if q[0]==0:
		_,s,t,x=q
		lst.update_range(s,t+1,x)
	else:
		_,s,t=q
		print(lst.query(s,t+1))
"""

# [t6]

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

lst = LazySegmentTree(a, operator=min, identity=float('inf'),required_length=False)
for q in queries:
	if q[0]==1:
		_,l,r,c=q
		lst.add_range(l-1,r,c)
	else:
		_,l,r,_=q
		print(lst.query(l-1,r))
0