結果
| 問題 | No.875 Range Mindex Query |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-07 10:27:30 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 27,582 bytes |
| コンパイル時間 | 469 ms |
| コンパイル使用メモリ | 82,208 KB |
| 実行使用メモリ | 276,096 KB |
| 最終ジャッジ日時 | 2024-07-22 03:28:21 |
| 合計ジャッジ時間 | 6,095 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
61,304 KB |
| testcase_01 | AC | 97 ms
76,864 KB |
| testcase_02 | AC | 115 ms
77,624 KB |
| testcase_03 | AC | 66 ms
72,784 KB |
| testcase_04 | AC | 84 ms
76,456 KB |
| testcase_05 | AC | 59 ms
69,288 KB |
| testcase_06 | AC | 94 ms
77,052 KB |
| testcase_07 | AC | 103 ms
77,108 KB |
| testcase_08 | AC | 83 ms
76,476 KB |
| testcase_09 | AC | 89 ms
76,552 KB |
| testcase_10 | AC | 112 ms
77,576 KB |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | AC | 1,917 ms
263,736 KB |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
ソースコード
# 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がでてますがどうしようもないです。
# [t1]https://atcoder.jp/contests/arc033/tasks/arc033_3 TLE
# [t2]https://yukicoder.me/problems/no/875
# [t5]https://yukicoder.me/problems/no/877
# [t6]https://atcoder.jp/contests/abc127/tasks/abc127_f
# [t7]https://atcoder.jp/contests/abc241/tasks/abc241_d
# 加えて遅延セグ木特有のテストは以下。特にt11はたくさんの基本的問題が含まれていますので、重要です。
# [t11]https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2
# [t12]https://yukicoder.me/problems/no/1234
# [t13]https://yukicoder.me/problems/no/1099
# [t14]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)]
"""
# 遅延伝搬セグメント木のクラス。
#区間更新を可能にしたセグメント木です。ただし区間更新以外はすべて定数倍以上通常のセグメント木よりも遅いので、区間更新が不要なときは通常のセグメント木やBITを使ってください。
# 構築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)
#作用素を管理するlazyを生成する。treeと同じサイズでtree[k]とlazy[k]は対応している。lazyの要素は[f,flag,length]となっている。fは作用素の値である。
#flagは上書きフラグである。これは上書きのときはTrueで加算のときはFalseになる。これはmapping,compositionのときに確認する。
#lengthはlazy[k]が管理する区間の長さである。これもlazyに管理させる。これはmappingでlazyを作用させてtreeに反映させるときに使う。ただしmin,maxなど区間長が不要な場合にはこの値は常に1になるようにrequired_length=Falseを設定する。
self.lazy = [[0, False,1] for _ in range(self.N + self.N)]
# 区間長管理専用のリスト。これは__init__で生成されてから今後変更されません。区間長は全部を1にした数列の区間和と考えればよいです。
#self.length = [None] * (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.lazy[i][2] = self.lazy[i << 1][2] + self.lazy[i << 1 | 1][2]
else:
self.lazy[i][2]=1
#mappingは作用fを要素sに作用させるメソッドです。f:s->r。上書きフラグを見て返す値を決めます。fにはself.lazy,sにはself.treeの要素が入る想定になっています。
def _mapping(self,f,s)->int:
if f[1]:
#上書きならfで上書き。区間長f[2]をかけるのを忘れずに。
return f[0]*f[2]
else:
#この場合は和
return f[0]*f[2]+s
#f,gの合成。作用順はf->g。つまりgの上書きflagで判断する
def _composition(self,f,g)->list:
if not g[1]:
return [f[0]+g[0],f[1],f[2]]
else:
return g
#kの値を返します。これは上からちゃんと順番に見ていって初めて意味があるので、get(k)とは違うことに注意してください。
def _evaluate_at(self,k):
return self._mapping(self.lazy[k],self.tree[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])
# 反映させたlazyはリセットする。上書きflagはFalseに
self.lazy[k] = [0, False,self.lazy[k][2]]
#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):
#lazyを経由しないで直接treeを更新すればいいです。
k += self.N
#propagationが必要
self._propagate_from_above(k)
#treeを直接更新
self.tree[k]=x
#再計算
self._recalc_above(k)
# O(log(N))
# Aのk番目の値A[k]にxを加算します。すなわちA[k]+=xと同じ操作です。
# 実装はupdateとほぼ同じ。
def add(self, k, x):
k += self.N
self._propagate_from_above(k)
# 加算
self.tree[k] += x
self._recalc_above(k)
# 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:
#updateでは上書きflagをTrueでいれます。
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:
#加算では上書きflagをFalseでいれます。
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)
############################################################
################以下はテスト用のコード########################
############################################################
# 隣接行列を入力することで出力します。ただし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(1, (len(tree) + 1) // 2):
left, right = 2 * i, 2 * i + 1
edges[i].append(left)
edges[i].append(right)
labels = [str(t) for t in enumerate(tree)]
return edges, labels
"""
lst=LazySegmentTree([0,0,0,0,0,0],operator=min,identity=float('inf'),required_length=False)
lst.add_range(1,4,1)
print(lst.lazy)
print(lst.query(1,2))
#print(lst.query(0,4))
#edges,labels=tree_to_edges(lst.tree)
#visualize(edges,dir=False,labels=labels,root=1)
"""
##############################################
# テストの実行
##############################################
# [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)
numst.update(i,1)
les.sort()
for _,d in les:
print(d)
"""
# [t6]
"""
Q=int(input())
#aをSにひとつずつ追加していくことを考える。最小値はa[i]がn個Sに追加された時点では、区間[a[(n-1)//2],a[ceil((n-1)/2)]となる（奇数のときは点）（まずウルフラムとかでplotしてみるのが大事）
#よってこの区間を高速に求められればOKである。
#これは言い換えると、Sの元の中で(n-1)//2+1番目に小さい元を求めるということである。これはSegmentTreeの典型的問題である。[t2]と同じように求めることが可能、と思ったけど、aの範囲がでかすぎて同じ手法では無理
#そこで座標圧縮を使います。すなわちaの座標を小さい順に1,2,3...と番号をふっていく。こうすればQまでしか座標は必要でないので、[t2]と同じように解くことができます。
a=[]
query=[]
cnt=0
for _ in range(Q):
q=tuple(map(int,input().split()))
query.append(q)
if q[0]==1:
_,ai,_=q
a.append(ai)
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,comp2a=coordinate_comp(a,comp_to_original=True)
#セグメントツリーを作る。サイズは圧縮された座標の中で一番大きいものと等しくすればいい。すなわちlen(comp2a)です
st=SegmentTree([0]*(len(comp2a)+1),operator=lambda x,y:x+y)
#クエリに答えていきます
#追加されたaの数
n=0
#最初の定数函数の時点では全区間で最小値0
prevminv=0
prevleft=-float('inf')
prevright=float('inf')
for q in query:
if q[0]==1:
_,a,b=q
#求値クエリが来てから最小値を求めるのではなくて、更新クエリが来るたびにその時点での最小値をもっておくようにします。なぜならひとつ前の最小値を知っていないと新たな点が追加されたときの最小値を更新できないからです。
#更新クエリではaをstにいれます。ただし圧縮してから。ただし同じ座標には加算していきますから、addです。
st.add(a2comp[a],1)
n+=1
sumb+=b
#二分探索して(n-1)//2とceil((n-1)/2)番目に小さいaの値を探しに行きます
left=0
right=len(comp2a)+1
while left+1<right:
mid=left+(right-left)//2
if st.query(0,mid)>=(n-1)//2+1:
#このときは左による
right=mid
else:
left=mid
#このleftが最小値を与えるx座標です
minleft=left
#次は区間の右。ただしnが奇数のときは等しいので求めなくていい
search=-(-(n-1)//2)+1
if n%2==0:
left=0
right=len(comp2a)+1
while left+1<right:
mid=left+(right-left)//2
if st.query(0,mid)>=-(-(n-1)//2)+1:
#このときは左による
right=mid
else:
left=mid
minright=left
else:
minright=minleft
#よって最小値を与える区間は[minleft,minright]になっています。xとしては小さい方を出すのでminx=minleftです。
#次に実際の最小値は新しく追加した点が前回の区間に含まれていれば変更なし、含まれていなければ前回の区間の近い方との距離と等しいです（解析的に計算してわかる）。
#ただし距離はもとの座標で求めなさいね
if prevleft<=a2comp[a]<=prevright:
#このとき前回の区間に含まれている。bも忘れずに
minles=prevminv+b
else:
#前回に含まれていなければ
o_prevleft=comp2a[prevleft]
o_prevright=comp2a[prevright]
minles=prevminv+min(abs(o_prevleft-a),abs(o_prevright-a))+b
prevminv=minles
prevleft=minleft
prevright=minright
else:
#求値クエリが来たら時点での最小値をprintします。
print(comp2a[minleft],minles)
"""
# [t7]
"""
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)
st=SegmentTree([0]*(len(x2comp)+1),operator=lambda x,y:x+y)
#セグメント木の言葉でいうと、まず全要素のうちk番目に小さい要素とは、区間和[0,i]がkになるような最小のiということになります。
#なのでx以上の要素のうち大きい方からk番目の値とは区間和[x,i]がkになるようなiのうち最小の値となります。
for query in queries:
if query[0]==1:
st.add(x2comp[query[1]],1)
elif query[0]==2:
_,x,k=query
x=x2comp[x]
#区間和[i,x+1)がkになるようなiのうち最大のiを求める
if st.query(None,x+1)<k:
print(-1)
else:
left=0
right=x+1
while left+1<right:
mid=left+(right-left)//2
if st.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 st.query(x,None)<k:
#このとき存在しない
print(-1)
else:
left=x
right=len(x2comp)+1
while left+1<right:
mid=left+(right-left)//2
if st.query(x,mid)>=k:
#このときは左による
right=mid
else:
left=mid
#leftが答えです
print(comp2x[left])
"""
#[t8]
"""
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:
_,i=q
print(lst.get(i-1))
"""
# [t9]
"""
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))
"""
#[t10]RMQRUQ
"""
# この問題は0-indexed
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))
"""
#[t11]RMQRAQ
"""
# この問題は0-indexed
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))
"""
# [t12]
"""
# この問題は0-indexed
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)
for q in queries:
#print(lst.tree, lst.lazy)
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))
"""
#[t12]
"""
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))
"""