packages feed

ac-library-hs 1.0.0.0 → 1.0.0.1

raw patch · 33 files changed

+489/−491 lines, 33 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

- AtCoder.Internal.Scc: addEdge :: PrimMonad m => SccGraph (PrimState m) -> Int -> Int -> m ()
- AtCoder.Internal.Scc: data SccGraph s
- AtCoder.Internal.Scc: new :: PrimMonad m => Int -> m (SccGraph (PrimState m))
- AtCoder.Internal.Scc: scc :: PrimMonad m => SccGraph (PrimState m) -> m (Vector (Vector Int))
- AtCoder.Internal.Scc: sccIds :: PrimMonad m => SccGraph (PrimState m) -> m (Int, Vector Int)

Files

ac-library-hs.cabal view
@@ -4,7 +4,7 @@ -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version:         1.0.0.0+version:         1.0.0.1 synopsis:        Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive
src/AtCoder/Convolution.hs view
@@ -35,7 +35,7 @@ -- -- If you want to calculate large values without taking mod, use `convolution64`. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Convolution   ( -- * Convolution in mod m     convolution,@@ -75,8 +75,7 @@ -- ==== Complexity -- - \(O(n\log{n} + \log{\mathrm{mod}})\), where \(n = |a| + |b|\). ----- @since 1.0.0--- {-# INLINE convolution #-}+-- @since 1.0.0.0 convolution ::   forall p.   (HasCallStack, AM.Modulus p) =>@@ -106,8 +105,7 @@ -- ==== Complexity -- - \(O(n\log{n} + \log{\mathrm{mod}})\), where \(n = |a| + |b|\). ----- @since 1.0.0--- {-# INLINE convolutionRaw #-}+-- @since 1.0.0.0 convolutionRaw ::   forall p a.   (HasCallStack, AM.Modulus p, Integral a, VU.Unbox a) =>@@ -136,8 +134,7 @@ -- ==== Complexity -- - \(O(n\log{n})\), where \(n = |a| + |b|\). ----- @since 1.0.0---- {-# INLINE convolution64 #-}+-- @since 1.0.0.0 convolution64 ::   (HasCallStack) =>   VU.Vector Int ->
src/AtCoder/Dsu.hs view
@@ -18,7 +18,7 @@ -- >>> Dsu.nDsu dsu -- 4 ----- Merge some vertices into the same group: b:+-- Merge some vertices into the same group: -- -- >>> Dsu.merge dsu 0 1  -- 0=1 2 3 -- 0@@ -41,7 +41,7 @@ -- >>> Dsu.groups dsu -- [[2,1,0],[3]] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Dsu   ( -- * Disjoint set union     Dsu (nDsu),@@ -75,7 +75,7 @@  -- | Disjoint set union. Akso known as Union-Find tree. ----- @since 1.0.0+-- @since 1.0.0.0 data Dsu s = Dsu   { -- | 1.0.0 The number of nodes.     --@@ -94,7 +94,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m) => Int -> m (Dsu (PrimState m)) new nDsu@@ -114,7 +114,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE merge #-} merge :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Int merge dsu@Dsu {..} a b = do@@ -143,7 +143,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE merge_ #-} merge_ :: (PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m () merge_ dsu a b = do@@ -159,7 +159,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE same #-} same :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> Int -> m Bool same dsu@Dsu {..} a b = do@@ -177,7 +177,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE leader #-} leader :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int leader dsu@Dsu {..} a = do@@ -198,7 +198,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE size #-} size :: (HasCallStack, PrimMonad m) => Dsu (PrimState m) -> Int -> m Int size dsu@Dsu {..} a = do@@ -215,7 +215,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE groups #-} groups :: (PrimMonad m) => Dsu (PrimState m) -> m (V.Vector (VU.Vector Int)) groups dsu@Dsu {..} = do
src/AtCoder/Extra/Math.hs view
@@ -12,7 +12,7 @@ -- >>> getProduct $ M.mtimes' 32 (Product 2) -- 4294967296 ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Math   ( -- * Binary exponential     power,@@ -37,7 +37,7 @@ -- ==== Constraints -- - \(n \gt 0\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE power #-} power :: (a -> a -> a) -> Int -> a -> a power op n0 x1@@ -61,7 +61,7 @@ -- ==== Constraints -- - \(n \gt 0\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE stimes' #-} stimes' :: (Semigroup a) => Int -> a -> a stimes' = power (<>)@@ -74,7 +74,7 @@ -- ==== Constraints -- - \(n \ge 0\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE mtimes' #-} mtimes' :: (Monoid a) => Int -> a -> a mtimes' n x = case compare n 0 of
src/AtCoder/Extra/Monoid.hs view
@@ -4,7 +4,7 @@ -- -- Be warned that they're not 100% guaranteed to be correct. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Monoid   ( -- * SegAct (re-export)     SegAct (..),
src/AtCoder/Extra/Monoid/Affine1.hs view
@@ -1,9 +1,8 @@ {-# LANGUAGE TypeFamilies #-} --- | `AtCoder.LazySegTree.SegAct` instance of one-dimensional affine transformation--- \(f: x \rightarrow a \times x + b\).+-- | Range add monoid action for \([l, r)\) intervals: \(f: x \rightarrow ax + b\). ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Monoid.Affine1   ( -- * Affine1     Affine1 (..),@@ -30,8 +29,7 @@  -- Tuple is not the fastest representation, but it's easier to implement `Unbox`. --- | `AtCoder.LazySegTree.SegAct` instance of one-dimensional affine transformation--- \(f: x \rightarrow a \times x + b\).+-- | Range add monoid action for \([l, r)\) intervals: \(f: x \rightarrow ax + b\). -- -- ==== Composition and dual -- `Semigroup` for `Affine1` is implemented like function composition, and rightmost affine@@ -47,45 +45,45 @@ -- >>> getSum <$> LST.allProd seg -- 9 ----- @since 1.0.0+-- @since 1.0.0.0 newtype Affine1 a = Affine1 (Affine1Repr a)   deriving newtype-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Ord,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | `Affine1` internal representation. Tuples are not the fastest representation, but it's easier -- to implement `Data.Vector.Unboxed.Unbox`. ----- @since 1.0.0+-- @since 1.0.0.0 type Affine1Repr a = (a, a)  -- | Creates `Affine1`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: a -> a -> Affine1 a new !a !b = Affine1 (a, b)  -- | Applies \(f: x \rightarrow a \times x + b\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE act #-} act :: (Num a) => Affine1 a -> a -> a act (Affine1 (!a, !b)) x = a * x + b  -- | Acts on @a@ with length in terms of `SegAct`. Works for `Sum a` only. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE actWithLength #-} actWithLength :: (Num a) => Int -> Affine1 a -> a -> a actWithLength len (Affine1 (!a, !b)) !x = a * x + b * fromIntegral len --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Semigroup (Affine1 a) where   {-# INLINE (<>) #-}   (Affine1 (!a1, !b1)) <> (Affine1 (!a2, !b2)) = Affine1 (a', b')@@ -97,7 +95,7 @@   {-# INLINE stimes #-}   stimes b = ACEM.power (<>) (fromIntegral b) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Monoid (Affine1 a) where   {-# INLINE mempty #-}   mempty = Affine1 (1, 0)@@ -105,39 +103,39 @@   mconcat [] = mempty   mconcat (x : xs) = foldl' (<>) x xs --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (Affine1 a) (Sum a) where   {-# INLINE segActWithLength #-}   segActWithLength !len f (Sum !x) = Sum $! actWithLength len f x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (Affine1 (Sum a)) (Sum a) where   {-# INLINE segActWithLength #-}   segActWithLength = actWithLength --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (Dual (Affine1 a)) (Sum a) where   {-# INLINE segActWithLength #-}   segActWithLength !len (Dual f) (Sum !x) = Sum $! actWithLength len f x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (Dual (Affine1 (Sum a))) (Sum a) where   {-# INLINE segActWithLength #-}   segActWithLength !len (Dual f) (Sum !x) = Sum $! actWithLength len (coerce f) x  -- not works as SegAct for Product, Min, and Max. --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.MVector s (Affine1 a) = MV_Affine1 (VU.MVector s (Affine1Repr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.Vector (Affine1 a) = V_Affine1 (VU.Vector (Affine1Repr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1 a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1 a) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (VU.Unbox a) => VU.Unbox (Affine1 a)
src/AtCoder/Extra/Monoid/RangeAdd.hs view
@@ -1,8 +1,8 @@ {-# LANGUAGE TypeFamilies #-} --- | Monoid action for setting interval \([l, r)\).+-- | Range add monoid action for \([l, r)\) intervals. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Monoid.RangeAdd   ( -- * RangeAdd     RangeAdd (..),@@ -22,7 +22,7 @@ import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM --- | Range set monoid action.+-- | Range add monoid action. -- -- ==== Example -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))@@ -33,66 +33,66 @@ -- >>> getSum <$> LST.prod seg 0 3 -- 18 ----- @since 1.0.0+-- @since 1.0.0.0 newtype RangeAdd a = RangeAdd a   deriving newtype-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Ord,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | Creates `RangeAdd`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: a -> RangeAdd a new = RangeAdd  -- | Applies one-length range add: \(f: x \rightarrow d + x\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE act #-} act :: (Num a) => RangeAdd a -> a -> a act (RangeAdd dx) x = dx + x  -- | Acts on @a@ with length in terms of `SegAct`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE actWithLength #-} actWithLength :: (Num a) => Int -> RangeAdd a -> a -> a actWithLength len (RangeAdd f) x = fromIntegral len * f + x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Semigroup (RangeAdd a) where   {-# INLINE (<>) #-}   (RangeAdd a) <> (RangeAdd b) = RangeAdd $! a + b --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Monoid (RangeAdd a) where   {-# INLINE mempty #-}   mempty = RangeAdd 0 --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (RangeAdd a) (Sum a) where   {-# INLINE segActWithLength #-}   segActWithLength len a (Sum x) = Sum $! actWithLength len a x  -- not works as SegAct for Product, Min, and Max. --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.MVector s (RangeAdd a) = MV_RangeAdd (VU.MVector s a) --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.Vector (RangeAdd a) = V_RangeAdd (VU.Vector a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeAdd a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeAdd a) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (VU.Unbox a) => VU.Unbox (RangeAdd a)
src/AtCoder/Extra/Monoid/RangeAddId.hs view
@@ -1,8 +1,9 @@ {-# LANGUAGE TypeFamilies #-} --- | Monoid action for setting interval \([l, r)\) over ideomponent monoids.+-- | Range add monoid action for \([l, r)\) intervals. Works on ideomponent monoids such as `Max`+-- or `Min` only. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Monoid.RangeAddId   ( -- * RangeAddId     RangeAddId (..),@@ -20,7 +21,7 @@ import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM --- | Range set monoid action.+-- | Range add monoid action. -- -- ==== Example -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAddId(..))@@ -31,64 +32,64 @@ -- >>> getMax <$> LST.prod seg 0 3 -- 7 ----- @since 1.0.0+-- @since 1.0.0.0 newtype RangeAddId a = RangeAddId a   deriving newtype-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Ord,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | Creates `RangeAddId`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: a -> RangeAddId a new = RangeAddId  -- | Applies one-length range add: \(f: x \rightarrow d + x\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE act #-} act :: (Num a) => RangeAddId a -> a -> a act (RangeAddId f) x = f + x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Semigroup (RangeAddId a) where   {-# INLINE (<>) #-}   (RangeAddId a) <> (RangeAddId b) = RangeAddId $! a + b --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => Monoid (RangeAddId a) where   {-# INLINE mempty #-}   mempty = RangeAddId 0 --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (RangeAddId a) (Max a) where   {-# INLINE segAct #-}   segAct f (Max x) = Max $! act f x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Num a) => SegAct (RangeAddId a) (Min a) where   {-# INLINE segAct #-}   segAct f (Min x) = Min $! act f x  -- not works as SegAct for Sum and Product. --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.MVector s (RangeAddId a) = MV_RangeAddId (VU.MVector s a) --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.Vector (RangeAddId a) = V_RangeAddId (VU.Vector a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeAddId a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeAddId a) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (VU.Unbox a) => VU.Unbox (RangeAddId a)
src/AtCoder/Extra/Monoid/RangeSet.hs view
@@ -1,9 +1,8 @@ {-# LANGUAGE TypeFamilies #-} --- | `AtCoder.LazySegTree.SegAct` instance of range set action. It can set an interval \([l, r)\) to--- the same monoid \(x\) such as @Sum Int@.+-- | Range set monoid action for \([l, r)\) intervals. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Extra.Monoid.RangeSet   ( -- * RangeSet     RangeSet (..),@@ -25,7 +24,7 @@ import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM --- | `AtCoder.LazySegTree.SegAct` instance of range set action.+-- | Range set monoid action. -- -- ==== Example -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeSet(..))@@ -37,14 +36,14 @@ -- >>> getProduct <$> LST.prod seg 0 4 -- 375 ----- @since 1.0.0+-- @since 1.0.0.0 newtype RangeSet a = RangeSet (RangeSetRepr a)   deriving newtype-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Ord,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     ) @@ -52,19 +51,19 @@ -- Tuples are not the fastest representation, but it's easier to implement -- `Data.Vector.Unboxed.Unbox`. ----- @since 1.0.0+-- @since 1.0.0.0 type RangeSetRepr a = (Bit, a)  -- | Creates a new `RangeSet` action. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: a -> RangeSet a new = RangeSet . (Bit True,)  -- | Applies one-length range set: \(f: x \rightarrow y\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE act #-} act :: RangeSet a -> a -> a act (RangeSet (Bit True, !f)) _ = f@@ -72,13 +71,13 @@  -- | Acts on @a@ with length in terms of `SegAct`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE actWithLength #-} actWithLength :: (Semigroup a) => Int -> RangeSet a -> a -> a actWithLength len (RangeSet (Bit True, !f)) _ = ACEM.power (<>) len f actWithLength _ (RangeSet (Bit False, !_)) x = x --- | @since 1.0.0+-- | @since 1.0.0.0 instance Semigroup (RangeSet a) where   {-# INLINE (<>) #-}   RangeSet (Bit False, !_) <> old = old@@ -86,7 +85,7 @@   {-# INLINE stimes #-}   stimes _ x = x --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Monoid a) => Monoid (RangeSet a) where   {-# INLINE mempty #-}   mempty = RangeSet (Bit False, mempty)@@ -96,22 +95,22 @@   mconcat (RangeSet (Bit False, !_) : as) = mconcat as   mconcat (a : _) = a --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Monoid a) => SegAct (RangeSet a) a where   {-# INLINE segActWithLength #-}   segActWithLength = actWithLength --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.MVector s (RangeSet a) = MV_RangeSet (VU.MVector s (RangeSetRepr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.Vector (RangeSet a) = V_RangeSet (VU.Vector (RangeSetRepr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeSet a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeSet a) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (VU.Unbox a) => VU.Unbox (RangeSet a)
src/AtCoder/Extra/Monoid/RangeSetId.hs view
@@ -1,9 +1,10 @@ {-# LANGUAGE TypeFamilies #-} --- | `AtCoder.LazySegTree.SegAct` instance of range set action over ideomponent monoids. It can set--- an interval \([l, r)\) to an idempotent monoid \(x\) such as @Max Int@.+-- | Range set monoid action for \([l, r)\) intervals. Works on ideomponent monoids such as `Max`+-- or `Min` only. ----- @since 1.0.0+--+-- @since 1.0.0.0 module AtCoder.Extra.Monoid.RangeSetId   ( -- * RangeSetId     RangeSetId (..),@@ -24,7 +25,7 @@ import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM --- | `AtCoder.LazySegTree.SegAct` instance of range set action over ideomponent monoids.+-- | Range set monoid action. -- -- ==== Example -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeSetId(..))@@ -36,14 +37,14 @@ -- >>> getMax <$> LST.prod seg 0 3 -- 12 ----- @since 1.0.0+-- @since 1.0.0.0 newtype RangeSetId a = RangeSetId (RangeSetIdRepr a)   deriving newtype-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Ord,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     ) @@ -51,19 +52,19 @@ -- Tuples are not the fastest representation, but it's easier to implement -- `Data.Vector.Unboxed.Unbox`. ----- @since 1.0.0+-- @since 1.0.0.0 type RangeSetIdRepr a = (Bit, a)  -- | Creates a new `RangeSet` action. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: a -> RangeSetId a new = RangeSetId . (Bit True,)  -- | Applies one-length range set: \(f: x \rightarrow y\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE act #-} act :: RangeSetId a -> a -> a act (RangeSetId (Bit True, !f)) _ = f@@ -71,7 +72,7 @@  -- segActWithLength works for ideomponent monoids only. --- | @since 1.0.0+-- | @since 1.0.0.0 instance Semigroup (RangeSetId a) where   {-# INLINE (<>) #-}   RangeSetId (Bit False, !_) <> old = old@@ -81,7 +82,7 @@  -- The `Monoid` constraint is just for their default value. --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Monoid a) => Monoid (RangeSetId a) where   {-# INLINE mempty #-}   mempty = RangeSetId (Bit False, mempty)@@ -94,7 +95,7 @@ -- The target is limited to ideomponent monoids. The `Monoid` constraint is just for their default -- value. --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Ord a, Bounded a) => SegAct (RangeSetId (Max a)) (Max a) where   {-# INLINE segAct #-}   segAct = act@@ -102,22 +103,22 @@ -- The target is limited to ideomponent monoids. The `Monoid` constraint is just for their default -- value. --- | @since 1.0.0+-- | @since 1.0.0.0 instance (Ord a, Bounded a) => SegAct (RangeSetId (Min a)) (Min a) where   {-# INLINE segAct #-}   segAct = act --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.MVector s (RangeSetId a) = MV_RangeSetId (VU.MVector s (RangeSetIdRepr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 newtype instance VU.Vector (RangeSetId a) = V_RangeSetId (VU.Vector (RangeSetIdRepr a)) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeSetId a) --- | @since 1.0.0+-- | @since 1.0.0.0 deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeSetId a) --- | @since 1.0.0+-- | @since 1.0.0.0 instance (VU.Unbox a) => VU.Unbox (RangeSetId a)
src/AtCoder/FenwickTree.hs view
@@ -31,7 +31,7 @@ -- >>> FT.sum ft 0 3 -- 8 ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.FenwickTree   ( -- * Fenwick tree     FenwickTree (nFt),@@ -62,11 +62,11 @@  -- | Fenwick tree. ----- @since 1.0.0+-- @since 1.0.0.0 data FenwickTree s a = FenwickTree   { -- | 1.0.0 The number of vertices.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nFt :: {-# UNPACK #-} !Int,     -- | The data storage.     dataFt :: !(VUM.MVector s a)@@ -81,7 +81,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (HasCallStack, PrimMonad m, Num a, VU.Unbox a) => Int -> m (FenwickTree (PrimState m) a) new nFt@@ -95,7 +95,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 build :: (PrimMonad m, Num a, VU.Unbox a) => VU.Vector a -> m (FenwickTree (PrimState m) a) {-# INLINE build #-} build xs = do@@ -111,7 +111,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE add #-} add :: (HasCallStack, PrimMonad m, Num a, VU.Unbox a) => FenwickTree (PrimState m) a -> Int -> a -> m () add FenwickTree {..} p0 x = do@@ -124,7 +124,7 @@  -- | \(O(\log n)\) Calculates the sum in half-open range @[0, r)@. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE prefixSum #-} prefixSum :: (PrimMonad m, Num a, VU.Unbox a) => FenwickTree (PrimState m) a -> Int -> m a prefixSum FenwickTree {..} = inner 0@@ -143,7 +143,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE sum #-} sum :: (HasCallStack, PrimMonad m, Num a, VU.Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m a sum ft@FenwickTree {nFt} l r@@ -151,12 +151,12 @@   | otherwise = unsafeSum ft l r  -- | Total version of `sum`. Calculates the sum in half-open range \([l, r)\). It returns `Nothing`--- for invalid intervals.+-- if the interval is invalid. -- -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE sumMaybe #-} sumMaybe :: (HasCallStack, PrimMonad m, Num a, VU.Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m (Maybe a) sumMaybe ft@FenwickTree {nFt} l r
src/AtCoder/Internal/Assert.hs view
@@ -1,6 +1,6 @@ -- | Runtime assertion utility. ----- ==== Example+-- ==== __Example__ -- >>> let !_ = runtimeAssert False "errorMessage" -- *** Exception: errorMessage -- ...@@ -30,7 +30,7 @@ -- *** Exception: AtCoder.Internal.Assert.doctest: given invalid interval `[0, 4)` over length `3` -- ... ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Assert   ( -- * Runtime assertion     runtimeAssert,@@ -59,7 +59,7 @@  -- | \(O(1)\) Assertion that is never erased at compile time. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE runtimeAssert #-} runtimeAssert :: (HasCallStack) => Bool -> String -> () runtimeAssert p s@@ -68,21 +68,21 @@  -- | \(O(1)\) Tests \(i \in [0, n)\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE testIndex #-} testIndex :: (HasCallStack) => Int -> Int -> Bool testIndex i n = 0 <= i && i < n  -- | \(O(1)\) Tests weather \([l, r)\) is a valid interval in \([0, n)\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE testInterval #-} testInterval :: Int -> Int -> Int -> Bool testInterval l r n = 0 <= l && l <= r && r <= n  -- | \(O(1)\) Asserts \(0 \leq i \lt n\) for an array index \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE checkIndex #-} checkIndex :: (HasCallStack) => String -> Int -> Int -> () checkIndex funcName i n@@ -91,7 +91,7 @@  -- | \(O(1)\) Emits index boundary error. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE errorIndex #-} errorIndex :: (HasCallStack) => String -> Int -> Int -> a errorIndex funcName i n =@@ -99,7 +99,7 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt n\) for a graph vertex \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE checkVertex #-} checkVertex :: (HasCallStack) => String -> Int -> Int -> () checkVertex funcName i n@@ -108,7 +108,7 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt n\) for a graph vertex \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE errorVertex #-} errorVertex :: (HasCallStack) => String -> Int -> Int -> a errorVertex funcName i n =@@ -116,7 +116,7 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt m\) for an edge index \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE checkEdge #-} checkEdge :: (HasCallStack) => String -> Int -> Int -> () checkEdge funcName i n@@ -125,7 +125,7 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt m\) for an edge index \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE errorEdge #-} errorEdge :: (HasCallStack) => String -> Int -> Int -> a errorEdge funcName i n =@@ -133,7 +133,7 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt m\) for an edge index \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE checkCustom #-} checkCustom :: (HasCallStack) => String -> String -> Int -> String -> Int -> () checkCustom funcName indexName i setName n@@ -142,14 +142,14 @@  -- | \(O(1)\) Asserts \(0 \leq i \lt m\) for an edge index \(i\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE errorCustom #-} errorCustom :: (HasCallStack) => String -> String -> Int -> String -> Int -> a errorCustom funcName indexName i setName n = error $ funcName ++ ": given invalid " ++ indexName ++ " `" ++ show i ++ "` over " ++ setName ++ " `" ++ show n ++ "`"  -- | \(O(1)\) Asserts \(0 \leq l \leq r \leq n\) for a half-open interval \([l, r)\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE checkInterval #-} checkInterval :: (HasCallStack) => String -> Int -> Int -> Int -> () checkInterval funcName l r n@@ -158,7 +158,7 @@  -- | \(O(1)\) Asserts \(0 \leq l \leq r \leq n\) for a half-open interval \([l, r)\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE errorInterval #-} errorInterval :: (HasCallStack) => String -> Int -> Int -> Int -> a errorInterval funcName l r n = error $ funcName ++ ": given invalid interval `[" ++ show l ++ ", " ++ show r ++ ")` over length `" ++ show n ++ "`"
src/AtCoder/Internal/Barrett.hs view
@@ -4,7 +4,7 @@ -- | Fast modular multiplication for `Word32` by barrett reduction. -- Reference: https://en.wikipedia.org/wiki/Barrett_reduction ----- ==== Example+-- ==== __Example__ -- >>> let bt = new32 10 -- mod 10 -- >>> umod bt -- 10@@ -12,7 +12,7 @@ -- >>> mulMod bt 7 7 -- 9 ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Barrett   ( -- * Barrett     Barrett,@@ -32,42 +32,42 @@ -- | Fast modular multiplication by barrett reduction. -- Reference: https://en.wikipedia.org/wiki/Barrett_reduction ----- @since 1.0.0+-- @since 1.0.0.0 data Barrett = Barrett   { mBarrett :: {-# UNPACK #-} !Word32,     imBarrett :: {-# UNPACK #-} !Word64   }   deriving-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | Creates barret reduction for modulus \(m\) from a `Word32` value. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new32 #-} new32 :: Word32 -> Barrett new32 m = Barrett m $ maxBound @Word64 `div` (fromIntegral m :: Word64) + 1  -- | Creates barret reduction for modulus \(m\) from a `Word64` value. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new64 #-} new64 :: Word64 -> Barrett new64 m = Barrett (fromIntegral m) $ maxBound @Word64 `div` m + 1  -- | Retrieves the modulus \(m\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE umod #-} umod :: Barrett -> Word32 umod Barrett {mBarrett} = mBarrett  -- | Calculates \(a b \bmod m\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE mulMod #-} mulMod :: Barrett -> Word64 -> Word64 -> Word64 mulMod Barrett {..} a b =
src/AtCoder/Internal/Bit.hs view
@@ -2,7 +2,7 @@  -- | Bit operations not in the `Data.Bits` module. ----- ==== Example+-- ==== __Example__ -- >>> bitCeil 0 -- 1 --@@ -18,7 +18,7 @@ -- >>> bitCeil 4 -- 4 ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Bit   ( -- * Utilities     bitCeil,@@ -29,7 +29,7 @@  -- | \(O(w)\) Returns minimum \(2^i s.t. 2^i \geq n\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE bitCeil #-} bitCeil :: Int -> Int bitCeil n = inner 1
src/AtCoder/Internal/Buffer.hs view
@@ -45,7 +45,7 @@ -- >>> B.unsafeFreeze buf -- [] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Buffer   ( -- * Buffer     Buffer,@@ -91,7 +91,7 @@  -- | Pushable vector with fixed size capacity. Stack. ----- @since 1.0.0+-- @since 1.0.0.0 data Buffer s a = Buffer   { lenB :: !(VUM.MVector s Int),     vecB :: !(VUM.MVector s a)@@ -99,7 +99,7 @@  -- | \(O(n)\) Creates a buffer with capacity \(n\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m, VU.Unbox a) => Int -> m (Buffer (PrimState m) a) new n = do@@ -109,7 +109,7 @@  -- | \(O(n)\) Creates a buffer with capacity \(n\) with initial values. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (PrimMonad m, VU.Unbox a) => VU.Vector a -> m (Buffer (PrimState m) a) build xs = do@@ -119,7 +119,7 @@  -- | \(O(1)\) Appends an element to the back. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pushBack #-} pushBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> a -> m () pushBack Buffer {..} e = do@@ -129,7 +129,7 @@  -- | \(O(1)\) Removes the last element from the buffer and returns it, or `Nothing` if it is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE popBack #-} popBack :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (Maybe a) popBack Buffer {..} = do@@ -143,7 +143,7 @@  -- | \(O(1)\) Returns the last value in the buffer, or `Nothing` if it is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE back #-} back :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (Maybe a) back Buffer {..} = do@@ -157,7 +157,7 @@ -- | \(O(1)\) Yields the element at the given position. Will throw an exception if the index is out -- of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE read #-} read :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> Int -> m a read Buffer {..} i = do@@ -168,7 +168,7 @@ -- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is -- out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE write #-} write :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> Int -> a -> m () write Buffer {..} i e = do@@ -179,7 +179,7 @@ -- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is -- out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modify #-} modify :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> (a -> a) -> Int -> m () modify Buffer {..} f i = do@@ -190,7 +190,7 @@ -- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is -- out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modifyM #-} modifyM :: (HasCallStack, PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> (a -> m a) -> Int -> m () modifyM Buffer {..} f i = do@@ -200,14 +200,14 @@  -- | \(O(1)\) Returns the array size. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE capacity #-} capacity :: (VU.Unbox a) => Buffer s a -> Int capacity = VUM.length . vecB  -- | \(O(1)\) Returns the number of elements in the buffer. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE length #-} length :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m Int length Buffer {..} = do@@ -215,14 +215,14 @@  -- | \(O(1)\) Returns `True` if the buffer is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE null #-} null :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m Bool null = (<$>) (== 0) . length  -- | \(O(1)\) Sets the `length` to zero. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE clear #-} clear :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m () clear Buffer {..} = do@@ -230,7 +230,7 @@  -- | \(O(n)\) Yields an immutable copy of the mutable vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE freeze #-} freeze :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (VU.Vector a) freeze Buffer {..} = do@@ -240,7 +240,7 @@ -- | \(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable -- vector may not be used after this operation. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeFreeze #-} unsafeFreeze :: (PrimMonad m, VU.Unbox a) => Buffer (PrimState m) a -> m (VU.Vector a) unsafeFreeze Buffer {..} = do
src/AtCoder/Internal/Convolution.hs view
@@ -4,7 +4,7 @@  -- | Internal implementation of `AtCoder.Convolution` module. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Convolution   ( -- * FFT information     FftInfo,@@ -39,7 +39,7 @@  -- | Data for FFT calculation. ----- @since 1.0.0+-- @since 1.0.0.0 data FftInfo p = FftInfo   { rootFft :: !(VU.Vector (AM.ModInt p)),     iRootFft :: !(VU.Vector (AM.ModInt p)),@@ -49,15 +49,15 @@     iRate3Fft :: !(VU.Vector (AM.ModInt p))   }   deriving-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | \(O(\log m)\) Creates `FftInfo`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE newInfo #-} newInfo :: forall m p. (PrimMonad m, AM.Modulus p) => m (FftInfo p) newInfo = do@@ -110,7 +110,7 @@   iRate3Fft <- VU.unsafeFreeze iRate3   pure FftInfo {..} --- | @since 1.0.0+-- | @since 1.0.0.0 {-# INLINE butterfly #-} butterfly ::   forall m p.@@ -174,7 +174,7 @@             (VU.generate (bit len) id)           loop $ len + 2 --- | @since 1.0.0+-- | @since 1.0.0.0 {-# INLINE butterflyInv #-} butterflyInv ::   forall m p.@@ -239,7 +239,7 @@             (VU.generate (bit (len - 2)) id)           loop $ len - 2 --- | @since 1.0.0+-- | @since 1.0.0.0 {-# INLINE convolutionNaive #-} convolutionNaive ::   forall p.@@ -262,7 +262,7 @@           VGM.modify ans (+ a VG.! i * b VG.! j) (i + j)   pure ans --- | @since 1.0.0+-- | @since 1.0.0.0 {-# INLINE convolutionFft #-} convolutionFft ::   forall p.
src/AtCoder/Internal/Csr.hs view
@@ -29,7 +29,7 @@ -- >>> csr `C.adjW` 2 -- [(3,123)] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Csr   ( -- * Compressed sparse row     Csr,@@ -53,22 +53,22 @@  -- | Comperssed Sparse Row representation of a graph. ----- @since 1.0.0+-- @since 1.0.0.0 data Csr w = Csr   { startCsr :: !(VU.Vector Int),     adjCsr :: !(VU.Vector Int),     wCsr :: !(VU.Vector w)   }   deriving-    ( -- | @since 1.0.0+    ( -- | @since 1.0.0.0       Eq,-      -- | @since 1.0.0+      -- | @since 1.0.0.0       Show     )  -- | \(O(n + m)\) Creates `Csr`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (HasCallStack, VU.Unbox w) => Int -> VU.Vector (Int, Int, w) -> Csr w build n edges = runST $ do@@ -99,7 +99,7 @@  -- | \(O(n + m)\) Creates `Csr` with no weight. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build' #-} build' :: (HasCallStack) => Int -> VU.Vector (Int, Int) -> Csr () build' n edges = build n $ VU.zip3 us vs (VU.replicate (VU.length us) ())@@ -108,7 +108,7 @@  -- | \(O(1)\) Returns adjacent vertices. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE adj #-} adj :: (HasCallStack, VU.Unbox w) => Csr w -> Int -> VU.Vector Int adj Csr {..} i =@@ -118,7 +118,7 @@  -- | \(O(1)\) Returns adjacent vertices with weights. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE adjW #-} adjW :: (HasCallStack, VU.Unbox w) => Csr w -> Int -> VU.Vector (Int, w) adjW Csr {..} i =@@ -128,7 +128,7 @@  -- | \(O(1)\) Returns a vector of @(edgeId, adjacentVertex)@. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE eAdj #-} eAdj :: (HasCallStack, VU.Unbox w) => Csr w -> Int -> VU.Vector (Int, Int) eAdj Csr {..} i =
src/AtCoder/Internal/GrowVec.hs view
@@ -2,7 +2,7 @@  -- | Growable vector with some runtime overhead (by `MutVar`). ----- ==== Example+-- ==== __Example__ -- >>> import AtCoder.Internal.GrowVec qualified as GV -- >>> growVec <- GV.new @_ @Int 0 -- >>> GV.null growVec@@ -37,7 +37,7 @@ -- >>> GV.unsafeFreeze growVec -- [10] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.GrowVec   ( -- * Growable vector     GrowVec (vecGV),@@ -83,17 +83,17 @@  -- | Growable vector with some runtime overhead. ----- @since 1.0.0+-- @since 1.0.0.0 data GrowVec s a = GrowVec   { -- | Stores [l, r) range in the `vecGV`.     posGV :: !(VUM.MVector s Int),-    -- | @since 1.0.0+    -- | @since 1.0.0.0     vecGV :: !(MutVar s (VUM.MVector s a))   }  -- | \(O(n)\) Creates `GrowVec` with initial capacity \(n\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m, VU.Unbox a) => Int -> m (GrowVec (PrimState m) a) new n = do@@ -103,7 +103,7 @@  -- | \(O(n)\) Creates `GrowVec` with initial values. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (PrimMonad m, VU.Unbox a) => VU.Vector a -> m (GrowVec (PrimState m) a) build xs = do@@ -113,7 +113,7 @@  -- | \(O(n)\) Reserves the internal storage capacity. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE reserve #-} reserve :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m () reserve GrowVec {..} len = do@@ -125,7 +125,7 @@ -- | \(O(1)\) Yields the element at the given position. Will throw an exception if the index is out -- of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE read #-} read :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> m a read GrowVec {..} i = do@@ -137,7 +137,7 @@ -- | \(O(1)\) Writes to the element at the given position. Will throw an exception if the index is -- out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE write #-} write :: (HasCallStack, PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> Int -> a -> m () write GrowVec {..} i x = do@@ -148,7 +148,7 @@  -- | Amortized \(O(1)\). Grow the capacity twice ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pushBack #-} pushBack :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> a -> m () pushBack GrowVec {..} e = do@@ -173,7 +173,7 @@  -- | \(O(1)\) Removes the last element from the buffer and returns it, or `Nothing` if it is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE popBack #-} popBack :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (Maybe a) popBack GrowVec {..} = do@@ -187,7 +187,7 @@  -- | \(O(1)\) `popBack` with return value discarded. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE popBack_ #-} popBack_ :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m () popBack_ GrowVec {..} = do@@ -196,7 +196,7 @@  -- | \(O(1)\) Returns the number of elements in the vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE length #-} length :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Int length GrowVec {posGV} = do@@ -204,7 +204,7 @@  -- | \(O(1)\) Returns the capacity of the internal the vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE capacity #-} capacity :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Int capacity GrowVec {vecGV} = do@@ -213,14 +213,14 @@  -- | \(O(1)\) Returns `True` if the vector is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE null #-} null :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m Bool null = (<$>) (== 0) . length  -- | \(O(n)\) Yields an immutable copy of the mutable vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE freeze #-} freeze :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (VU.Vector a) freeze GrowVec {..} = do@@ -231,7 +231,7 @@ -- | \(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable -- vector may not be used after this operation. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeFreeze #-} unsafeFreeze :: (PrimMonad m, VU.Unbox a) => GrowVec (PrimState m) a -> m (VU.Vector a) unsafeFreeze GrowVec {..} = do
src/AtCoder/Internal/Math.hs view
@@ -1,6 +1,6 @@ -- | Internal math implementation. ----- ==== Example+-- ==== __Example__ -- >>> import AtCoder.Internal.Math -- >>> powMod 10 60 998244353 -- 10^60 mod 998244353 -- 526662729@@ -23,7 +23,7 @@ -- >>> floorSumUnsigned 8 12 3 5 -- 6 ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Math   ( powMod,     isPrime,@@ -62,7 +62,7 @@ -- >>> powMod 10 60 m -- 10^60 mod m -- 526662729 ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE powMod #-} powMod :: (HasCallStack) => Int -> Int -> Int -> Int powMod x n0 m0@@ -81,7 +81,7 @@  -- | M. Forisek and J. Jancina, Fast Primality Testing for Integers That Fit into a Machine Word ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE isPrime #-} isPrime :: Int -> Bool isPrime n@@ -105,7 +105,7 @@ -- ==== Constraints -- - \(1 \le b\) (not asserted) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE invGcd #-} invGcd :: Int -> Int -> (Int, Int) invGcd a0 b@@ -130,7 +130,7 @@  -- | Returns primitive root. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE primitiveRoot #-} primitiveRoot :: Int -> Int primitiveRoot m@@ -176,7 +176,7 @@ -- ==== Complexity -- - \(O(\log m)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE floorSumUnsigned #-} floorSumUnsigned :: Int -> Int -> Int -> Int -> Int floorSumUnsigned = inner 0
src/AtCoder/Internal/McfCsr.hs view
@@ -3,7 +3,7 @@  -- | Internal CSR for `AtCoder.MinCostFlow`. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.McfCsr   ( -- * Compressed sparse row     Csr (..),@@ -26,25 +26,25 @@  -- | CSR for min cost flow. ----- @since 1.0.0+-- @since 1.0.0.0 data Csr s cap cost = Csr-  { -- | @since 1.0.0+  { -- | @since 1.0.0.0     startCsr :: !(VU.Vector Int),-    -- | @since 1.0.0+    -- | @since 1.0.0.0     toCsr :: !(VU.Vector Int),-    -- | @since 1.0.0+    -- | @since 1.0.0.0     revCsr :: !(VU.Vector Int),     -- | Mutable.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     capCsr :: !(VUM.MVector s cap),-    -- | @since 1.0.0+    -- | @since 1.0.0.0     costCsr :: !(VU.Vector cost)   }  -- | \(O(n + m)\) Creates `Csr`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (HasCallStack, Num cap, VU.Unbox cap, VU.Unbox cost, Num cost, PrimMonad m) => Int -> VU.Vector (Int, Int, cap, cap, cost) -> m (VU.Vector Int, Csr (PrimState m) cap cost) build n edges = do@@ -94,7 +94,7 @@  -- | \(O(1)\) Returns a vector of @(to, rev, cost)@. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE adj #-} adj :: (HasCallStack, Num cap, VU.Unbox cap, VU.Unbox cost) => Csr s cap cost -> Int -> VU.Vector (Int, Int, cost) adj Csr {..} v = VU.slice offset len vec
src/AtCoder/Internal/MinHeap.hs view
@@ -4,7 +4,7 @@ -- -- <https://en.wikipedia.org/wiki/Binary_heap> ----- ==== Example+-- ==== __Example__ -- >>> import AtCoder.Internal.MinHeap qualified as MH -- >>> heap <- MH.new @Int 4 -- >>> MH.capacity heap@@ -29,7 +29,7 @@ -- >>> MH.null heap -- True ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.MinHeap   ( -- * Heap     Heap,@@ -73,7 +73,7 @@ -- -- INVARIANT (min heap): child values are bigger than or equal to their parent value. ----- @since 1.0.0+-- @since 1.0.0.0 data Heap s a = Heap   { -- | Size of the heap.     sizeBH_ :: !(VUM.MVector s Int),@@ -83,7 +83,7 @@  -- | \(O(n)\) Creates `Heap` with capacity \(n\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (VU.Unbox a, PrimMonad m) => Int -> m (Heap (PrimState m) a) new n = do@@ -93,35 +93,35 @@  -- | \(O(1)\) Returns the maximum number of elements in the heap. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE capacity #-} capacity :: (VU.Unbox a) => Heap s a -> Int capacity = VUM.length . dataBH  -- | \(O(1)\) Returns the number of elements in the heap. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE length #-} length :: (VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Int length Heap {sizeBH_} = VGM.unsafeRead sizeBH_ 0  -- | \(O(1)\) Returns `True` if the heap is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE null #-} null :: (VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Bool null = (<$>) (== 0) . length  -- | \(O(1)\) Sets the `length` to zero. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE clear #-} clear :: (VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m () clear Heap {sizeBH_} = VGM.unsafeWrite sizeBH_ 0 0  -- | \(O(\log n)\) Inserts an element to the heap. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE push #-} push :: (HasCallStack, Ord a, VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> a -> m () push Heap {..} x = do@@ -138,7 +138,7 @@  -- | \(O(1)\) Returns the smallest value in the heap, or `Nothing` if it is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE peek #-} peek :: (VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a) peek heap = do@@ -150,7 +150,7 @@ -- | \(O(\log n)\) Removes the last element from the heap and returns it, or `Nothing` if it is -- empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pop #-} pop :: (HasCallStack, Ord a, VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a) pop heap@Heap {..} = do@@ -191,7 +191,7 @@  -- | \(O(\log n)\) `pop` with return value discarded. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pop_ #-} pop_ :: (HasCallStack, Ord a, VU.Unbox a, PrimMonad m) => Heap (PrimState m) a -> m () pop_ heap = do
src/AtCoder/Internal/Queue.hs view
@@ -2,7 +2,7 @@  -- | Fixed-sized queue. Internally it has \(l, r\) pair of valid element bounds. ----- ==== Example+-- ==== __Example__ -- >>> import AtCoder.Internal.Queue qualified as Q -- >>> que <- Q.new @_ @Int 3 -- >>> Q.capacity que@@ -35,7 +35,7 @@ -- >>> Q.freeze que -- [0,1,2] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Queue   ( -- * Queue     Queue,@@ -72,7 +72,7 @@  -- | Fixed-sized queue. Internally it has \([l, r)\) pair of valid element bounds. ----- @since 1.0.0+-- @since 1.0.0.0 data Queue s a = Queue   { -- | Stores [l, r) range in the `vecQ`.     posQ :: !(VUM.MVector s Int),@@ -81,7 +81,7 @@  -- | \(O(n)\) Creates `Queue` with capacity \(n\). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m, VU.Unbox a) => Int -> m (Queue (PrimState m) a) new n = do@@ -91,7 +91,7 @@  -- | \(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pushBack #-} pushBack :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> a -> m () pushBack Queue {..} e = do@@ -105,7 +105,7 @@  -- | \(O(1)\) Appends an element to the back. Will throw an exception if the index is out of range. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pushFront #-} pushFront :: (HasCallStack, PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> a -> m () pushFront Queue {..} e = do@@ -123,7 +123,7 @@  -- | \(O(1)\) Removes the first element from the queue and returns it, or `Nothing` if it is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE popFront #-} popFront :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (Maybe a) popFront Queue {..} = do@@ -138,7 +138,7 @@  -- | \(O(1)\) `popFront` with return value discarded. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE popFront_ #-} popFront_ :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m () popFront_ que = do@@ -147,14 +147,14 @@  -- | \(O(1)\) Returns the array size. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE capacity #-} capacity :: (VU.Unbox a) => Queue s a -> Int capacity = VUM.length . vecQ  -- | \(O(1)\) Returns the number of elements in the queue. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE length #-} length :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m Int length Queue {..} = do@@ -164,14 +164,14 @@  -- | \(O(1)\) Returns `True` if the buffer is empty. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE null #-} null :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m Bool null = (<$>) (== 0) . length  -- | \(O(1)\) Sets the `length` to zero. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE clear #-} clear :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m () clear Queue {..} = do@@ -179,7 +179,7 @@  -- | \(O(n)\) Yields an immutable copy of the mutable vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE freeze #-} freeze :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (VU.Vector a) freeze Queue {..} = do@@ -190,7 +190,7 @@ -- | \(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable -- vector may not be used after this operation. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeFreeze #-} unsafeFreeze :: (PrimMonad m, VU.Unbox a) => Queue (PrimState m) a -> m (VU.Vector a) unsafeFreeze Queue {..} = do
src/AtCoder/Internal/Scc.hs view
@@ -1,8 +1,9 @@ {-# LANGUAGE RecordWildCards #-}+{-# OPTIONS_HADDOCK hide #-}  -- | Implementation of Strongly Connected Components calculation. Use `AtCoder.Scc` instead. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Internal.Scc   ( -- * Internal SCC     SccGraph (nScc),@@ -34,18 +35,18 @@  -- | Graph for collecting strongly connected components. ----- @since 1.0.0+-- @since 1.0.0.0 data SccGraph s = SccGraph   { -- | The number of vertices.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nScc :: {-# UNPACK #-} !Int,     edgesScc :: !(ACIGV.GrowVec s (Int, Int))   }  -- | \(O(n)\) Creates `SccGraph` of \(n\) vertices. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m) => Int -> m (SccGraph (PrimState m)) new nScc = do@@ -54,7 +55,7 @@  -- | \(O(1)\) amortized. Adds an edge to the graph. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge #-} addEdge :: (PrimMonad m) => SccGraph (PrimState m) -> Int -> Int -> m () addEdge SccGraph {edgesScc} from to = do@@ -62,7 +63,7 @@  -- | \(O(n + m)\) Returns a pair of @(# of scc, scc id)@. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE sccIds #-} sccIds :: (PrimMonad m) => SccGraph (PrimState m) -> m (Int, VU.Vector Int) sccIds SccGraph {..} = do@@ -138,7 +139,7 @@  -- | \(O(n + m)\) Returns the strongly connected components. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE scc #-} scc :: (PrimMonad m) => SccGraph (PrimState m) -> m (V.Vector (VU.Vector Int)) scc g = do
src/AtCoder/Internal/String.hs view
@@ -1,4 +1,4 @@--- | Internal implementation of `AtCoder.String` module.+-- | Internal implementation of @AtCoder.String@ module. module AtCoder.Internal.String   ( -- * Suffix array     saNaive,@@ -24,7 +24,7 @@  -- | \(O(n^2)\) Internal implementation of suffix array creation (naive). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE saNaive #-} saNaive :: (HasCallStack) => VU.Vector Int -> VU.Vector Int saNaive s =@@ -47,7 +47,7 @@  -- | \(O(n \log n)\) Internal implementation of suffix array creation (doubling). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE saDoubling #-} saDoubling :: (HasCallStack) => VU.Vector Int -> VU.Vector Int saDoubling s = VU.create $ do@@ -86,7 +86,7 @@  -- | \(O(n)\) Internal implementation of suffix array creation (suffix array induced sorting). ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE saIsImpl #-} saIsImpl :: (HasCallStack) => Int -> Int -> VU.Vector Int -> Int -> VU.Vector Int saIsImpl naiveThreshold doublingThreshold s upper = VU.create $ do@@ -245,7 +245,7 @@ -- G. Nong, S. Zhang, and W. H. Chan, -- Two Efficient Algorithms for Linear Time Suffix Array Construction ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE saIs #-} saIs :: (HasCallStack) => VU.Vector Int -> Int -> VU.Vector Int saIs = saIsManual 10 40@@ -257,7 +257,7 @@ -- G. Nong, S. Zhang, and W. H. Chan, -- Two Efficient Algorithms for Linear Time Suffix Array Construction ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE saIsManual #-} saIsManual :: (HasCallStack) => Int -> Int -> VU.Vector Int -> Int -> VU.Vector Int saIsManual naiveThreshold doublingThreshold s upper
src/AtCoder/LazySegTree.hs view
@@ -69,16 +69,16 @@ -- -- - `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'+-- - If you ever need to store boxed types to `LazySegTree`, wrap it in 'vector:Data.Vector.Unboxed.DoNotUnboxStrict' -- or the like. -- -- ==== Major changes from the original @ac-library@ -- - The API is based on `Monoid` and `SegAct`, not the functions @op@, @e@, @mapping@, -- @composition@ and @id@.--- - The functions names follow the vector package: @get@ and @set@ are renamed to `read` and--- `write`. `modify`, `modifyM`, `freeze` and `unsafeFreeze` are added.+-- - @get@ and @set@ are renamed to `read` and `write`.+-- - `modify`, `modifyM`, `freeze` and `unsafeFreeze` are added. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.LazySegTree   ( -- Lazy segment tree     SegAct (..),@@ -268,11 +268,11 @@ --   putStrLn "=> test passed!" -- @ ----- @since 1.0.0+-- @since 1.0.0.0 class (Monoid f) => SegAct f a where   -- | Lazy segment tree action \(f(x)\).   ---  -- @since 1.0.0+  -- @since 1.0.0.0   {-# INLINE segAct #-}   segAct :: f -> a -> a   segAct = segActWithLength 1@@ -282,26 +282,26 @@   -- If you implement `SegAct` with this function, you don't have to store the monoid's length,   -- since it's given externally.   ---  -- @since 1.0.0+  -- @since 1.0.0.0   {-# INLINE segActWithLength #-}   segActWithLength :: Int -> f -> a -> a   segActWithLength _ = segAct  -- | Lazy segment tree defined around `SegAct`. ----- @since 1.0.0+-- @since 1.0.0.0 data LazySegTree s f a = LazySegTree   { -- | Valid length.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nLst :: {-# UNPACK #-} !Int,     -- | \(\lceil \log_2 \mathrm{nLst} \rceil\)     ---    -- @since 1.0.0+    -- @since 1.0.0.0     sizeLst :: {-# UNPACK #-} !Int,     -- | \(\log_2 \mathrm{sizeLst}\).     ---    -- @since 1.0.0+    -- @since 1.0.0.0     logLst :: {-# UNPACK #-} !Int,     -- | Data storage of length @2 * sizeLst@.     dLst :: !(VUM.MVector s a),@@ -309,7 +309,7 @@     lzLst :: !(VUM.MVector s f)   } --- | Creates an array of length @n@. All the elements are initialized to `mempty`.+-- | Creates an array of length \(n\). All the elements are initialized to `mempty`. -- -- ==== Constraints -- - \(0 \leq n\)@@ -317,14 +317,14 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Int -> m (LazySegTree (PrimState m) f a) new nLst   | nLst >= 0 = build $ VU.replicate nLst mempty   | otherwise = error $ "new: given negative size `" ++ show nLst ++ "`" --- | Creates an array with initial values @vs@.+-- | Creates an array with initial values \(vs\). -- -- ==== Constraints -- - \(0 \leq n\)@@ -332,7 +332,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => VU.Vector a -> m (LazySegTree (PrimState m) f a) build vs = do@@ -356,7 +356,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE write #-} write :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m () write self@LazySegTree {..} p x = do@@ -368,7 +368,7 @@   for_ [1 .. logLst] $ \i -> do     update self $ p' .>>. i --- | (Extra API) Modifies \(p\)-th value of the array to \(x\).+-- | (Extra API) Modifies \(p\)-th value with a function \(f\). -- -- ==== Constraints -- - \(0 \leq p \lt n\)@@ -376,7 +376,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modify #-} modify :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m () modify self@LazySegTree {..} f p = do@@ -388,7 +388,7 @@   for_ [1 .. logLst] $ \i -> do     update self $ p' .>>. i --- | (Extra API) Modifies \(p\)-th value of the array to \(x\).+-- | (Extra API) Modifies \(p\)-th value with a monadic function \(f\). -- -- ==== Constraints -- - \(0 \leq p \lt n\)@@ -396,7 +396,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modifyM #-} modifyM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> (a -> m a) -> Int -> m () modifyM self@LazySegTree {..} f p = do@@ -416,7 +416,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE read #-} read :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> m a read self@LazySegTree {..} p = do@@ -435,7 +435,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE prod #-} prod :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m a prod self@LazySegTree {nLst} l0 r0@@ -444,13 +444,13 @@   | otherwise = unsafeProd self l0 r0  -- | Total version of `prod`. Returns the product of \([a[l], ..., a[r - 1]]\), assuming the--- properties of the monoid. It returns `'Just' 'mempty'` if \(l = r\). It returns `Nothing` for--- invalid intervals.+-- properties of the monoid. It returns `Just` `mempty` if \(l = r\). It returns `Nothing` if the+-- interval is invalid. -- -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE prodMaybe #-} prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m (Maybe a) prodMaybe self@LazySegTree {nLst} l0 r0@@ -489,7 +489,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE allProd #-} allProd :: (PrimMonad m, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m a allProd LazySegTree {..} = VGM.read dLst 1@@ -502,7 +502,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE applyAt #-} applyAt :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> f -> m () applyAt self@LazySegTree {..} p f = do@@ -525,7 +525,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE applyIn #-} applyIn :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> f -> m () applyIn self@LazySegTree {..} l0 r0 f@@ -572,7 +572,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE minLeft #-} minLeft :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int minLeft seg r0 g = minLeftM seg r0 (pure . g)@@ -588,7 +588,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE minLeftM #-} minLeftM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int minLeftM self@LazySegTree {..} r0 g = do@@ -647,7 +647,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE maxRight #-} maxRight :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int maxRight seg l0 g = maxRightM seg l0 (pure . g)@@ -663,7 +663,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE maxRightM #-} maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int maxRightM self@LazySegTree {..} l0 g = do@@ -708,7 +708,7 @@  -- | \(O(n)\) Yields an immutable copy of the mutable vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE freeze #-} freeze :: (PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m (VU.Vector a) freeze self@LazySegTree {..} = do@@ -720,7 +720,7 @@ -- | \(O(n)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable -- vector may not be used after this operation. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeFreeze #-} unsafeFreeze :: (PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m (VU.Vector a) unsafeFreeze self@LazySegTree {..} = do
src/AtCoder/Math.hs view
@@ -2,7 +2,7 @@  -- | Math module. It contains number-theoretic algorithms. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Math   ( -- * Modulus operations     -- These functions are internally used for `AtCoder.ModInt`.@@ -40,7 +40,7 @@ -- >>> (invMod 2 m) * 2 `mod` m -- (2^(-1) mod m) * 2 mod m -- 1 ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE invMod #-} invMod :: (HasCallStack) => Int -> Int -> Int invMod x m =@@ -84,7 +84,7 @@ -- >>> VU.zipWith mod rs ms == VU.map (y `mod`) ms -- True ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE crt #-} crt :: (HasCallStack) => VU.Vector Int -> VU.Vector Int -> (Int, Int) crt r m = loop 0 1 [0 .. VU.length r - 1]@@ -148,7 +148,7 @@ --                  n = 5 -- @ ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE floorSum #-} floorSum :: (HasCallStack) => Int -> Int -> Int -> Int -> Int floorSum n m a b = ACIM.floorSumUnsigned n m a' b' - da - db
src/AtCoder/MaxFlow.hs view
@@ -8,7 +8,7 @@ -- >>> import AtCoder.MaxFlow qualified as MF -- >>> g <- MF.new @_ @Int 3        --  0     1     2 ----- Build a simple graph with `'addEdge' g from to cap` or `addEdge_`:+-- Build a simple graph with @'addEdge' g from to cap@ or `addEdge_`: -- -- >>> MF.addEdge g 0 1 (2 :: Int)  --  0 --> 1     2 -- 0@@ -21,7 +21,7 @@ -- 1 -- -- Get the minimum cut with `minCut`. In this case, removing the second edge makes the minimum cut--- (note that the edge capacity (`1`) = max flow):+-- (note that the edge capacity (\(1\)) = max flow): -- -- >>> MF.minCut g 0 -- returns a Bit vector. `1` (`Bit True`) is on the `s` side. -- [1,1,0]@@ -31,7 +31,7 @@ -- >>> MF.getEdge g 0 -- returns (from, to, cap, flow) -- (0,1,2,1) ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.MaxFlow   ( -- * Max flow graph     MfGraph (nG),@@ -76,11 +76,11 @@  -- | Max flow graph. ----- @since 1.0.0+-- @since 1.0.0.0 data MfGraph s cap = MfGraph   { -- | The number of vertices.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nG :: {-# UNPACK #-} !Int,     -- | MfGraph: fromVertex -> vector of @(toVertex, revEdgeIndex, capacity)@.     gG :: !(V.Vector (ACIGV.GrowVec s (Int, Int, cap))),@@ -88,7 +88,7 @@     posG :: !(ACIGV.GrowVec s (Int, Int))   } --- | Creates a graph of @n@ vertices and \(0\) edges. `cap` is the type of the capacity.+-- | Creates a graph of \(n\) vertices and \(0\) edges. `cap` is the type of the capacity. -- -- ==== Constraints -- - \(0 \leq n\)@@ -96,7 +96,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m, VU.Unbox cap) => Int -> m (MfGraph (PrimState m) cap) new nG = do@@ -114,7 +114,7 @@ -- ==== Complexity -- - \(O(1)\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge #-} addEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m Int addEdge MfGraph {..} from to cap = do@@ -140,7 +140,7 @@ -- ==== Complexity -- - \(O(1)\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge_ #-} addEdge_ :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m () addEdge_ graph from to cap = do@@ -159,7 +159,7 @@ -- - \(O(n^2 m)\) (general), or -- - \(O(F(n + m))\), where \(F\) is the returned value ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE flow #-} flow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> cap -> m cap flow MfGraph {..} s t flowLimit = do@@ -251,7 +251,7 @@ -- - \(O(n^2 m)\) (general), or -- - \(O(F(n + m))\), where \(F\) is the returned value ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE maxFlow #-} maxFlow :: (HasCallStack, PrimMonad m, Num cap, Ord cap, Bounded cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> Int -> m cap maxFlow graph s t = flow graph s t maxBound@@ -263,7 +263,7 @@ -- ==== Complexity -- - \(O(n + m)\), where \(m\) is the number of added edges. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE minCut #-} minCut :: (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (VU.Vector Bit) minCut MfGraph {..} s = do@@ -294,7 +294,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE getEdge #-} getEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> m (Int, Int, cap, cap) getEdge MfGraph {..} i = do@@ -311,7 +311,7 @@ -- ==== Complexity -- - \(O(m)\), where \(m\) is the number of added edges. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE edges #-} edges :: (PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> m (VU.Vector (Int, Int, cap, cap)) edges g@MfGraph {posG} = do@@ -327,7 +327,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE changeEdge #-} changeEdge :: (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap) => MfGraph (PrimState m) cap -> Int -> cap -> cap -> m () changeEdge MfGraph {..} i newCap newFlow = do
src/AtCoder/MinCostFlow.hs view
@@ -23,7 +23,7 @@ -- Note that you can't call `flow`, `maxFlow` or `slope` multiple times, or else you'll get wrong -- return value. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.MinCostFlow   ( -- * Minimum cost flow     McfGraph (nG),@@ -70,11 +70,11 @@  -- | Min cost flow graph. ----- @since 1.0.0+-- @since 1.0.0.0 data McfGraph s cap cost = McfGraph   { -- | The number of vertices.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nG :: {-# UNPACK #-} !Int,     -- | fromVertex -> vector of @(from, to, cap, flow, cost)@.     edgesG :: !(ACIGV.GrowVec s (Int, Int, cap, cap, cost))@@ -89,7 +89,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m, VU.Unbox cap, VU.Unbox cost) => Int -> m (McfGraph (PrimState m) cap cost) new nG = do@@ -106,7 +106,7 @@ -- ==== Complexity -- - \(O(1)\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge #-} addEdge ::   (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, VU.Unbox cost) =>@@ -134,7 +134,7 @@ -- ==== Complexity -- - \(O(1)\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge_ #-} addEdge_ ::   (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, VU.Unbox cost) =>@@ -157,7 +157,7 @@ -- ==== Complexity -- - Same as `slope`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE flow #-} flow ::   (HasCallStack, PrimMonad m, Integral cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, Bounded cost, VU.Unbox cost) =>@@ -178,7 +178,7 @@ -- ==== Complexity -- - Same as `slope`. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE maxFlow #-} maxFlow ::   (HasCallStack, PrimMonad m, Integral cap, Ord cap, Bounded cap, VU.Unbox cap, Num cost, Ord cost, Bounded cost, VU.Unbox cost) =>@@ -212,7 +212,7 @@ -- ==== Complexity -- - \(O(F (n + m) \log (n + m))\), where \(F\) is the amount of the flow and \(m\) is the number of added edges. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE slope #-} slope ::   (HasCallStack, PrimMonad m, Integral cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, Bounded cost, VU.Unbox cost) =>@@ -364,7 +364,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE getEdge #-} getEdge ::   (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, VU.Unbox cost) =>@@ -382,7 +382,7 @@ -- ==== Complexity -- - \(O(m)\), where \(m\) is the number of added edges. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE edges #-} edges ::   (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, VU.Unbox cost) =>@@ -397,7 +397,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeEdges #-} unsafeEdges ::   (HasCallStack, PrimMonad m, Num cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, VU.Unbox cost) =>
src/AtCoder/ModInt.hs view
@@ -16,7 +16,7 @@ -- ==== Major changes from the original @ac-library@ -- - @DynamicModInt@ is removed. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.ModInt   ( -- * Modulus     Modulus (..),@@ -75,17 +75,17 @@  -- | `KnownNat` with meta information used for modulus. ----- @since 1.0.0+-- @since 1.0.0.0 class (KnownNat a) => Modulus a where   -- | Returns if the modulus is a prime value.   ---  -- @since 1.0.0+  -- @since 1.0.0.0   isPrimeModulus :: Proxy# a -> Bool    -- | Returns the primitive root of the modulus value. Note that the default implementation is   -- slow.   ---  -- @since 1.0.0+  -- @since 1.0.0.0   {-# INLINE primitiveRootModulus #-}   primitiveRootModulus :: Proxy# a -> Int   -- we could use `AllowAmbigousTypes` or `Tagged` newtype, but `Proxy#` wasn't so slow.@@ -94,7 +94,7 @@  -- | \(2^{24} - 1\). ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 167772161 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -103,7 +103,7 @@  -- | \(2^{25} - 1\). ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 469762049 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -112,7 +112,7 @@  -- | \(2^{26} - 1\). ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 754974721 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -121,7 +121,7 @@  -- | \(119 \times 2^{23} + 1\). It is often used in contest problems ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 998244353 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -130,7 +130,7 @@  -- | It used to be used in contest problems. ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 1000000007 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -139,7 +139,7 @@  -- | \(2^{31} - 1\), suitable for boundary testing. ----- @since 1.0.0+-- @since 1.0.0.0 instance Modulus 2147483647 where   {-# INLINE isPrimeModulus #-}   isPrimeModulus _ = True@@ -148,12 +148,12 @@  -- | `ModInt` with modulus value @998244353@. ----- @since 1.0.0+-- @since 1.0.0.0 type ModInt998244353 = ModInt 998244353  -- | `ModInt` with modulus value @1000000007@. ----- @since 1.0.0+-- @since 1.0.0.0 type ModInt1000000007 = ModInt 1000000007  -- | Retrieves `Int` from `KnownNat`.@@ -162,7 +162,7 @@ -- >>> modVal (Proxy @42) -- 42 ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modVal #-} modVal :: forall a. (KnownNat a) => Proxy a -> Int modVal p = fromIntegral $ natVal p@@ -174,28 +174,28 @@ -- >>> modVal# (proxy# @42) -- 42 ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modVal# #-} modVal# :: forall a. (KnownNat a) => Proxy# a -> Int modVal# p = fromIntegral $ natVal' p  -- | Creates `ModInt` from an `Int` value taking mod. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: forall a. (KnownNat a) => Int -> ModInt a new v = ModInt . fromIntegral $ v `mod` fromIntegral (natVal' (proxy# @a))  -- | Creates `ModInt` from a `Word32` value taking mod. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new32 #-} new32 :: forall a. (KnownNat a) => Word32 -> ModInt a new32 v = ModInt $ v `mod` fromIntegral (natVal' (proxy# @a))  -- | Creates `ModInt` from a `Word64` value taking mod. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new64 #-} new64 :: forall a. (KnownNat a) => Word64 -> ModInt a new64 v = ModInt . fromIntegral $ v `mod` fromIntegral (natVal' (proxy# @a))@@ -205,7 +205,7 @@ -- ==== Constraints -- - \(0 \leq x \lt \mathrm{mod}\) (not asserted at runtime) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeNew #-} unsafeNew :: (KnownNat a) => Word32 -> ModInt a unsafeNew = ModInt@@ -213,17 +213,17 @@ -- | `Word32` value that treats the modula arithmetic. newtype ModInt a = ModInt {unModInt :: Word32}   deriving-    ( -- @since 1.0.0+    ( -- @since 1.0.0.0       P.Prim     )   deriving newtype-    ( -- @since 1.0.0+    ( -- @since 1.0.0.0       Eq,-      -- @since 1.0.0+      -- @since 1.0.0.0       Ord,-      -- @since 1.0.0+      -- @since 1.0.0.0       Read,-      -- @since 1.0.0+      -- @since 1.0.0.0       Show     ) @@ -232,7 +232,7 @@ -- ==== Complecity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modulus #-} modulus :: forall a. (KnownNat a) => ModInt a -> Int modulus _ = fromIntegral (natVal' (proxy# @a))@@ -242,7 +242,7 @@ -- ==== Complecity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE val #-} val :: (KnownNat a) => ModInt a -> Int val = fromIntegral . unModInt@@ -253,7 +253,7 @@ -- ==== Complecity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE val32 #-} val32 :: (KnownNat a) => ModInt a -> Word32 val32 = unModInt@@ -263,7 +263,7 @@ -- ==== Complecity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE val64 #-} val64 :: (KnownNat a) => ModInt a -> Word64 val64 = fromIntegral . unModInt@@ -276,7 +276,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE pow #-} pow :: forall a. (HasCallStack, KnownNat a) => ModInt a -> Int -> ModInt a pow (ModInt x0) n0 = ModInt . fromIntegral $ inner n0 1 (fromIntegral x0)@@ -310,7 +310,7 @@ -- ==== Complexity -- - \(O(\log \mathrm{mod})\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE inv #-} inv :: forall a. (HasCallStack, Modulus a) => ModInt a -> ModInt a inv self@(ModInt x)@@ -322,10 +322,10 @@           !_ = ACIA.runtimeAssert (eg1 == 1) "AtCoder.ModInt.inv: `x^(-1) mod m` cannot be calculated when `gcd x modulus /= 1`"        in fromIntegral eg2 --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 deriving newtype instance (KnownNat p) => Real (ModInt p) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance (KnownNat p) => Num (ModInt p) where   {-# INLINE (+) #-}   (ModInt !x1) + (ModInt !x2)@@ -355,45 +355,45 @@   {-# INLINE fromInteger #-}   fromInteger = ModInt . fromInteger . (`mod` fromIntegral (natVal' (proxy# @p))) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance (KnownNat p) => Bounded (ModInt p) where   {-# INLINE minBound #-}   minBound = ModInt 0   {-# INLINE maxBound #-}   maxBound = ModInt $! fromIntegral (natVal' (proxy# @p)) - 1 --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance (KnownNat p) => Enum (ModInt p) where   {-# INLINE toEnum #-}   toEnum = new   {-# INLINE fromEnum #-}   fromEnum = fromIntegral . unModInt --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance (Modulus p) => Integral (ModInt p) where   {-# INLINE quotRem #-}   quotRem x y = (x / y, x - x / y * y)   {-# INLINE toInteger #-}   toInteger = coerce (toInteger @Word32) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance (Modulus p) => Fractional (ModInt p) where   {-# INLINE recip #-}   recip = inv   {-# INLINE fromRational #-}   fromRational q = fromInteger (numerator q) / fromInteger (denominator q) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 newtype instance VU.MVector s (ModInt a) = MV_ModInt (VU.MVector s Word32) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 newtype instance VU.Vector (ModInt a) = V_ModInt (VU.Vector Word32) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 deriving newtype instance VGM.MVector VU.MVector (ModInt a) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 deriving newtype instance VG.Vector VU.Vector (ModInt a) --- | -- @since 1.0.0+-- | -- @since 1.0.0.0 instance VU.Unbox (ModInt a)
src/AtCoder/Scc.hs view
@@ -12,7 +12,7 @@ -- >>> Scc.scc gr -- [[3],[0,1],[2]] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.Scc (SccGraph, nScc, new, addEdge, scc) where  import AtCoder.Internal.Assert qualified as ACIA@@ -24,12 +24,12 @@  -- | Directed graph for calculating strongly connected components. ----- @since 1.0.0+-- @since 1.0.0.0 newtype SccGraph s = SccGraph (ACISCC.SccGraph s)  -- | Returns the number of vertices in the SCC graph. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE nScc #-} nScc :: SccGraph s -> Int nScc (SccGraph g) = ACISCC.nScc g@@ -42,7 +42,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m) => Int -> m (SccGraph (PrimState m)) new n = SccGraph <$> ACISCC.new n@@ -56,7 +56,7 @@ -- ==== Complexity -- - \(O(1)\) amortized ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addEdge #-} addEdge :: (HasCallStack, PrimMonad m) => SccGraph (PrimState m) -> Int -> Int -> m () addEdge (SccGraph gr) from to = do@@ -74,7 +74,7 @@ -- ==== Complexity -- - \(O(n + m)\), where \(m\) is the number of added edges. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE scc #-} scc :: (PrimMonad m) => SccGraph (PrimState m) -> m (V.Vector (VU.Vector Int)) scc (SccGraph g) = ACISCC.scc g
src/AtCoder/SegTree.hs view
@@ -57,7 +57,7 @@ -- -- - `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 `SegTree`, wrap it in 'Data.Vector.Unboxed.DoNotUnboxStrict'+-- - If you ever need to store boxed types to `LazySegTree`, wrap it in 'vector:Data.Vector.Unboxed.DoNotUnboxStrict' -- or the like. -- -- ==== Major changes from the original @ac-library@@@ -65,7 +65,7 @@ -- - @get@ and @set@ are renamed to `read` and `write`. -- - `modify`, `modifyM`, `freeze` and `unsafeFreeze` are added. ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.SegTree   ( -- * Segment tree     SegTree (nSt, sizeSt, logSt),@@ -88,13 +88,13 @@     -- * Binary searches      -- ** Left binary searches-    maxRight,-    maxRightM,--    -- ** Right binary searches     minLeft,     minLeftM, +    -- ** Right binary searches+    maxRight,+    maxRightM,+     -- * Conversions     freeze,     unsafeFreeze,@@ -114,25 +114,25 @@  -- | Segment tree. ----- @since 1.0.0+-- @since 1.0.0.0 data SegTree s a = SegTree   { -- | THe number of vertices.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nSt :: {-# UNPACK #-} !Int,     -- | \(\lceil \log_2 \mathrm{nSt} \rceil\).     ---    -- @since 1.0.0+    -- @since 1.0.0.0     sizeSt :: {-# UNPACK #-} !Int,     -- | \(\log_2 \mathrm{sizeSt}\).     ---    -- @since 1.0.0+    -- @since 1.0.0.0     logSt :: {-# UNPACK #-} !Int,     -- | Data storage of length @2 * sizeSt@.     dSt :: !(VUM.MVector s a)   } --- | Creates an array @a@ of length @n@. All the elements are initialized to `mempty`.+-- | Creates an array \(a\) of length \(n\). All the elements are initialized to `mempty`. -- -- ==== Constraints -- - \(0 \leq n\)@@ -140,7 +140,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => Int -> m (SegTree (PrimState m) a) new nSt@@ -152,7 +152,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE build #-} build :: (PrimMonad m, Monoid a, VU.Unbox a) => VU.Vector a -> m (SegTree (PrimState m) a) build vs = do@@ -175,7 +175,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE write #-} write :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> a -> m () write self@SegTree {..} p x = do@@ -184,7 +184,7 @@   for_ [1 .. logSt] $ \i -> do     update self ((p + sizeSt) .>>. i) --- | (Extra API) Modifies \(p\)-th value of the array to \(x\).+-- | (Extra API) Modifies \(p\)-th value with a function \(f\). -- -- ==== Constraints -- - \(0 \leq p \lt n\)@@ -192,7 +192,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modify #-} modify :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> (a -> a) -> Int -> m () modify self@SegTree {..} f p = do@@ -201,7 +201,7 @@   for_ [1 .. logSt] $ \i -> do     update self ((p + sizeSt) .>>. i) --- | (Extra API) Modifies \(p\)-th value of the array to \(x\).+-- | (Extra API) Modifies \(p\)-th value with a monadic function \(f\). -- -- ==== Constraints -- - \(0 \leq p \lt n\)@@ -209,7 +209,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE modifyM #-} modifyM :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> (a -> m a) -> Int -> m () modifyM self@SegTree {..} f p = do@@ -226,7 +226,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE read #-} read :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> m a read SegTree {..} p = do@@ -242,7 +242,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE prod #-} prod :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> Int -> m a prod self@SegTree {nSt} l0 r0@@ -250,12 +250,13 @@   | otherwise = ACIA.errorInterval "AtCoder.SegTree.prod" l0 r0 nSt  -- | Total version of `prod`. Returns \(a[l] \cdot ... \cdot a[r - 1]\), assuming the properties of--- the monoid. It returns `'Just' 'mempty'` if \(l = r\). It return `Nothing` for invalid intervals.+-- the monoid. It returns `Just` `mempty` if \(l = r\). It return `Nothing` if the interval is+-- invalid. -- -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE prodMaybe #-} prodMaybe :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> Int -> m (Maybe a) prodMaybe self@SegTree {nSt} l0 r0@@ -288,81 +289,11 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE allProd #-} allProd :: (PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> m a allProd SegTree {..} = VGM.read dSt 1 --- | Applies a binary search on the segment tree. It returns an index \(r\) that satisfies both of the--- following.------ - \(r = l\) or \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\) returns `True`.--- - \(r = n\) or \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r]))\) returns `False`.------ If \(f\) is monotone, this is the maximum \(r\) that satisfies--- \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).------ ==== Constraints--- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.--- - @f mempty == True@.--- - \(0 \leq l \leq n\)------ ==== Complexity--- - \(O(\log n)\)------ @since 1.0.0-{-# INLINE maxRight #-}-maxRight :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> Bool) -> m Int-maxRight seg l0 f = maxRightM seg l0 (pure . f)---- | Moandic version of `maxRight`.------ ==== Constraints--- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.--- - @f mempty == True@.--- - \(0 \leq l \leq n\)------ ==== Complexity--- - \(O(\log n)\)------ @since 1.0.0-{-# INLINE maxRightM #-}-maxRightM :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int-maxRightM SegTree {..} l0 f = do-  b <- f mempty-  let !_ = ACIA.runtimeAssert b "AtCoder.SegTree.maxRightM: `f mempty` returned `False`"-  if l0 == nSt-    then pure nSt-    else inner (l0 + sizeSt) mempty-  where-    -- NOTE: Not ordinary bounds check!-    !_ = ACIA.runtimeAssert (0 <= l0 && l0 <= nSt) $ "AtCoder.SegTree.maxRightM: given invalid `left` index `" ++ show l0 ++ "` over length `" ++ show nSt ++ "`"-    inner l !sm = do-      let l' = chooseBit l-      !sm' <- (sm <>) <$> VGM.read dSt l'-      b <- f sm'-      if not b-        then do-          inner2 l' sm-        else do-          let l'' = l' + 1-          if (l'' .&. (-l'')) /= l''-            then inner l'' sm'-            else pure nSt-    chooseBit :: Int -> Int-    chooseBit l-      | even l = chooseBit $ l .>>. 1-      | otherwise = l-    inner2 l !sm-      | l < sizeSt = do-          let l' = 2 * l-          !sm' <- (sm <>) <$> VGM.read dSt l'-          b <- f sm'-          if b-            then inner2 (l' + 1) sm'-            else inner2 l' sm-      | otherwise = pure $ l - sizeSt- -- | Applies a binary search on the segment tree. It returns an index \(l\) that satisfies both of -- the following. --@@ -382,7 +313,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE minLeft #-} minLeft :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> Bool) -> m Int minLeft seg r0 f = minLeftM seg r0 (pure . f)@@ -399,7 +330,7 @@ -- ==== Complexity -- - \(O(\log n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE minLeftM #-} minLeftM :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int minLeftM SegTree {..} r0 f = do@@ -435,9 +366,79 @@             else inner2 r' sm       | otherwise = pure $ r + 1 - sizeSt +-- | Applies a binary search on the segment tree. It returns an index \(r\) that satisfies both of the+-- following.+--+-- - \(r = l\) or \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\) returns `True`.+-- - \(r = n\) or \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r]))\) returns `False`.+--+-- If \(f\) is monotone, this is the maximum \(r\) that satisfies+-- \(f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).+--+-- ==== Constraints+-- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.+-- - @f mempty == True@.+-- - \(0 \leq l \leq n\)+--+-- ==== Complexity+-- - \(O(\log n)\)+--+-- @since 1.0.0.0+{-# INLINE maxRight #-}+maxRight :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> Bool) -> m Int+maxRight seg l0 f = maxRightM seg l0 (pure . f)++-- | Moandic version of `maxRight`.+--+-- ==== Constraints+-- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.+-- - @f mempty == True@.+-- - \(0 \leq l \leq n\)+--+-- ==== Complexity+-- - \(O(\log n)\)+--+-- @since 1.0.0.0+{-# INLINE maxRightM #-}+maxRightM :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int+maxRightM SegTree {..} l0 f = do+  b <- f mempty+  let !_ = ACIA.runtimeAssert b "AtCoder.SegTree.maxRightM: `f mempty` returned `False`"+  if l0 == nSt+    then pure nSt+    else inner (l0 + sizeSt) mempty+  where+    -- NOTE: Not ordinary bounds check!+    !_ = ACIA.runtimeAssert (0 <= l0 && l0 <= nSt) $ "AtCoder.SegTree.maxRightM: given invalid `left` index `" ++ show l0 ++ "` over length `" ++ show nSt ++ "`"+    inner l !sm = do+      let l' = chooseBit l+      !sm' <- (sm <>) <$> VGM.read dSt l'+      b <- f sm'+      if not b+        then do+          inner2 l' sm+        else do+          let l'' = l' + 1+          if (l'' .&. (-l'')) /= l''+            then inner l'' sm'+            else pure nSt+    chooseBit :: Int -> Int+    chooseBit l+      | even l = chooseBit $ l .>>. 1+      | otherwise = l+    inner2 l !sm+      | l < sizeSt = do+          let l' = 2 * l+          !sm' <- (sm <>) <$> VGM.read dSt l'+          b <- f sm'+          if b+            then inner2 (l' + 1) sm'+            else inner2 l' sm+      | otherwise = pure $ l - sizeSt+ -- | \(O(n)\) Yields an immutable copy of the mutable vector. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE freeze #-} freeze :: (PrimMonad m, VU.Unbox a) => SegTree (PrimState m) a -> m (VU.Vector a) freeze SegTree {..} = do@@ -446,7 +447,7 @@ -- | \(O(1)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable -- vector may not be used after this operation. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeFreeze #-} unsafeFreeze :: (PrimMonad m, VU.Unbox a) => SegTree (PrimState m) a -> m (VU.Vector a) unsafeFreeze SegTree {..} = do
src/AtCoder/String.hs view
@@ -22,7 +22,7 @@ -- >>> S.zAlgorithmBS s -- [4,0,2,0] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.String   ( -- * Suffix array     suffixArray,@@ -67,7 +67,7 @@ -- ==== Complexity -- - (3) \(O(n + \mathrm{upper})\)-time ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE suffixArray #-} suffixArray :: (HasCallStack) => VU.Vector Int -> Int -> VU.Vector Int suffixArray s upper =@@ -83,7 +83,7 @@ -- ==== Complexity -- - (1) \(O(n)\)-time ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE suffixArrayBS #-} suffixArrayBS :: (HasCallStack) => BS.ByteString -> VU.Vector Int suffixArrayBS s = do@@ -99,7 +99,7 @@ -- ==== Complexity -- - (2) \(O(n \log n)\)-time, \(O(n)\)-space ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE suffixArrayOrd #-} suffixArrayOrd :: (HasCallStack, Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int suffixArrayOrd s =@@ -135,7 +135,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE lcpArray #-} lcpArray :: (HasCallStack, Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int -> VU.Vector Int lcpArray s sa =@@ -176,7 +176,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE lcpArrayBS #-} lcpArrayBS :: (HasCallStack) => BS.ByteString -> VU.Vector Int -> VU.Vector Int lcpArrayBS s sa =@@ -192,7 +192,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE zAlgorithm #-} zAlgorithm :: (Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int zAlgorithm s@@ -234,7 +234,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE zAlgorithmBS #-} zAlgorithmBS :: BS.ByteString -> VU.Vector Int zAlgorithmBS s = zAlgorithm $ VU.fromListN (BS.length s) (BS.unpack s)
src/AtCoder/TwoSat.hs view
@@ -19,7 +19,7 @@ -- >>> TS.answer ts -- [0] ----- @since 1.0.0+-- @since 1.0.0.0 module AtCoder.TwoSat   ( -- * TwoSat     TwoSat (nTs),@@ -46,11 +46,11 @@  -- | 2-SAT state. ----- @since 1.0.0+-- @since 1.0.0.0 data TwoSat s = TwoSat   { -- | The number of clauses the `TwoSat` can hold.     ---    -- @since 1.0.0+    -- @since 1.0.0.0     nTs :: {-# UNPACK #-} !Int,     answerTs :: !(VUM.MVector s Bit),     sccTs :: !(ACISCC.SccGraph s)@@ -64,7 +64,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE new #-} new :: (PrimMonad m) => Int -> m (TwoSat (PrimState m)) new nTs = do@@ -81,7 +81,7 @@ -- ==== Complexity -- - \(O(1)\) amortized. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE addClause #-} addClause :: (HasCallStack, PrimMonad m) => TwoSat (PrimState m) -> Int -> Bool -> Int -> Bool -> m () addClause TwoSat {..} i f j g = do@@ -99,7 +99,7 @@ -- ==== Complexity -- - \(O(n + m)\), where \(m\) is the number of added clauses. ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE satisfiable #-} satisfiable :: (PrimMonad m) => TwoSat (PrimState m) -> m Bool satisfiable TwoSat {..} = do@@ -119,7 +119,7 @@ -- ==== Complexity -- - \(O(n)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE answer #-} answer :: (PrimMonad m) => TwoSat (PrimState m) -> m (VU.Vector Bit) answer = VU.freeze . answerTs@@ -129,7 +129,7 @@ -- ==== Complexity -- - \(O(1)\) ----- @since 1.0.0+-- @since 1.0.0.0 {-# INLINE unsafeAnswer #-} unsafeAnswer :: (PrimMonad m) => TwoSat (PrimState m) -> m (VU.Vector Bit) unsafeAnswer = VU.unsafeFreeze . answerTs