結果

問題 No.879 Range Mod 2 Query
ユーザー potoooooooopotoooooooo
提出日時 2019-09-06 23:18:38
言語 OCaml
(5.1.0)
結果
MLE  
実行時間 -
コード長 4,018 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 21,888 KB
実行使用メモリ 811,776 KB
最終ジャッジ日時 2024-04-17 08:50:34
合計ジャッジ時間 6,121 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 10 ms
6,944 KB
testcase_02 AC 12 ms
7,040 KB
testcase_03 AC 10 ms
6,944 KB
testcase_04 AC 16 ms
7,680 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 17 ms
7,936 KB
testcase_08 AC 16 ms
7,680 KB
testcase_09 AC 6 ms
6,940 KB
testcase_10 AC 11 ms
7,040 KB
testcase_11 MLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
権限があれば一括ダウンロードができます

ソースコード

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

let g_func x a =
  let a_os, a_o, a_es, a_e = a in
  if x = 0 then (a_o, a_o, 0, a_e)
  else
    if x mod 2 = 0 then (a_os + a_o * x, a_o, a_es + a_e * x, a_e)
    else (a_es + a_e * x, a_e, a_os + a_o * x, a_o)

(* define : propagate function *)
let f (a_os, a_o, a_es, a_e) (b_os, b_o, b_es, b_e) = (a_os+b_os, a_o+b_o, a_es+b_es, a_e+b_e)
let g a x_list len = List.fold_right g_func x_list a
let h a b = b @ a

(* main function *)
let () =
  let n = scan_int() and q = scan_int() in
  let lst = LazySegmentTree.init n (0, 0, 0, 0) [] f g h in
  let _ =
    for i = 0 to n-1 do
      let a = scan_int() in
      if a mod 2 = 0 then LazySegmentTree.set lst i (0, 0, a, 1)
      else LazySegmentTree.set lst i (a, 1, 0, 0)
    done in
  let _ = LazySegmentTree.build lst in
  for i = 1 to q do
    let op = scan_int() in
    if op = 1 then
      let l = scan_int() and r = scan_int() in
      LazySegmentTree.update lst (l-1) r [0]
    else if op = 2 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, _, y, _ = LazySegmentTree.query lst (l-1) r in
      print_int (x+y)
  done
0