ac-library-hs 1.5.3.1 → 1.5.3.2

raw patch · 3 files changed

+22/−8 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• ac-library-hs.cabal +1/−1
• src/AtCoder/FenwickTree.hs +11/−2
• src/AtCoder/LazySegTree.hs +10/−5

@@ -3,7 +3,7 @@ -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version: 1.5.3.1+version: 1.5.3.2 synopsis: Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive

@@ -31,6 +31,11 @@ -- >>> FT.sum ft 0 3 -- 8 --+-- ==== Known bugs+--+-- Currently, `maxRight` and `maxRightM` are not reliable. If you need it, please use `SegTree`+-- instead.+-- -- @since 1.0.0.0 module AtCoder.FenwickTree   ( -- * Fenwick tree@@ -140,7 +145,9 @@ sumMaybe :: (HasCallStack, PrimMonad m, Num a, VU.Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m (Maybe a) sumMaybe ft l r = stToPrim $ sumMaybeST ft l r --- | (Extra API) Applies a binary search on the Fenwick tree. It returns an index \(r\) that+-- | known bugs: this function is not reliable. if you need t, please use `segtree` instead.+--+-- (Extra API) Applies a binary search on the Fenwick tree. It returns an index \(r\) that -- satisfies both of the following. -- -- - \(r = l\) or \(f(a[l] + a[l + 1] + ... + a[r - 1])\) returns `True`.@@ -171,7 +178,9 @@   m Int maxRight ft l0 f = maxRightM ft l0 (pure . f) --- | (Extra API) Monadic variant of `maxRight`.+-- | known bugs: this function is not reliable. if you need t, please use `segtree` instead.+--+-- (Extra API) Monadic variant of `maxRight`. -- -- ==== Constraints -- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.

@@ -14,10 +14,14 @@ -- - Acting the map \(f\in F\) (cf. \(x = f(x)\)) on all the elements of an interval -- - Calculating the product of the elements of an interval ----- In Haskell types, \(F\) is a `SegAct` (@'segAct' f@) and \(S\) is a `Monoid`. For simplicity, in--- this document, we assume that the relevant methods work in constant time. If these work in--- \(O(T)\) time, each time complexity appear in this document is multiplied by \(O(T)\).+-- In Haskell types, \(F\) is a `SegAct` (@'segAct' f@) and \(S\) is a `Monoid`. You would want to+-- look into @AtCoder.Extra.Monoid@ for builtin monoid action types. For example, there's no+-- implementation of @SegAct (Sum Int) (Sum Int)@, but you have @SegAct (RangeAdd Int) (Sum Int)@. --+-- For simplicity, in this document, we assume that the relevant methods work in constant time. If+-- these work in \(O(T)\) time, each time complexity appear in this document is multiplied by+-- \(O(T)\).+-- -- ==== __Example__ -- Here we'll use `AtCoder.Extra.Monoid.Affine1` as a monoid action \(F\) and `Data.Semigroup.Sum` -- as the acted monoid \(S\):@@ -66,6 +70,7 @@ -- -- ==== Tips --+-- - See @AtCoder.Extra.Monoid@ for builtin monoid action types. -- - `prod` returns \(a_l \cdot a_{l + 1} \cdot .. \cdot a_{r - 1}\). If you need \(a_{r - 1} \cdot a_{r - 2} \cdot .. \cdot a_{l}\), -- wrap your monoid in `Data.Monoid.Dual`. -- - If you ever need to store boxed types to `LazySegTree`, wrap it in @Data.Vector.Unboxed.DoNotUnboxStrict@@@ -133,7 +138,7 @@ import Prelude hiding (read)  -- | Typeclass reprentation of the `LazySegTree` properties. User can implement either `segAct` or--- `segActWithLength`.+-- `segActWithLength`. See @AtCoder.Extra.Monoid@ for builtin monoid action types. -- -- Instances should satisfy the follwing properties: --@@ -150,7 +155,7 @@ -- order is important for non-commutative monoid implementations. -- -- ==== __Example instance__--- Take `AtCoder.Extra.Monoid.Affine1` as an example of type \(F\).+-- Take `AtCoder.Extra.Monoid.Affine1` as an example of type \(F\) instance. -- -- @ -- {-# LANGUAGE TypeFamilies #-}