OCaml で競技プログラミングをやっている時の知見

items (* Iter.t *)
|> Iter.flat_map (fun j -> ...)
|> Iter.filter (fun j -> ...)
|> Iter.map (fun j -> printf "debug print %d" j; j)

let items = 
  items (* Iter.t *)
  |> Iter.flat_map (fun j -> ...)
  |> Iter.filter (fun j -> ...)
in
items |> Iter.iter (fun j -> printf "debug print %d" j);
items

let modulo = 1000000007
let (+%) a b = (a + b) % modulo
and (-%) a b = (a - b + modulo) % modulo
and( *%) a b = a * b % modulo

let (let+) x k = Iter.flat_map k x
and (let*) x k = Iter.map k x
and (let^) x k = Iter.filter_map k x

module Graph = struct
  include Hashtbl
  let push v = function
    | None     -> Iter.singleton v
    | Some acc -> Iter.cons v acc
  let push g v u = update g v ~f:(push u)
  let connect g v u = push g v u; push g u v
 
  let around g v = find g v |> Option.value ~default:Iter.empty
end
let g = Graph.create ~size:n (module Int)
let () =
  for _ = 1 to m do
    scanf " %d %d" @@ Graph.connect g
  done

let rec binsearch ~ok left right =
  if abs (right - left) <= 1L then right
  else
    let mid = (right + left) / 2L in
    let left, right = if ok mid then left, mid else mid, right in
    binsearch ~ok left right

module SegmentTree = struct
  type m                = int
  let idm : m           = 0
  let mul : m -> m -> m = max

  type t = { tree: m array; size: int }

  let create ~len : t = { tree = Array.create ~len:(2 * len) idm; size = len }

  let product { tree; size } l r =
    let rec product lp rp l r =
      if r <= l
      then mul lp rp
      else
        product
          (if l mod 2 = 0 then lp else mul lp tree.(l))
          (if r mod 2 = 0 then rp else mul tree.(r - 1) rp)
          ((l + 1) / 2) (r / 2)
    in
    product idm idm (l + size) (r + size)

  let update { tree; size } i x =
    tree.(i + size) <- x;
    let left i = 2 * i and right i = 2 * i + 1 in
    let rec propagate i =
      if 0 < i then begin
        tree.(i) <- mul tree.(left i) tree.(right i);
        propagate (i / 2)
      end
    in
    propagate ((i + size) / 2)
end

(* 標準ライブラリ環境 *)
module SI = Set.Make(Int)
let targets : SI.t = (* ... *)
let find x = SI.find_opt x targets |> Option.is_some

(* Core 環境 *)
open Core
let targets : Int.Set.t = (* ... *)
let find x = Int.Set.find targets ~f:((=) x) |> Option.is_some

module Iter = struct
  include Iter
  let zip x y = flat_map (fun x -> map (fun y -> x, y) y) x
  let( * ) = zip
end
 
module Bit_all = struct
  open Iter
  let on x i = x land (1 lsl (i - 1)) <> 0
 
  let bits len = 0 -- (1 lsl len - 1)
  let by_bits x = map (fun bits -> (1 -- x) |> filter (on bits) |> map (fun x -> x - 1) |> to_array)
  let start x = by_bits x (bits x)
end

Iter.(
    Bit_all.start a * Bit_all.start b
  )
|> Iter.filter (fun (i, j) -> ...)
|> Iter.iter (fun (i, j) -> ...)

module PI = struct
  type t = int * int
  let compare = Tuple2.compare ~cmp1:Int.compare ~cmp2:Int.compare
  let sexp_of_t = Tuple2.sexp_of_t sexp_of_int sexp_of_int
  let t_of_sexp = Tuple2.t_of_sexp int_of_sexp int_of_sexp
end
module SP = Set.Make(PI)

module Memo = struct
  include Memo
  let recursive m f =
    let h = Hashtbl.create m in
    let rec g x = Hashtbl.update_and_return h x ~f:(function
      | Some v -> v
      | None   -> f g x
    )
    in g
end

let eratosthenes n =
  let sieve = Array.init n ~f:(const 1) in
  let rec eratosthenes ?(acc=Iter.empty) = function
    | []      -> acc
    | x :: xs ->
      if sieve.(x) = 0 then eratosthenes ~acc xs
      else begin
        List.range ~start:`inclusive ~stop:`inclusive ~stride:x (x*x) 300_004
        |> List.iter ~f:(fun x -> sieve.(x) <- 0);
        eratosthenes ~acc:(Iter.snoc acc @@ Int64.of_int x) xs
      end
  in
  let primes = eratosthenes List.(range 2 n) |> Iter.to_array in
  for i = 1 to Array.length sieve - 1 do
    sieve.(i) <- sieve.(i) + sieve.(i - 1);
  done;
  primes, sieve

let primes, prime_count = eratosthenes 300_005

let (.!()<-) a i v = a.(i) <- max a.(i) v

module Heap = struct
  include Batteries.Heap
  let singleton v = add v empty
  let pop_min heap =
    if size heap = 0 then None
    else
      Some (find_min heap, del_min heap)
end

module Array = struct
  include Array
  let rec reverse a ~start ~stop =
    if start < stop then begin
      Array.swap a start stop;
      reverse a ~start:(start + 1) ~stop:(stop - 1)
    end
end

module Permutation (M: sig type t val compare: t -> t -> int end) = struct
  let next a ~l ~r =
    let downto_loop ~start ~stop ~p ~proc =
      Iter.(start --^ stop) |> Fn.flip Iter.fold_while false
      @@ fun _ i -> if p i then (proc i; true, `Stop) else false, `Continue
    in
    let change_to_next_permutation a ~l ~r =
      downto_loop ~start:(r - 1) ~stop:l
        ~p:(fun i -> M.compare a.(l) a.(i) < 0)
        ~proc:(fun i ->
            Array.swap a l i;
            Array.reverse a ~start:(l + 1) ~stop:(r - 1)
          )
    in
    downto_loop ~start:(r - 2) ~stop:l
      ~p:(fun i -> 
        M.compare a.(i) a.(i + 1) < 0 && 
        change_to_next_permutation a ~l:i ~r
      )
      ~proc:ignore

  let fold arr n ~f ~acc =
    let arr = Array.copy arr in
    Array.sort arr ~compare:M.compare;
    let rec permutations acc =
      let acc = f acc arr in
      let found_next = next arr ~l:0 ~r:n in
      if found_next then permutations acc else acc
    in
    permutations acc
end

module PermutationChar = Permutation (Char)

let a = [| 1; 2; 3; 4; |]

let cumsum a =
  let paired f a b = let r = f a b in r, r in
  Array.folding_map a ~init:0 ~f:(paired Int.bit_xor)

let cumsum = cumsum a

let () =
  Array.iter cumsum ~f:(printf "%d ")

(* output: 1 3 6 10 *) 

module Fenwick = struct
  module M = Int

  type t = { n : int; a : M.t array }

  let create n = { n; a = Array.create ~len:n M.zero }

  let add t i x =
    let rec go i = if i < t.n then (
      t.a.(i) <- M.(t.a.(i) + x);
      go (i lor (i + 1))
    ) in
    go i

  let sum t l r =
    let rec go i acc = 
      if i < 0 then acc
      else 
        go (i land (i + 1) - 1) M.(acc + t.a.(i))
    in
    M.(go Int.(pred r) zero - go Int.(pred l) zero)
end