結果
| 問題 | No.879 Range Mod 2 Query |
| コンテスト | |
| ユーザー |
 potoooooooo
|
| 提出日時 | 2019-09-06 23:40:43 |
| 言語 | OCaml (5.2.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,152 bytes |
| 記録 | |
| コンパイル時間 | 356 ms |
| コンパイル使用メモリ | 22,400 KB |
| 実行使用メモリ | 55,680 KB |
| 最終ジャッジ日時 | 2024-10-09 00:50:53 |
| 合計ジャッジ時間 | 19,138 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 21 |
ソースコード
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_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 =
let a_os, a_o, a_es, a_e = a in (a_o, a_o, 0, a_e) in
add (andone (add a prev)) 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, 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