提出 #3877048

---

ソースコード 拡げる

let rec fix f x = f (fix f) x
module BIT = struct
  let lsb i = i land -i
  let sum i b = (* 0-indexed; Σv[0,i-1] *)
    fix (fun f i s -> if i>0 then f (i - lsb i) (s + b.(i)) else s) i 0
  let sum_closed i = sum (i+1) (* 0-indexed; Σv[0,i] *)
  let sum_interval l r b = (* 0-indexed; Σv[l,r] = Σv[0,r+1-1] - Σv[0,l-1] *)
    if l>r then 0 else sum (r+1) b - sum l b
  let add i x b = (* 0-indexed; v[i]+=x. not b *)
    fix (fun f i -> if i<Array.length b then (
      b.(i) <- b.(i) + x; f (i + lsb i))) (i+1)
  let of_array v = let b = Array.make (Array.length v + 1) 0 in
    Array.iteri (fun i v -> add i v b) v; b
  let make n = Array.make (n+1) 0
  let reconst b = Array.init (Array.length b-1) (
    fun i -> sum_interval i i b)
end
module IMap = Map.Make(struct type t=int let compare=compare end)
let coordinate_compression a =
  let ls = a |> Array.to_list |> List.sort_uniq compare in
  let unzip = Array.make (List.length ls) 0 in
  let zip = fst @@ List.fold_left (fun (m,i) v ->
    unzip.(i) <- v; IMap.add v i m,i+1) (IMap.empty,0) ls
  in zip,unzip
open Scanf
let n = scanf " %d" @@ fun v -> v
let a = Array.init n @@ fun _ -> scanf " %d" @@ fun v -> v
let zip,_ = coordinate_compression a
let b = BIT.make (n+1)
let () = print_int @@
  Array.fold_left (fun sum v ->
    let v = IMap.find v zip in
    BIT.add v 1 b;
    sum + BIT.sum_interval (v+1) n b) 0 a

提出情報

ジャッジ結果