提出 #32140388

---

ソースコード 拡げる

module SegtreeQueries = struct
  (** val product_rec' :
      ('a1 -> 'a1 -> 'a1) -> (int -> 'a1) -> int -> int -> int -> int
      -> 'a1 -> 'a1 -> 'a1 **)

  let rec product_rec' mul x x0 x1 x2 x3 x4 x5 =
    if ( <= ) x3 x2
    then mul x4 x5
    else product_rec' mul x ((fun n -> n / 2) x0) (( + ) x1 x0)
           ((fun n -> (n + 1) / 2) x2) ((fun n -> n / 2) x3)
           (if (fun n -> 0 < n mod 2) x2
            then mul x4 (x (( + ) x1 x2))
            else x4)
           (if (fun n -> 0 < n mod 2) x3
            then mul (x (( + ) x1 (pred x3))) x5
            else x5)

  (** val product' :
      'a1 -> ('a1 -> 'a1 -> 'a1) -> (int -> 'a1) -> int -> int -> int
      -> 'a1 **)

  let product' idm mul segtree m l r =
    product_rec' mul segtree m 0 l r idm idm

  (** val upper_bound_rec' :
      ('a1 -> 'a1 -> 'a1) -> 'a1 pred -> (int -> 'a1) -> int -> int
      -> int -> int -> int -> 'a1 -> (int -> 'a1 -> 'a2) -> 'a2 **)

  let rec upper_bound_rec' mul p segtree i m n l r p0 cont =
    (fun fO fS n -> if n=0 then fO () else fS (n-1))
      (fun _ -> cont l p0)
      (fun i0 ->
      if ( <= ) r l
      then cont l p0
      else let p' =
             if (fun n -> 0 < n mod 2) l
             then mul p0 (segtree (( + ) n l))
             else p0
           in
           if if (fun n -> 0 < n mod 2) l then not (p p') else false
           then cont l p0
           else upper_bound_rec' mul p segtree i0
                  ((fun n -> n / 2) m) (( + ) n m)
                  ((fun n -> (n + 1) / 2) l) ((fun n -> n / 2) r) p'
                  (fun k p1 ->
                  if ( <= ) r ((fun n -> n + n) k)
                  then cont ((fun n -> n + n) k) p1
                  else let p'0 =
                         mul p1
                           (segtree (( + ) n ((fun n -> n + n) k)))
                       in
                       if p p'0
                       then cont (succ ((fun n -> n + n) k)) p'0
                       else cont ((fun n -> n + n) k) p1))
      i

  (** val upper_bound' :
      'a1 -> ('a1 -> 'a1 -> 'a1) -> 'a1 pred -> (int -> 'a1) -> int
      -> int -> int -> int * 'a1 **)

  let upper_bound' idm mul p segtree m l r =
    upper_bound_rec' mul p segtree m m 0 l r idm (fun x x0 -> (x, x0))

  (** val lower_bound_rec' :
      ('a1 -> 'a1 -> 'a1) -> 'a1 pred -> (int -> 'a1) -> int -> int
      -> int -> int -> int -> 'a1 -> (int -> 'a1 -> 'a2) -> 'a2 **)

  let rec lower_bound_rec' mul p segtree i m n l r p0 cont =
    (fun fO fS n -> if n=0 then fO () else fS (n-1))
      (fun _ -> cont r p0)
      (fun i0 ->
      if ( <= ) r l
      then cont r p0
      else let p' =
             if (fun n -> 0 < n mod 2) r
             then mul (segtree (( + ) n (pred r))) p0
             else p0
           in
           if if (fun n -> 0 < n mod 2) r then not (p p') else false
           then cont r p0
           else lower_bound_rec' mul p segtree i0
                  ((fun n -> n / 2) m) (( + ) n m)
                  ((fun n -> (n + 1) / 2) l) ((fun n -> n / 2) r) p'
                  (fun k p1 ->
                  if ( <= ) ((fun n -> n + n) k) l
                  then cont ((fun n -> n + n) k) p1
                  else let p'0 =
                         mul
                           (segtree
                             (( + ) n (pred ((fun n -> n + n) k)))) p1
                       in
                       if p p'0
                       then cont (pred ((fun n -> n + n) k)) p'0
                       else cont ((fun n -> n + n) k) p1))
      i

  (** val lower_bound' :
      'a1 -> ('a1 -> 'a1 -> 'a1) -> 'a1 pred -> (int -> 'a1) -> int
      -> int -> int -> int * 'a1 **)

  let lower_bound' idm mul p segtree m l r =
    lower_bound_rec' mul p segtree m m 0 l r idm (fun x x0 -> (x, x0))
end

module Segtree = struct
  module type Monoid = sig
    type t

    val e : t

    val op : t -> t -> t
  end

  module Make (M : Monoid) = struct
    type elt = M.t
    type t = elt array

    let make m = Array.make (2 * m) M.e
    let leaves segtree = Array.length segtree / 2

    let rec initialize_ancestors i j n d =
      if 0 < n then begin
        for k = 0 to n - 1 do
          d.(i + k) <- M.op d.(j + 2 * k) d.(j + 2 * k + 1)
        done;
        initialize_ancestors (i + n) i (n / 2) d
      end

    let of_list l =
      let segtree = make (List.length l) in
      List.iteri (Array.set segtree) l;
      initialize_ancestors (leaves segtree) 0 (leaves segtree / 2) segtree;
      segtree

    let init m f =
      let segtree = make m in
      for i = 0 to m - 1 do
        segtree.(i) <- f i
      done;
      initialize_ancestors m 0 (m / 2) segtree;
      segtree

    let product segtree = SegtreeQueries.product' M.e M.op (Array.get segtree) (leaves segtree)
    let upper_bound segtree l r p = SegtreeQueries.upper_bound' M.e M.op p (Array.get segtree) (leaves segtree) l r
    let lower_bound segtree l r p = SegtreeQueries.lower_bound' M.e M.op p (Array.get segtree) (leaves segtree) l r

    let rec update_ancestors i j k n d =
      if k < n then begin
        d.(i + k) <- M.op d.(j + 2 * k) d.(j + 2 * k + 1);
        update_ancestors (i + n) i (k / 2) (n / 2) d
      end
    let update segtree i f =
      segtree.(i) <- f segtree.(i);
      update_ancestors (leaves segtree) 0 (i / 2) (leaves segtree / 2) segtree 
  end
end

module SumSegtree = Segtree.Make (struct
  type t = int
  let e = 0
  let op = ( + )
end)

let () = Scanf.scanf "%d\n" @@ fun q ->
  let segtree = SumSegtree.make 200001 in
  for i = 0 to q - 1 do
    Scanf.scanf "%d %d\n" @@ fun t x ->
      match t with
      | 1 -> SumSegtree.update segtree x succ;
      | 2 ->
          let (n, _) = SumSegtree.upper_bound segtree 0 200001 (fun sum -> sum < x) in
          Printf.printf "%d\n" n;
          SumSegtree.update segtree n pred;
  done

提出情報

コンパイルエラー

File "./Main.ml", lines 168-173, characters 6-43:
168 | ......match t with
169 |       | 1 -> SumSegtree.update segtree x succ;
170 |       | 2 ->
171 |           let (n, _) = SumSegtree.upper_bound segtree 0 200001 (fun sum -> sum < x) in
172 |           Printf.printf "%d\n" n;
173 |           SumSegtree.update segtree n pred;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
0

ジャッジ結果