結果

問題 No.879 Range Mod 2 Query
ユーザー potoooooooopotoooooooo
提出日時 2019-09-07 00:03:46
言語 OCaml
(5.1.0)
結果
AC  
実行時間 1,992 ms / 3,000 ms
コード長 4,252 bytes
コンパイル時間 387 ms
コンパイル使用メモリ 22,400 KB
実行使用メモリ 55,552 KB
最終ジャッジ日時 2024-04-17 08:51:21
合計ジャッジ時間 20,492 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 6 ms
5,376 KB
testcase_02 AC 8 ms
5,888 KB
testcase_03 AC 7 ms
5,504 KB
testcase_04 AC 8 ms
6,144 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 7 ms
6,144 KB
testcase_08 AC 8 ms
6,016 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 6 ms
5,376 KB
testcase_11 AC 1,992 ms
50,944 KB
testcase_12 AC 1,039 ms
49,536 KB
testcase_13 AC 1,393 ms
49,664 KB
testcase_14 AC 1,280 ms
52,480 KB
testcase_15 AC 1,308 ms
34,304 KB
testcase_16 AC 1,819 ms
54,528 KB
testcase_17 AC 1,861 ms
55,552 KB
testcase_18 AC 1,960 ms
54,528 KB
testcase_19 AC 1,783 ms
54,272 KB
testcase_20 AC 1,771 ms
55,040 KB
testcase_21 AC 1,891 ms
54,656 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 lst a b 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 lst a b x (2*k) l m) (rec_update lst a b x (2*k+1) m r) in
          lst.seg.(k) in
      let _ = rec_update lst a b x 1 0 lst.n in ()
    
    (* query: [a, b) *)
    let query lst a b =
      let rec rec_query lst a b 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 lst a b (2*k) l m) (rec_query lst a b (2*k+1) m r) in
      rec_query lst a b 1 0 lst.n
    let get lst i = query lst i (i+1)
  end

(* 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 (b, prev, post) len =
  let add a x =
    let a_os, a_o, a_es, a_e = a in
    if x mod 2 = 0 then (a_os+x*a_o, a_o, a_es+x*a_e, a_e) 
    else (a_es+x*a_e, a_e, a_os+x*a_o, a_o) in
  let andone a b = 
    let a_os, a_o, a_es, a_e = a in 
    if b = 1 then (a_o, a_o, 0, a_e) else a in
  add (andone (add a prev) b) post
let h a b = 
  let p, q, r = a and s, t, u = b in
  if s = 0 then (p, q, r+t+u)
  else (s, q+r+t mod 2, u)

(* main function *)
let () =
  let n = scan_int() and q = scan_int() in
  let lst = LazySegmentTree.init n (0, 0, 0, 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 (1, 0, 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 (0, 0, 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