結果

問題 No.876 Range Compress Query
ユーザー potoooooooopotoooooooo
提出日時 2019-09-06 21:53:55
言語 OCaml
(5.1.0)
結果
AC  
実行時間 812 ms / 2,000 ms
コード長 3,614 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 36,608 KB
最終ジャッジ日時 2024-04-17 08:50:18
合計ジャッジ時間 7,544 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 4 ms
6,940 KB
testcase_07 AC 4 ms
6,944 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 AC 4 ms
6,940 KB
testcase_11 AC 804 ms
35,200 KB
testcase_12 AC 658 ms
33,920 KB
testcase_13 AC 639 ms
34,816 KB
testcase_14 AC 763 ms
34,944 KB
testcase_15 AC 520 ms
34,944 KB
testcase_16 AC 793 ms
36,352 KB
testcase_17 AC 781 ms
36,608 KB
testcase_18 AC 812 ms
36,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let scan_array len read_func = Array.init len (fun _ -> read_func())
let print_int n = Printf.printf "%d\n" n

(* zero-based numbering *)
module LazySegmentTree :
  sig
    type ('a, 'b) lst
    val init   : int -> 'a -> 'b -> ('a->'a->'a) -> ('a->'b->int->'a) -> ('b->'b->'b) -> ('a, 'b) lst
    val set    : ('a, 'b) lst -> int -> 'a -> unit
    val build  : ('a, 'b) lst -> unit
    val update : ('a, 'b) lst -> int -> int -> 'b -> unit
    val query  : ('a, 'b) lst -> int -> int -> 'a
    val get    : ('a, 'b) lst -> int -> 'a
  end =
  struct
    (* m: monoid; om: operator monoid *)
    type ('a, 'b) lst = 
      { n: int; seg: 'a array; lazyseg: 'b array; id_m: 'a; id_om: 'b; 
        func_m: 'a -> 'a -> 'a; func_mo: 'a -> 'b -> int -> 'a; func_o: 'b -> 'b -> 'b}
    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 _id_m _id_om _func_m _func_mo _func_o =
      let _n = get_n _n in
      { n = _n; seg = Array.make (_n*2) _id_m; lazyseg = Array.make (_n*2) _id_om;
        id_m = _id_m; id_om = _id_om; func_m = _func_m; func_mo = _func_mo; func_o = _func_o}
    let set lst i x = lst.seg.(lst.n+i) <- x
    let merge lst par = lst.seg.(par) <- lst.func_m lst.seg.(par*2) lst.seg.(par*2+1)
    let build lst =
      let rec loop i =
        if i = 0 then () else let _ = merge lst i in loop (i-1) in
      loop (lst.n-1)
    let propagate lst k len =
      if lst.lazyseg.(k) <> lst.id_om then
        let _ =
          if k < lst.n then
            let _ = lst.lazyseg.(2*k) <- lst.func_o lst.lazyseg.(2*k) lst.lazyseg.(k) in
            lst.lazyseg.(2*k+1) <- lst.func_o lst.lazyseg.(2*k+1) lst.lazyseg.(k) in
        let _ = lst.seg.(k) <- lst.func_mo lst.seg.(k) lst.lazyseg.(k) len in
        lst.lazyseg.(k) <- lst.id_om
    
    (* update: [a, b) *)
    let update lst a b x = 
      let rec rec_update x k l r =
        let _ = propagate lst k (r-l) in
        if b <= l || r <= a then lst.seg.(k)
        else if a <= l && r <= b then
          let _ = lst.lazyseg.(k) <- lst.func_o lst.lazyseg.(k) x in
          let _ = propagate lst k (r-l) in lst.seg.(k)
        else
          let m = (l+r) / 2 in
          let _ = lst.seg.(k) <- lst.func_m (rec_update x (2*k) l m) (rec_update x (2*k+1) m r) in
          lst.seg.(k) in
      let _ = rec_update x 1 0 lst.n in ()
    
    (* query: [a, b) *)
    let query lst a b =
      let rec rec_query k l r =
        let _ = propagate lst k (r-l) in
        if b <= l || r <= a then lst.id_m
        else if a <= l && r <= b then lst.seg.(k)
        else
          let m = (l+r) / 2 in
          lst.func_m (rec_query (2*k) l m) (rec_query (2*k+1) m r) in
      rec_query 1 0 lst.n
    let get lst i = query lst i (i+1)
  end

(* define : propagate function *)
let f (a, af, ab) (b, bf, bb) = 
  if ab <> bf && ab >= 0 && bf >= 0 then (a+b+1, af, bb) else (a+b, af, bb)
let g (a, af, ab) b len = (a, af+b, ab+b)
let h a b = a + b

(* main function *)
let () =
  let n = scan_int() and q = scan_int() in
  let lst = LazySegmentTree.init n (0, -1, -1) 0 f g h in
  let _ =
    for i = 0 to n-1 do
      let a = scan_int() in
      LazySegmentTree.set lst i (0, a, a)
    done in
  let _ = LazySegmentTree.build lst in
  for i = 1 to q do
    let com = scan_int() in
    if com = 1 then
      let l = scan_int() and r = scan_int() and x = scan_int() in
      LazySegmentTree.update lst (l-1) r x
    else
      let l = scan_int() and r = scan_int() in
      let x, _, _ = LazySegmentTree.query lst (l-1) r in
      print_int (x+1)
  done
0