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