結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー potoooooooo
提出日時 2019-09-06 21:30:00
言語 OCaml
(5.2.1)
結果
AC  
実行時間 266 ms / 2,000 ms
コード長 2,322 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 21,504 KB
実行使用メモリ 23,680 KB
最終ジャッジ日時 2024-10-09 00:49:22
合計ジャッジ時間 3,681 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let print_int n = Printf.printf "%d\n" n

(* zero-based numbering *)
module SegmentTree :
  sig
    type 'a st
    val init   : int -> ('a -> 'a -> 'a) -> 'a -> 'a st
    val set    : 'a st -> int -> 'a -> unit
    val build  : 'a st -> unit
    val update : 'a st -> int -> 'a -> unit
    val query  : 'a st -> int -> int -> 'a
    val get    : 'a st -> int -> 'a
  end =
  struct
    type 'a st = {n: int; func: ('a -> 'a -> 'a); seg: 'a array; id: 'a}
    let get_n _n =
      let rec loop n ret = if ret < n then loop n (ret*2) else ret in loop _n 1
    let init _n _func _id =
      let _n = get_n _n in {n = _n; func = _func; seg = Array.make (_n*2) _id; id = _id}
    let set st i x = st.seg.(st.n+i) <- x
    let merge st par = st.seg.(par) <- st.func st.seg.(par*2) st.seg.(par*2+1)
    let build st =
      let rec loop i = 
        if i = 0 then () else let _ = merge st i in loop (i-1) in
      loop (st.n-1)
    let update st i x =
      let _ = set st i x in
      let k = i + st.n in
      let rec loop i =
        if i = 0 then () else let _ = merge st i in loop (i/2) in
      loop (k/2)
    (* query: [a, b) *)
    let query st a b =
      let rec loop a b l r =
        if a >= b then st.func l r
        else
          let l = if a land 1 = 0 then l else st.func l st.seg.(a) in
          let r = if b land 1 = 0 then r else st.func st.seg.(b-1) r in
          loop ((a + a land 1) / 2) ((b - b land 1) / 2) l r in
      loop (a+st.n) (b+st.n) st.id st.id
    let get st i = st.seg.(st.n+i)
  end

(* sample code (AOJ Course Range Minimum Query) *)
let () =
  let n = scan_int() and q = scan_int() in
  let merge (a, ai) (b, bi) = if a < b then (a, ai) else (b, bi) in
  let st = SegmentTree.init n merge (2147483647, -1) in
  let _ = 
    for i = 0 to n-1 do
      let a = scan_int() in
      SegmentTree.set st i (a, i)
    done in
  let _ = SegmentTree.build st in
  for i = 1 to q do
    let com = scan_int() and x = scan_int() and y = scan_int() in
    if com = 1 then 
      let s, si = SegmentTree.get st (x-1) in
      let t, ti = SegmentTree.get st (y-1) in
      let _ = SegmentTree.update st (x-1) (t, x-1) in
      SegmentTree.update st (y-1) (s, y-1)
    else
      let x, xi = SegmentTree.query st (x-1) y in
      print_int (xi+1)
  done
0