open System open System.Collections.Generic [] module Cin = let read f = stdin.ReadLine() |> f let reada f = stdin.ReadLine().Split() |> Array.map f let readChars() = read string |> Seq.toArray let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString())) [] module Cout = let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput())) let print (s: string) = writer.Write s let println (s: string) = writer.WriteLine s let inline puts (s: ^a) = string s |> println type SegmentTree<'Monoid> = { /// 実データの要素数(葉ノードの数) size: int height: int /// モノイドの単位元 unity: 'Monoid /// 1-indexed([0]は使用しない) nodes: 'Monoid array /// 二項演算 merge: Merge<'Monoid> } and Merge<'a> = 'a -> 'a -> 'a [] [] module SegmentTree = let internal sizeAndHeight n = let rec loop sAcc hAcc = if sAcc < n then loop (sAcc <<< 1) (hAcc + 1) else (sAcc, hAcc) loop 1 0 let internal parent i = i / 2 let internal leftChild i = (i <<< 1) + 0 let internal rightChild i = (i <<< 1) + 1 let internal leafIdx tree k = k + tree.size let init (n: int) (f: Merge<'Monoid>) (unity: 'Monoid) = let size, height = sizeAndHeight n let nodes = Array.init (size * 2) (fun _ -> unity) { SegmentTree.size = size height = height unity = unity nodes = nodes merge = f } let build (sq: 'Monoid seq) tree: unit = let sq = Seq.indexed sq for (i, s) in sq do let li = leafIdx tree i tree.nodes.[li] <- s /// 一点更新 let update k x tree: unit = let k = leafIdx tree k let nodes = tree.nodes nodes.[k] <- x // 子から親に伝搬 let mutable p = k while p > 0 do p <- parent p let lc, rc = leftChild p, rightChild p nodes.[p] <- tree.merge nodes.[lc] nodes.[rc] let rec internal queryCore (a: int) (b: int) (k: int) (l: int) (r: int) tree: 'Monoid = if r <= a || b <= l then tree.unity elif a <= l && r <= b then tree.nodes.[k] else let lc, rc, mid = leftChild k, rightChild k, (l + r) >>> 1 let lv = queryCore a b lc l mid tree let rv = queryCore a b rc mid r tree tree.merge lv rv let get k tree = let k = leafIdx tree k tree.nodes.[k] let query a b tree: 'Monoid = queryCore a b 1 0 tree.size tree let main() = let [| N; Q |] = reada int let A = reada int |> Array.indexed let f x y = let xi, xv = x let yi, yv = y if xv < yv then x else y let e = Int32.MaxValue, Int32.MaxValue let seg = SegmentTree.init N f e SegmentTree.build A seg for i in 0 .. Q - 1 do let [| q; l; r |] = reada int let l, r = l - 1, r - 1 match q with | 1 -> let li, lv = seg |> SegmentTree.get l let ri, rv = seg |> SegmentTree.get r seg |> SegmentTree.update l (ri, lv) seg |> SegmentTree.update r (li, rv) | _ -> let i, v = seg |> SegmentTree.query (l + 1) (r + 2) puts (i + 1) () main() writer.Close()