提出 #32185102

---

ソースコード 拡げる

module SegtreeQueries = struct
  (** val odd : int -> bool **)

  let rec odd = fun n -> n mod 2 = 1

  (** val double : int -> int **)

  let double = fun n -> n * 2

  (** val half : int -> int **)

  let rec half = fun n -> n / 2

  (** val uphalf : int -> int **)

  and uphalf = fun n -> (n + 1) / 2

  (** val lsb : int -> int **)

  let lsb = fun n -> n mod 2

  (** 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 (half x0) (( + ) x1 x0) (uphalf x2)
          (half x3)
          (if odd x2 then mul x4 (x (( + ) x1 x2)) else x4)
          (if odd 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''_aux :
      ('a1 -> 'a1 -> 'a1) -> 'a1 pred -> (int -> 'a1) -> int -> int
      -> int -> int -> 'a1 -> int * 'a1 **)

  let rec upper_bound_rec''_aux mul p x x0 x1 x2 x3 x4 =
    if ( <= ) x2 (succ 0)
    then (x3, x4)
    else if ( <= ) (( + ) (double x0) (lsb x2)) (double x3)
        then upper_bound_rec''_aux mul p x
                (( + ) (double x0) (lsb x2))
                (( - ) x1 (( + ) (double x0) (lsb x2))) (half x2)
                (double x3) x4
        else if p
                  (mul x4
                    (x
                      (( + )
                        (( - ) x1 (( + ) (double x0) (lsb x2)))
                        (double x3))))
              then upper_bound_rec''_aux mul p x
                    (( + ) (double x0) (lsb x2))
                    (( - ) x1 (( + ) (double x0) (lsb x2)))
                    (half x2) (succ (double x3))
                    (mul x4
                      (x
                        (( + )
                          (( - ) x1 (( + ) (double x0) (lsb x2)))
                          (double x3))))
              else upper_bound_rec''_aux mul p x
                    (( + ) (double x0) (lsb x2))
                    (( - ) x1 (( + ) (double x0) (lsb x2)))
                    (half x2) (double x3) x4

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

  let rec upper_bound_rec'' mul p x x0 x1 x2 x3 x4 =
    if ( <= ) x0 x3
    then upper_bound_rec''_aux mul p x x0 x1 x2 x3 x4
    else if odd x3
        then if p (mul x4 (x (( + ) x1 x3)))
              then upper_bound_rec'' mul p x (half x0) (( + ) x1 x0)
                    (( + ) (double x2) (lsb x0)) (succ (half x3))
                    (mul x4 (x (( + ) x1 x3)))
              else upper_bound_rec''_aux mul p x x0 x1 x2 x3 x4
        else upper_bound_rec'' mul p x (half x0) (( + ) x1 x0)
                (( + ) (double x2) (lsb x0)) (half x3) x4

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

  let upper_bound'' idm mul p segtree m l =
    upper_bound_rec'' mul p segtree m 0 (succ 0) l idm

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

  let rec lower_bound_rec''_aux mul p x x0 x1 x2 x3 x4 =
    if ( <= ) x2 (succ 0)
    then (x3, x4)
    else if ( <= ) (double x3) 0
        then lower_bound_rec''_aux mul p x
                (( + ) (double x0) (lsb x2))
                (( - ) x1 (( + ) (double x0) (lsb x2))) (half x2)
                (double x3) x4
        else if p
                  (mul
                    (x
                      (( + )
                        (( - ) x1 (( + ) (double x0) (lsb x2)))
                        (pred (double x3)))) x4)
              then lower_bound_rec''_aux mul p x
                    (( + ) (double x0) (lsb x2))
                    (( - ) x1 (( + ) (double x0) (lsb x2)))
                    (half x2) (pred (double x3))
                    (mul
                      (x
                        (( + )
                          (( - ) x1 (( + ) (double x0) (lsb x2)))
                          (pred (double x3)))) x4)
              else lower_bound_rec''_aux mul p x
                    (( + ) (double x0) (lsb x2))
                    (( - ) x1 (( + ) (double x0) (lsb x2)))
                    (half x2) (double x3) x4

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

  let rec lower_bound_rec'' mul p x x0 x1 x2 x3 x4 =
    if ( <= ) x3 0
    then lower_bound_rec''_aux mul p x x0 x1 x2 x3 x4
    else if odd x3
        then if p (mul (x (( + ) x1 (pred x3))) x4)
              then lower_bound_rec'' mul p x (half x0) (( + ) x1 x0)
                    (( + ) (double x2) (lsb x0)) (half x3)
                    (mul (x (( + ) x1 (pred x3))) x4)
              else lower_bound_rec''_aux mul p x x0 x1 x2 x3 x4
        else lower_bound_rec'' mul p x (half x0) (( + ) x1 x0)
                (( + ) (double x2) (lsb x0)) (half x3) x4

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

  let lower_bound'' idm mul p segtree m r =
    lower_bound_rec'' mul p segtree m 0 (succ 0) r idm
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 p = SegtreeQueries.upper_bound'' M.e M.op p (Array.get segtree) (leaves segtree) l
    let lower_bound segtree r p = SegtreeQueries.lower_bound'' M.e M.op p (Array.get segtree) (leaves segtree) 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 (fun sum -> sum < x) in
          Printf.printf "%d\n" n;
          SumSegtree.update segtree n pred;
  done

提出情報

コンパイルエラー

File "./Main.ml", lines 215-220, characters 6-43:
215 | ......match t with
216 |       | 1 -> SumSegtree.update segtree x succ;
217 |       | 2 ->
218 |           let (n, _) = SumSegtree.upper_bound segtree 0 (fun sum -> sum < x) in
219 |           Printf.printf "%d\n" n;
220 |           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

ジャッジ結果