結果
| 問題 | No.875 Range Mindex Query |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-01 12:32:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 529 ms / 2,000 ms |
| コード長 | 10,907 bytes |
| コンパイル時間 | 310 ms |
| コンパイル使用メモリ | 87,112 KB |
| 実行使用メモリ | 111,300 KB |
| 最終ジャッジ日時 | 2023-09-22 01:25:53 |
| 合計ジャッジ時間 | 6,863 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 75 ms
71,436 KB |
| testcase_01 | AC | 106 ms
76,640 KB |
| testcase_02 | AC | 122 ms
77,560 KB |
| testcase_03 | AC | 88 ms
75,356 KB |
| testcase_04 | AC | 98 ms
76,592 KB |
| testcase_05 | AC | 82 ms
71,332 KB |
| testcase_06 | AC | 100 ms
76,536 KB |
| testcase_07 | AC | 106 ms
76,776 KB |
| testcase_08 | AC | 91 ms
76,528 KB |
| testcase_09 | AC | 96 ms
76,460 KB |
| testcase_10 | AC | 116 ms
77,556 KB |
| testcase_11 | AC | 529 ms
107,992 KB |
| testcase_12 | AC | 443 ms
100,956 KB |
| testcase_13 | AC | 408 ms
104,900 KB |
| testcase_14 | AC | 402 ms
103,396 KB |
| testcase_15 | AC | 471 ms
109,420 KB |
| testcase_16 | AC | 421 ms
109,876 KB |
| testcase_17 | AC | 437 ms
111,300 KB |
| testcase_18 | AC | 433 ms
111,088 KB |
ソースコード
# 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)