packages feed

ac-library-hs 1.3.0.0 → 1.3.0.1

raw patch · 37 files changed

+472/−282 lines, 37 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

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.3.0.0+version:         1.3.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/Extra/Bisect.hs view
@@ -4,8 +4,8 @@ -- into two and return either the left or the right point of the boundary. -- -- @--- Y Y Y Y Y N N N N N      Y: user predicate holds--- --------* *---------> X  N: user predicate does not hold+-- Y Y Y Y Y N N N N N      Y: user predicate holds,+-- --------* *---------> x  N: user predicate does not hold, --         L R              L, R: left, right point of the boundary -- @ --@@ -41,11 +41,11 @@ import Data.Vector.Generic qualified as VG import GHC.Stack (HasCallStack) --- | \(O(\log n)\) Returns the maximum \(r\) where \(x \lt x_i\) holds for \(i \in [0, r)\).+-- | \(O(\log n)\) Returns the maximum \(r\) where \(x_i \lt x_0\) holds for \(i \in [0, r)\). -- -- @--- Y Y Y Y Y N N N N N      Y: (< x0)--- --------- *---------> X  N: (>= x0)+-- Y Y Y Y Y N N N N N      Y: x_i < x_0+-- --------- *---------> x  N: x_i >= x_0 --           R              R: the right boundary point returned -- @ --@@ -64,11 +64,7 @@ -- >>> lowerBound xs 4 -- 4 ----- Out of range values also return some index: ----- >>> lowerBound xs 0--- 0--- -- >>> lowerBound xs 5 -- 6 --@@ -79,11 +75,8 @@  -- | \(O(\log n)\) Computes the `lowerBound` for a slice of a vector within the interval \([l, r)\). ----- - The user predicate evaluates indices in \([l, r)\).--- -- ==== Constraints--- - \(0 \le l \lt n)--- - \(-1 \le r \le n)+-- - \(0 \le l \le r \le n\) -- -- ==== __Example__ -- >>> import Data.Vector.Unboxed qualified as VU@@ -111,17 +104,20 @@   where     !_ = ACIA.checkIntervalBounded "AtCoder.Extra.Bisect.lowerBoundIn" l r $ VG.length vec --- | \(O(\log n)\) Returns the maximum \(r\) where \(x \le x_i\) holds for \(i \in [0, r)\).+-- | \(O(\log n)\) Returns the maximum \(r\) where \(x_i \le x_0\) holds for \(i \in [0, r)\). -- -- @--- Y Y Y Y Y N N N N N      Y: (<= x0)--- --------- *---------> X  N: (> x0)+-- Y Y Y Y Y N N N N N      Y: x_i <= x_0,+-- --------- *---------> x  N: x_i > x_0, --           R              R: the right boundary point returned -- @ -- -- ==== __Example__ -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let xs = VU.fromList [10, 10, 20, 20, 40, 40]+-- >>> upperBound xs 0+-- 0+-- -- >>> upperBound xs 10 -- 2 --@@ -134,11 +130,6 @@ -- >>> upperBound xs 39 -- 4 ----- Out of range values:------ >>> upperBound xs 0--- 0--- -- >>> upperBound xs 40 -- 6 --@@ -149,8 +140,8 @@  -- | \(O(\log n)\) Computes the `upperBound` for a slice of a vector within the interval \([l, r)\). ----- - The user predicate evaluates indices in \([l, r)\).--- - The interval \([l, r)\) is silently clamped to ensure it remains within the bounds \([0, n)\).+-- ==== Constraints+-- - \(0 \le l \le r \le n\) -- -- ==== __Example__ -- >>> import Data.Vector.Unboxed qualified as VU@@ -185,8 +176,8 @@ -- right boundary point. -- -- @--- Y Y Y Y Y N N N N N      Y: user predicate holds--- --------- *---------> X  N: user predicate does not hold+-- Y Y Y Y Y N N N N N      Y: p(i) returns `true`,+-- --------- *---------> x  N: p(i) returns `false`, --           R              R: the right boundary point returned -- @ --@@ -216,7 +207,7 @@   Int ->   -- | \(p\)   (Int -> Bool) ->-  -- | Maximum \(r'\) where \(p\) holds for \([l, r')\).+  -- | Maximum \(r' (r' \le r)\) where \(p(i)\) holds for \(i \in [l, r')\).   Int maxRight l r p = runIdentity $ maxRightM l r (pure . p) @@ -233,8 +224,8 @@ -- left boundary point. -- -- @--- N N N N N Y Y Y Y Y      Y: user predicate holds--- --------* ----------> X  N: user predicate does not hold+-- N N N N N Y Y Y Y Y      Y: p(i) returns `true`,+-- --------* ----------> x  N: p(i) returns `false`, --         L                L: the left boundary point returned -- @ --@@ -261,7 +252,7 @@   Int ->   -- | \(p\)   (Int -> Bool) ->-  -- | Minimum \(l'\) where \(p\) holds for \([l', r)\)+  -- | Minimum \(l' (l' \ge l)\) where \(p(i)\) holds for \(i \in [l', r)\)   Int minLeft l r p = runIdentity $ minLeftM l r (pure . p)
src/AtCoder/Extra/Graph.hs view
@@ -19,6 +19,8 @@     rev,      -- * Generic graph functions++    -- TODO: generalize vertex dimensions?     topSort,     connectedComponents,     bipartiteVertexColors,@@ -34,25 +36,25 @@      -- ** BFS (breadth-first search) -    -- *** Constraints--    -- | - Edge weight \(w > 0\)+    -- | Constraints:+    --+    -- - Edge weight \(w > 0\)     bfs,     trackingBfs,      -- ** 01-BFS -    -- *** Constraints--    -- | - Edge weight \(w\) is either \(0\) or \(1\) of type `Int`.+    -- | Constraints:+    --+    -- - Edge weight \(w\) is either \(0\) or \(1\) of type `Int`.     bfs01,     trackingBfs01,      -- ** Dijkstra's algorithm -    -- *** Constraints--    -- | - Edge weight \(w > 0\)+    -- | Constraints:+    --+    -- - Edge weight \(w > 0\)     dijkstra,     trackingDijkstra, @@ -62,7 +64,11 @@     bellmanFord,     trackingBellmanFord, -    -- ** Floyd–Warshall algorithm (all-pair shortest path)+    -- ** Floyd–Warshall algorithm++    --++    -- | All-pair shortest path.     floydWarshall,     trackingFloydWarshall, @@ -74,16 +80,17 @@      -- ** Path reconstruction +    -- TODO: panic instead of infinite loop?+     -- *** Single source point (root) -    -- | Functions for retrieving a path from a predecessor array where @-1@ represents none.+    -- | Functions for retrieving a path from a predecessor array, where @-1@ represents none.     constructPathFromRoot,     constructPathToRoot,      -- *** All-pair -    -- | Functions for retrieving a path from a predecessor matrix \(m\), which is accessed as-    -- @m VG.! (n * from + to)@, where @-1@ represents none.+    -- | Functions for retrieving a path from a predecessor matrix \(m\).     constructPathFromRootMat,     constructPathToRootMat,     constructPathFromRootMatM,@@ -233,7 +240,7 @@ -- graph. -- -- ==== Constraints--- - The graph must be a DAG; no cycle can exist.+-- - The graph must be a DAG; there must be no cycle. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -245,7 +252,13 @@ -- -- @since 1.1.0.0 {-# INLINEABLE topSort #-}-topSort :: Int -> (Int -> VU.Vector Int) -> VU.Vector Int+topSort ::+  -- | \(n\): The number of vertices.+  Int ->+  -- | \(g\): Graph function, typically @'adj' gr@.+  (Int -> VU.Vector Int) ->+  -- | Vertices in topological ordering: upstream vertices come first.+  VU.Vector Int topSort n gr = runST $ do   inDeg <- VUM.replicate n (0 :: Int)   for_ [0 .. n - 1] $ \u -> do@@ -277,7 +290,7 @@ -- | \(O(n)\) Returns connected components for a non-directed graph. -- -- ==== Constraints--- - The graph must be non-directed.+-- - The graph must be non-directed: both \((u, v)\) and \((v, u)\) edges must exist. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -292,7 +305,13 @@ -- -- @since 1.2.4.0 {-# INLINEABLE connectedComponents #-}-connectedComponents :: Int -> (Int -> VU.Vector Int) -> V.Vector (VU.Vector Int)+connectedComponents ::+  -- | \(n\): The number of vertices.+  Int ->+  -- | \(g\): Graph function, typically @'adj' gr@.+  (Int -> VU.Vector Int) ->+  -- | Connected components.+  V.Vector (VU.Vector Int) connectedComponents n gr = runST $ do   buf <- B.new @_ @Int n   len <- B.new @_ @Int n@@ -340,7 +359,13 @@ -- -- @since 1.2.4.0 {-# INLINEABLE bipartiteVertexColors #-}-bipartiteVertexColors :: Int -> (Int -> VU.Vector Int) -> Maybe (VU.Vector Bit)+bipartiteVertexColors ::+  -- | \(n\): The number of vertices.+  Int ->+  -- | \(g\): Graph function, typically @'adj' gr@.+  (Int -> VU.Vector Int) ->+  -- | Bipartite vertex coloring.+  Maybe (VU.Vector Bit) bipartiteVertexColors n gr = runST $ do   (!isBipartite, !color, !_) <- bipartiteVertexColorsImpl n gr   if isBipartite@@ -388,7 +413,7 @@       b <- isCompatible 0       pure (b, color', dsu) --- | \(O(n + m)\) Returns a [block cut tree](https://en.wikipedia.org/wiki/Biconnected_component)+-- | \(O(n + m)\) Returns a [block-cut tree](https://en.wikipedia.org/wiki/Biconnected_component) -- where super vertices \((v \ge n)\) represent each biconnected component. -- -- ==== __Example__@@ -407,7 +432,14 @@ -- -- @since 1.1.1.0 {-# INLINEABLE blockCut #-}-blockCut :: Int -> (Int -> VU.Vector Int) -> Csr ()+blockCut ::+  -- | \(n\): The number of vertices.+  Int ->+  -- | \(g\): Graph function, typically @'adj' gr@.+  (Int -> VU.Vector Int) ->+  -- | Graph that represents a block-cut tree, where super vertices \((n \ge n)\) represent each+  -- biconnected component.+  Csr () blockCut n gr = runST $ do   low <- VUM.replicate n (0 :: Int)   ord <- VUM.replicate n (0 :: Int)@@ -492,7 +524,13 @@ -- -- @since 1.1.1.0 {-# INLINEABLE blockCutComponents #-}-blockCutComponents :: Int -> (Int -> VU.Vector Int) -> V.Vector (VU.Vector Int)+blockCutComponents ::+  -- | \(n\): The number of vertices.+  Int ->+  -- | \(g\): Graph function, typically @'adj' gr@.+  (Int -> VU.Vector Int) ->+  -- | Block-cut components+  V.Vector (VU.Vector Int) blockCutComponents n gr =   let bct = blockCut n gr       d = nCsr bct - n@@ -504,7 +542,7 @@  -- The implementations can be a bit simpler with `whenJustM` --- | \(O(n + m)\) Opinionated breadth-first search that returns a distance array.+-- | \(O(n + m)\) Opinionated breadth-first search function that returns a distance array. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -534,8 +572,8 @@   let (!dist, !_) = bfsImpl False bnd0 gr undefW sources    in dist --- | \(O(n + m)\) Opinionated breadth-first search that returns a distance array and a predecessor--- array.+-- | \(O(n + m)\) Opinionated breadth-first search function that returns a distance array and a+-- predecessor array. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -812,7 +850,7 @@   Int ->   -- | Distance assignment for unreachable vertices.   w ->-  -- | Source vertices with weights.+  -- | Source vertices with initial weights.   VU.Vector (i, w) ->   -- | A tuple of (distance array in one-dimensional index, predecessor array).   (VU.Vector w, VU.Vector Int)@@ -998,10 +1036,12 @@    runLoop 0 --- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\), which should be--- accessed as @m VU.! (`index0` (n, n) (from, to))@. Negative loop can be detected by testing if--- there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@.+-- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\). --+-- - The distance matrix should be accessed as @m VG.! (`index0` (n, n) (from, to))@,+-- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@+-- is negative.+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1034,7 +1074,7 @@   Int ->   -- | Weighted edges.   VU.Vector (Int, Int, w) ->-  -- | Distance assignment \(d_0 \gt 0\) for unreachable vertices. It should be @maxBound `div` 2@+  -- | Distance assignment \(d_0 \gt 0\) for unreachable vertices. It should be @maxBound \`div` 2@   -- for `Int`.   w ->   -- | Distance array in one-dimensional index.@@ -1044,10 +1084,13 @@   pure dist  -- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\) and predecessor--- matrix \(p\). The distance matrix should be accessed as @m VU.! (`index0` (n, n) (from, to))@,--- and the predecessor matrix should be accessed as @m VU.! (`index0` (n, n) (root, v))@. There's a--- negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@.+-- matrix \(p\). --+-- - The distance matrix should be accessed as @m VG.! (`index0` (n, n) (from, to))@,+-- - The predecessor matrix should be accessed as @m VG.! (`index0` (n, n) (root, v))@+-- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@+-- is negative.+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1086,7 +1129,7 @@   Int ->   -- | Weighted edges.   VU.Vector (Int, Int, w) ->-  -- | Distance assignment \(d_0 \gt 0\) for unreachable vertices. It should be @maxBound `div` 2@+  -- | Distance assignment \(d_0 \gt 0\) for unreachable vertices. It should be @maxBound \`div` 2@   -- for `Int`.   w ->   -- | Distance array in one-dimensional index.@@ -1095,10 +1138,12 @@   (!dist, !prev) <- newFloydWarshallST True nVerts edges undefW   (,) <$> VU.unsafeFreeze dist <*> VU.unsafeFreeze prev --- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\), which should be--- accessed as @m VU.! (n * from + to)@. There's a negative cycle if any @m VU.! (n * i + i)@ is--- negative.+-- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\). --+-- - The distance matrix should be accessed as @m VG.! (`index0` (n, n) (from, to))@,+-- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@+-- is negative.+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1130,8 +1175,13 @@   pure dist  -- | \(O(n^3)\) Floyd–Warshall algorithm that returns a distance matrix \(m\) and predecessor--- matrix. There's a negative cycle if any @m VU.! (n * i + i)@ is negative.+-- matrix. --+-- - The distance matrix should be accessed as @m VG.! (`index0` (n, n) (from, to))@,+-- - The predecessor matrix should be accessed as @m VG.! (`index0` (n, n) (root, v))@+-- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@+-- is negative.+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1217,8 +1267,7 @@   where     idx !from !to = nVerts * from + to --- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight decreasement or new edge--- addition.+-- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight change or new edge addition. -- -- @since 1.2.4.0 {-# INLINE updateEdgeFloydWarshall #-}@@ -1244,8 +1293,7 @@   prev <- VUM.replicate @_ @Int 0 (-1 :: Int)   stToPrim $ updateEdgeFloydWarshallST False mat prev nVerts undefW a b w --- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight decreasement or new edge--- addition.+-- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight chaneg or new edge addition. -- -- @since 1.2.4.0 {-# INLINE updateEdgeTrackingFloydWarshall #-}
src/AtCoder/Extra/HashMap.hs view
@@ -4,11 +4,12 @@ -- <https://github.com/maspypy/library/blob/main/ds/hashmap.hpp>  -- | A dense, fast `Int` hash map with a fixed-sized `capacity` of \(n\). Most operations are--- performed in \(O(1)\) time, but in average.+-- performed in \(O(1)\) average. -- -- ==== Capacity limitation -- Access to each key creates a new entry. Note that entries cannot be invalidated due to the--- internal implementation (called /open addressing/).+-- internal implementation (called /open addressing/). Be sure to specify large enough capacity+-- on `new`. -- -- ==== __Example__ -- Create a `HashMap` with `capacity` \(10\):@@ -16,7 +17,7 @@ -- >>> import AtCoder.Extra.HashMap qualified as HM -- >>> hm <- HM.new @_ @Int 10 ----- `insert`, `lookup` and other functions are available in \(O(1)\) averaged time:+-- `insert`, `lookup` and other functions are available in \(O(1)\) in averaged: -- -- >>> HM.insert hm 0 100 -- >>> HM.insert hm 10 101
src/AtCoder/Extra/IntMap.hs view
@@ -9,7 +9,7 @@ -- >>> import AtCoder.Extra.IntMap qualified as IM -- >>> im <- IM.new @_ @Int 10 ----- `insert`, `delete`, `lookup` and other functions are available:+-- `insert`, `delete`, `lookup`, `lookupGT` and other functions are available: -- -- >>> IM.insert im 0 100 -- >>> IM.insert im 9 101@@ -106,7 +106,7 @@ new :: (PrimMonad m, VU.Unbox a) => Int -> m (IntMap (PrimState m) a) new cap = stToPrim $ newST cap --- | \(O(n + m \log n)\) Creates an `IntMap` for an interval \([0, n)\) with initial values.+-- | \(O(n + m \log n)\) Creates an `IntMap` for an interval \([0, n)\) with initial entries. -- -- @since 1.1.0.0 {-# INLINEABLE build #-}@@ -120,7 +120,7 @@ capacity :: IntMap s a -> Int capacity = IS.capacity . setIM --- | \(O(1)\) Returns the number of elements in the map.+-- | \(O(1)\) Returns the number of entries in the map. -- -- @since 1.1.0.0 {-# INLINEABLE size #-}@@ -134,7 +134,7 @@ null :: (PrimMonad m) => IntMap (PrimState m) a -> m Bool null = IS.null . setIM --- | \(O(\log n)\) Looks up the value for a key.+-- | \(O(\log n)\) Looks up the value associated with a key. -- -- @since 1.1.0.0 {-# INLINEABLE lookup #-}@@ -214,7 +214,7 @@ insertWith im f k v = stToPrim $ insertWithST im f k v  -- | \(O(\log n)\) Modifies the value associated with a key. If an entry with the same key already--- does not exist, nothing is performed.+-- does not exist, it does nothing. -- -- @since 1.1.0.0 {-# INLINEABLE modify #-}@@ -222,7 +222,7 @@ modify im f k = stToPrim $ modifyST im f k  -- | \(O(\log n)\) Modifies the value associated with a key. If an entry with the same key already--- does not exist, nothing is performed.+-- does not exist, it does nothing. -- -- @since 1.1.0.0 {-# INLINEABLE modifyM #-}
src/AtCoder/Extra/IntSet.hs view
@@ -11,7 +11,7 @@ -- >>> import AtCoder.Extra.IntSet qualified as IS -- >>> is <- IS.new @_ 10 ----- `insert`, `delete` and other functions are available:+-- `insert`, `delete`, `member`, `lookupGT` and other functions are available: -- -- >>> IS.insert is 0 -- >>> IS.insert is 9
src/AtCoder/Extra/IntervalMap.hs view
@@ -167,15 +167,14 @@ size :: (PrimMonad m) => IntervalMap (PrimState m) a -> m Int size = IM.size . unITM --- | \(O(\log n)\) Returns whether a point \(x\) is contained within any of the intervals.+-- | \(O(\log n)\) Returns whether any of the intervals contain a point \(x\). -- -- @since 1.1.0.0 {-# INLINE contains #-} contains :: (PrimMonad m, VU.Unbox a) => IntervalMap (PrimState m) a -> Int -> m Bool contains itm i = stToPrim $ containsIntervalST itm i (i + 1) --- | \(O(\log n)\) Returns whether an interval \([l, r)\) is fully contained within any of the--- intervals.+-- | \(O(\log n)\) Returns whether any of the intervals fully contain an interval \([l, r)\). -- -- @since 1.1.0.0 {-# INLINE containsInterval #-}@@ -425,14 +424,14 @@               -- IM.delete_ dim l'               stToPrim $ IM.insert dim l' (l, x') --- | \(O(\log n)\) Shorthand for overwriting the value of an interval that contains \([l, r)\).+-- | \(O(\log n)\) Shorthand for overwriting the value of an interval that fully contains \([l, r)\). -- -- @since 1.1.0.0 {-# INLINE overwrite #-} overwrite :: (PrimMonad m, Eq a, VU.Unbox a) => IntervalMap (PrimState m) a -> Int -> Int -> a -> m () overwrite itm l r x = stToPrim $ overwriteST itm l r x --- | \(O(\log n)\). Shorthand for overwriting the value of an interval that contains \([l, r)\).+-- | \(O(\log n)\). Shorthand for overwriting the value of an interval that fully contains \([l, r)\). -- Tracks interval state changes via @onAdd@ and @onDel@ hooks. -- -- @since 1.1.0.0@@ -458,8 +457,8 @@     Just (!l', !r', !_) -> insertM itm l' r' x onAdd onDel     Nothing -> pure () --- | \(O(n \log n)\) Enumerates the intervals and the associated values as \((l, (r, x))\) tuples,--- where \([l, r)\) is the interval and \(x\) is the associated value.+-- | \(O(n \log n)\) Enumerates the intervals and the associated values as \((l, (r, v))\) tuples,+-- where \([l, r)\) is the interval and \(v\) is the associated value. -- -- @since 1.1.0.0 {-# INLINE freeze #-}
src/AtCoder/Extra/Ix0.hs view
@@ -1,15 +1,17 @@ {-# LANGUAGE TypeFamilies #-} --- | Opinionated zero-based multidimensional index and their boundaries.+-- | Opinionated zero-based \(n\)-dimensional index and their bounds. module AtCoder.Extra.Ix0 where +-- | Zero-based \(n\)-dimensional bounds: \([0, d_0) \times [0, d_1) \times .. \times [0, d_{n - 1})\). type Bounds0 i = i +-- | Zero-based \(n\)-dimensional index. class Ix0 i where-  -- | Returns the size of the boundary.+  -- | Returns the size of the bounds: \(\Pi_i d_i\).   rangeSize0 :: Bounds0 i -> Int -  -- | Returns zero-based index, **without** running boundary check.+  -- | Returns zero-based one dimensional index, __without__ running boundary check.   index0 :: Bounds0 i -> i -> Int    -- | Returns whether an index is contained in a bounds.
src/AtCoder/Extra/KdTree.hs view
@@ -2,7 +2,7 @@  -- | Static, \(k\)-dimensional tree \((k = 2)\). ----- - Points are fixed on `build`.+-- - Points are fixed on `build` and cannot be moved or added later. -- - Multiple points can exist at the same coordinate. -- -- ==== __Examples__@@ -137,9 +137,6 @@  -- | \(O(n \log n)\) Creates `KdTree` from a \((x, y)\) vector. ----- ==== Constraints--- - \(|\mathrm{xs}| = |\mathrm{ys}|\).--- -- @since 1.2.2.0 {-# INLINE build2 #-} build2 ::@@ -209,7 +206,7 @@   Int ->   -- | \(y\)   Int ->-  -- | The nearest point index+  -- | The nearest point index.   Maybe Int findNearestPoint KdTree {..} x y   | nKt == 0 = Nothing
src/AtCoder/Extra/LazyKdTree.hs view
@@ -1,9 +1,9 @@ {-# LANGUAGE RecordWildCards #-}  -- | Static, \(k\)-dimensional tree \((k = 2)\) with lazily propagated monoid actions and--- commutative monoids.+-- commutative acted monoids. ----- - Point coordinates are fixed on `build`.+-- - Point coordinates are fixed on `build` and cannot be moved or added later. -- - Multiple points can exist at the same coordinate. -- -- ==== __Examples__@@ -110,17 +110,17 @@ -- | \(O(n \log n)\) Creates a `LazyKdTree` from @xs@ and @ys@. -- -- ==== Constraints--- - \(|\mathrm{xs}| = |\mathrm{ys}|+-- - \(|\mathrm{xs}| = |\mathrm{ys}|\) -- -- @since 1.2.3.0 {-# INLINE new #-} new ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | \(x\) coordnates+  -- | \(x\) coordnates.   VU.Vector Int ->-  -- | \(y\) coordnates+  -- | \(y\) coordnates.   VU.Vector Int ->-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   m (LazyKdTree (PrimState m) f a) new xs ys = stToPrim $ buildST xs ys (VU.replicate (VU.length xs) mempty) @@ -133,13 +133,13 @@ {-# INLINE build #-} build ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | \(x\) coordnates+  -- | \(x\) coordnates.   VU.Vector Int ->-  -- | \(y\) coordnates+  -- | \(y\) coordnates.   VU.Vector Int ->-  -- | monoid \(v\)alues+  -- | monoid \(v\)alues.   VU.Vector a ->-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   m (LazyKdTree (PrimState m) f a) build xs ys vs = stToPrim $ buildST xs ys vs @@ -152,11 +152,11 @@ {-# INLINE build2 #-} build2 ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | \((x, y)\) coordinates+  -- | \((x, y)\) coordinates.   VU.Vector (Int, Int) ->-  -- | Monoid \(v\)alues+  -- | Monoid \(v\)alues.   VU.Vector a ->-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   m (LazyKdTree (PrimState m) f a) build2 xys ws = stToPrim $ buildST xs ys ws   where@@ -168,9 +168,9 @@ {-# INLINE build3 #-} build3 ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | \((x, y, v)\) tuples+  -- | \((x, y, v)\) tuples.   VU.Vector (Int, Int, a) ->-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   m (LazyKdTree (PrimState m) f a) build3 xyws = stToPrim $ buildST xs ys ws   where@@ -182,45 +182,45 @@ {-# INLINE write #-} write ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   LazyKdTree (PrimState m) f a ->   -- | Original vertex index.   Int ->-  -- | Monoid value+  -- | Monoid value.   a ->-  -- | Monadic tuple+  -- | Monadic tuple.   m () write kt i x = stToPrim $ modifyM kt (pure . const x) i --- | \(O(\log n)\) Modifies the \(k\)-th point's monoid value.+-- | \(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th point's monoid value with it. -- -- @since 1.2.2.0 {-# INLINE modify #-} modify ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   LazyKdTree (PrimState m) f a ->-  -- | Creates a new monoid value from the old one.+  -- | \(f\): Creates a new monoid value from the old one.   (a -> a) ->-  -- | Original vertex index.+  -- | \(k\): Original vertex index.   Int ->-  -- | Monadic tuple+  -- | Monadic tuple.   m () modify kt f i = stToPrim $ modifyM kt (pure . f) i --- | \(O(\log n)\) Modifies the \(k\)-th point's monoid value.+-- | \(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th point's monoid value with it. -- -- @since 1.2.2.0 {-# INLINEABLE modifyM #-} modifyM ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | `LazyKdTree`+  -- | `LazyKdTree`.   LazyKdTree (PrimState m) f a ->-  -- | Creates a new monoid value from the old one.+  -- | \(f\): Creates a new monoid value from the old one.   (a -> m a) ->-  -- | Original vertex index.+  -- | \(k\): Original vertex index.   Int ->-  -- | Monadic tuple+  -- | Monadic tuple.   m () modifyM kt@LazyKdTree {..} f i0 = do   let !_ = ACIA.checkIndex "AtCoder.Extra.LazyKdTree.modifyM" i0 nLkt@@ -274,7 +274,8 @@   -- In case of zero vertices, use `Maybe`:   fromMaybe mempty <$> VGM.readMaybe (dataLkt kt) 1 --- | \(O(\log n)\) Applies a monoid action to points in \([x_1, x_2) \times [y_1, y_2)\).+-- | \(O(\log n)\) Given a rectangle \([x_1, x_2) \times [y_1, y_2)\), applies a monoid action to+-- it. -- -- @since 1.2.2.0 {-# INLINE applyIn #-}@@ -292,7 +293,7 @@   Int ->   -- | \(f\)   f ->-  -- | Monadic tuple+  -- | Monadic tuple.   m () applyIn kt x1 x2 y1 y2 f = stToPrim $ applyInST kt 1 x1 x2 y1 y2 f
src/AtCoder/Extra/Math.hs view
@@ -333,11 +333,15 @@ -- TODO: use intro sort? divisors = VU.modify VAR.sort . divisorsUnsorted --- | Enumerates divisors of the input value.+-- | Enumerates divisors of the input value, not sorted. -- -- ==== Constraints -- - \(x \ge 1\) --+-- ==== __Example__+-- >>> divisorsUnsorted 180+-- [1,2,4,3,6,12,9,18,36,5,10,20,15,30,60,45,90,180]+-- -- @since 1.2.6.0 {-# INLINEABLE divisorsUnsorted #-} divisorsUnsorted :: (HasCallStack) => Int -> VU.Vector Int@@ -367,7 +371,7 @@     (!_, !ns) = VU.unzip pns     nDivisors = VU.foldl' (\ !acc n -> acc * (n + 1)) (1 :: Int) ns --- | Returns a primitive root of module \(p\), where \(p\) is a prime number.+-- | Returns a primitive root modulo \(p\), where \(p\) is a prime number. -- -- ==== Constraints -- - \(p\) must be a prime number.
src/AtCoder/Extra/Math/Montgomery64.hs view
@@ -1,9 +1,11 @@ {-# LANGUAGE MagicHash #-} {-# LANGUAGE NamedFieldPuns #-} --- | Fast modular multiplication for `Word64` using Montgomery multiplication. If the modulus value--- is known to fit in 32 bits, use the @AtCoder.Internal.Barrett@ module instead.+-- | Fast modular multiplication for `Word64` using Montgomery multiplication. --+-- - The modulus value must be odd.+-- - If the modulus value is known to fit in 32 bits, @AtCoder.Internal.Barrett@ can be faster.+-- -- @since 1.2.6.0 module AtCoder.Extra.Math.Montgomery64   ( -- * Montgomery64@@ -61,7 +63,7 @@ -- | \(O(1)\) Static, shared storage of `Montgomery64`. -- -- ==== Constraints--- - \(m \le 2^{62})+-- - \(m \le 2^{62}\) -- - \(m\) is odd -- -- @since 1.2.6.0@@ -73,7 +75,7 @@ -- | \(O(1)\) Creates a `Montgomery64` for a modulus value \(m\) of type `Word64` value. -- -- ==== Constraints--- - \(m \le 2^{62})+-- - \(m \le 2^{62}\) -- - \(m\) is odd -- -- @since 1.2.6.0
src/AtCoder/Extra/ModInt64.hs view
@@ -6,7 +6,7 @@ -- | @ModInt@ for 64 bit modulus values with Montgomery modular multiplication. -- -- ==== Constraints--- - The modulus value should be an odd number, otherwise it would be too slow.+-- - The modulus value must be an odd number. -- -- @since 1.2.6.0 module AtCoder.Extra.ModInt64@@ -53,7 +53,7 @@ -- | `Word64` value that treats the modular arithmetic. -- -- ==== Constraints--- - The modulus value should be an odd number, otherwise it would be too slow.+-- - The modulus value must be an odd number. -- -- @since 1.2.6.0 newtype ModInt64 a = ModInt64@@ -140,7 +140,7 @@ val64 :: forall a. (KnownNat a) => ModInt64 a -> Word64 val64 (ModInt64 x) = M64.decode (M64.new (proxy# @a)) x --- | \(O(\log n\) Returns \(x^n\). The implementation is a bit more efficient than `^`.+-- | \(O(\log n)\) Returns \(x^n\). The implementation is a bit more efficient than `^`. -- -- ==== Constraints -- - \(0 \le n\)@@ -153,7 +153,7 @@ -- TODO: move invMod to Montgomery64 -- TODO: time complexity of `inv`? --- | Returns \(y\) such that \(xy \equiv 1\) holds.+-- | Returns \(y\) such that \(xy \equiv 1 \bmod m\) holds. -- -- ==== Constraints -- - The value must not be zero.
src/AtCoder/Extra/Monoid/Affine1.hs view
@@ -36,8 +36,7 @@  -- | Monoid action \(f: x \rightarrow ax + b\). ----- - Use @Mat2x2@ if inverse operations are required, or if it's necessary to store the monoid--- length in the acted monoid (@V2@).+-- - Use @Mat2x2@ if inverse operations are required. -- -- ==== Composition and dual -- The affine transformation acts as a left monoid action: \(f_2 (f_1 v) = (f_2 \circ f_1) v\). To
src/AtCoder/Extra/Monoid/Mat2x2.hs view
@@ -1,8 +1,8 @@ {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE TypeFamilies #-} --- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but compatible with--- inverse opereations.+-- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but is compatible+-- with inverse opereations. -- -- @since 1.1.0.0 module AtCoder.Extra.Monoid.Mat2x2@@ -37,8 +37,8 @@ import GHC.Stack (HasCallStack) import Prelude hiding (map) --- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but compatible with--- inverse opereations.+-- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but is compatible+-- with inverse opereations. -- -- ==== Composition and dual -- The affine transformation acts as a left monoid action: \(f_2 (f_1 v) = (f_2 \circ f_1) v\). To@@ -71,7 +71,7 @@ -- @since 1.1.0.0 type Mat2x2Repr a = (a, a, a, a) --- | \(O(1)\) Creates a one-dimensional affine transformation: \(f: x \rightarrow a \times x + b\).+-- | \(O(1)\) Creates a one-dimensional affine transformation \(f: x \rightarrow a \times x + b\). -- -- @since 1.1.0.0 {-# INLINE new #-}@@ -124,7 +124,7 @@ act :: (Num a) => Mat2x2 a -> V2 a -> V2 a act = mulMV --- | \(O(1)\) Maps the every component of `Mat2x2`.+-- | \(O(1)\) Maps every component of `Mat2x2`. -- -- @since 1.1.0.0 {-# INLINE map #-}
src/AtCoder/Extra/Monoid/RollingHash.hs view
@@ -56,8 +56,12 @@ -- @since 1.1.0.0 data RollingHash b p = RollingHash   { -- | The hash value.+    --+    -- @since 1.1.0.0     hashRH :: {-# UNPACK #-} !Int,     -- | \(b^{\mathrm{length}} \bmod p\).+    --+    -- @since 1.1.0.0     nextDigitRH :: {-# UNPACK #-} !Int   }   deriving
src/AtCoder/Extra/Monoid/V2.hs view
@@ -27,6 +27,18 @@  -- | A monoid acted on by `Mat2x2`, an affine transformation target. --+-- ==== __Example__+-- >>> import AtCoder.Extra.Monoid.Mat2x2 (Mat2x2(..))+-- >>> import AtCoder.Extra.Monoid.Mat2x2 qualified as Mat2x2+-- >>> import AtCoder.Extra.Monoid.V2 (V2(..))+-- >>> import AtCoder.Extra.Monoid.V2 qualified as V2+-- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import Data.Vector.Unboxed qualified as VU+-- >>> seg <- LST.build @_ @(Mat2x2 Int) @(V2 Int) . VU.map V2.new $ VU.fromList [1, 2, 3, 4]+-- >>> LST.applyIn seg 1 3 $ Mat2x2.new 2 1 -- [1, 5, 7, 4]+-- >>> V2.unV2 <$> LST.prod seg 1 3+-- 12+-- -- @since 1.1.0.0 newtype V2 a = V2 (V2Repr a)   deriving newtype
src/AtCoder/Extra/MultiSet.hs view
@@ -1,13 +1,13 @@ {-# LANGUAGE LambdaCase #-} {-# LANGUAGE RecordWildCards #-} --- | A fast, mutable multiset for `Int` keys backed by a @HashMap@.  Most operations are performed--- in \(O(1)\) time, but in average.+-- | A fast, mutable multiset for `Int` keys backed by a @HashMap@. Most operations are performed+-- in \(O(1)\) in average. -- -- ==== Capacity limitation -- Access to each key creates a new entry. Note that entries cannot be invalidated due to the -- internal implementation (called /open addressing/). If the hash map is full,--- __access to a new key causes infinite loop__ .+-- __access to a new key causes infinite loop__. -- -- ==== Invariant -- The count for each key must be non-negative. An exception is thrown if this invariant is
src/AtCoder/Extra/Pdsu.hs view
@@ -5,8 +5,8 @@  -- | A potentialized disjoint set union on a [group](https://en.wikipedia.org/wiki/Group_(mathematics\)) -- under a differential constraint system. Each vertex \(v\) is assigned a potential value \(p(v)\),--- where representatives (`leader`) of each group have a potential of `mempty`, and other vertices have--- potentials relative to their representative.+-- where representatives (`leader`) of each group have a potential value of `mempty`, and other+-- vertices have potentials relative to their representative. -- -- The group type is represented as a `Monoid` with a inverse operator, passed on `new`. This -- approach avoids defining a separate typeclass for groups.@@ -117,11 +117,11 @@ new ::   forall m a.   (PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | The number of vertices+  -- | The number of vertices.   Int ->-  -- | The inverse operator of the monoid+  -- | The inverse operator of the monoid.   (a -> a) ->-  -- | A DSU+  -- | A potencialized DSU.   m (Pdsu (PrimState m) a) new n f = Pdsu n <$> VUM.replicate n (-1 {- size 1 -}) <*> VUM.replicate n (mempty :: a) <*> pure f @@ -168,6 +168,8 @@ {-# INLINE unsafeDiff #-} unsafeDiff :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => Pdsu (PrimState m) a -> Int -> Int -> m a unsafeDiff dsu v1 v2 = stToPrim $ unsafeDiffST dsu v1 v2++-- TODO: use merge and mergeMaybe  -- | \(O(\alpha(n))\) Merges \(v_1\) to \(v_2\) with differential (relative) potential -- \(\mathrm{dp}\): \(p(v1) := \mathrm{dp} \cdot p(v2)\). Returns `True` if they're newly merged.
src/AtCoder/Extra/Pool.hs view
@@ -51,6 +51,8 @@ import Prelude hiding (read)  -- | Fixed-sized array for \(O(1)\) allocation and \(O(1)\) clearing after \(O(n)\) construction.+--+-- @since 1.2.0.0 data Pool s a = Pool   { -- | Data array.     dataPool :: !(VUM.MVector s a),@@ -61,46 +63,70 @@   }  -- | Strongly typed index of pool items. User has to explicitly @corece@ on raw index use.+--+-- @since 1.2.0.0 newtype Index = Index {unIndex :: Int}-  deriving (Eq, VP.Prim)+  deriving+    ( -- | @since 1.2.0.0+      Eq,+      -- | @since 1.2.0.0+      VP.Prim+    )   deriving newtype (Ord, Show) +-- | @since 1.2.0.0 newtype instance VU.MVector s Index = MV_Index (VP.MVector s Index) +-- | @since 1.2.0.0 newtype instance VU.Vector Index = V_Index (VP.Vector Index) +-- | @since 1.2.0.0 deriving via (VU.UnboxViaPrim Index) instance VGM.MVector VUM.MVector Index +-- | @since 1.2.0.0 deriving via (VU.UnboxViaPrim Index) instance VG.Vector VU.Vector Index +-- | @since 1.2.0.0 instance VU.Unbox Index  -- | Invalid, null `Index`.+--+-- @since 1.2.0.0 {-# INLINE undefIndex #-} undefIndex :: Index undefIndex = Index (-1)  -- | Returns `True` for `undefIndex`.+--+-- @since 1.2.0.0 {-# INLINE nullIndex #-} nullIndex :: Index -> Bool nullIndex = (== undefIndex)  -- | \(O(n)\) Creates a pool with the specified @capacity@.+--+-- @since 1.2.0.0 {-# INLINE new #-} new :: (VU.Unbox a, PrimMonad m) => Int -> m (Pool (PrimState m) a) new cap = stToPrim $ newST cap  -- | \(O(1)\) Resets the pool to the initial state.+--+-- @since 1.2.0.0 {-# INLINE clear #-} clear :: (PrimMonad m) => Pool (PrimState m) a -> m () clear pool = stToPrim $ clearST pool  -- | \(O(1)\) Returns the maximum number of elements the pool can store.+--+-- @since 1.2.0.0 {-# INLINE capacity #-} capacity :: (VU.Unbox a) => Pool s a -> Int capacity = VGM.length . dataPool  -- | \(O(1)\) Returns the number of elements in the pool.+--+-- @since 1.2.0.0 {-# INLINE size #-} size :: (PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> m Int size pool = stToPrim $ sizeST pool@@ -109,6 +135,8 @@ -- -- ==== Constraints -- - The number of elements must not exceed the `capacity`.+--+-- @since 1.2.0.0 {-# INLINE alloc #-} alloc :: (HasCallStack, PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> a -> m Index alloc pool x = stToPrim $ allocST pool x@@ -117,6 +145,8 @@ -- -- ==== Constraints -- - \(0 \le i \lt n\)+--+-- @since 1.2.0.0 {-# INLINE free #-} free :: (PrimMonad m) => Pool (PrimState m) a -> Index -> m () free Pool {..} i = do@@ -126,6 +156,8 @@ -- -- ==== Constraints -- - \(0 \le i \lt n\)+--+-- @since 1.2.0.0 {-# INLINE read #-} read :: (PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> Index -> m a read Pool {dataPool} !i = do@@ -134,16 +166,20 @@ -- | \(O(1)\) Writes to the \(k\)-th value. -- -- ==== Constraints+--+-- @since 1.2.0.0 -- - \(0 \le i \lt n\) {-# INLINE write #-} write :: (PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> Index -> a -> m () write Pool {dataPool} !i !x = do   VGM.write dataPool (coerce i) x --- | \(O(1)\) Modifies the \(k\)-th value.+-- | \(O(1)\) Given a user function \(f\), modifies the \(k\)-th value with it. -- -- ==== Constraints -- - \(0 \le i \lt n\)+--+-- @since 1.2.0.0 {-# INLINE modify #-} modify :: (PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> (a -> a) -> Index -> m () modify Pool {dataPool} !f !i = do@@ -153,6 +189,8 @@ -- -- ==== Constraints -- - \(0 \le i \lt n\)+--+-- @since 1.2.0.0 {-# INLINE exchange #-} exchange :: (PrimMonad m, VU.Unbox a) => Pool (PrimState m) a -> Index -> a -> m a exchange Pool {dataPool} !i !x = do@@ -166,21 +204,21 @@     unHandle :: VUM.MVector s Index   } --- | \(O(1)\) Creates a new sequence `Handle` from a root node index.+-- | \(O(1)\) Creates a new `Handle` from a root node index. -- -- @since 1.2.0.0 {-# INLINE newHandle #-} newHandle :: (PrimMonad m) => Index -> m (Handle (PrimState m)) newHandle x = Handle <$> VUM.replicate 1 x --- | \(O(1)\) Returns whether the sequence is empty.+-- | \(O(1)\) Returns whether the handle represents null. -- -- @since 1.2.0.0 {-# INLINE nullHandle #-} nullHandle :: (PrimMonad m) => Handle (PrimState m) -> m Bool nullHandle (Handle h) = nullIndex <$> VGM.unsafeRead h 0 --- | \(O(1)\) Invalidates a sequence handle. Note that it does not change or `free` the sequence.+-- | \(O(1)\) Invalidates a handle. Note that it does not change or `free` the pool item. -- -- @since 1.2.0.0 {-# INLINE invalidateHandle #-}
src/AtCoder/Extra/SegTree2d.hs view
@@ -195,43 +195,45 @@ {-# INLINE write #-} write ::   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | Two-dimensional segment tree+  -- | Two-dimensional segment tree.   SegTree2d (PrimState m) a ->-  -- | Original point index+  -- | Original point index.   Int ->-  -- | New monoid value+  -- | New monoid value.   a ->   m () write seg i x = stToPrim $ do   modifyM seg (pure . const x) i --- | \(O(\log n)\) Given \(f\), modofies the \(k\)-th original point's monoid value.+-- | \(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th original point's monoid value+-- with it. -- -- @since 1.2.3.0 {-# INLINE modify #-} modify ::   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | Two-dimensional segment tree+  -- | Two-dimensional segment tree.   SegTree2d (PrimState m) a ->-  -- | Function that alters the monoid value+  -- | Function that alters the monoid value.   (a -> a) ->-  -- | Original point index+  -- | Original point index.   Int ->   m () modify seg f i = stToPrim $ do   modifyM seg (pure . f) i --- | \(O(\log n)\) Given \(f\), modofies the \(k\)-th original point's monoid value.+-- | \(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th original point's monoid value+-- with it. -- -- @since 1.2.3.0 {-# INLINEABLE modifyM #-} modifyM ::   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | Two-dimensional segment tree+  -- | Two-dimensional segment tree.   SegTree2d (PrimState m) a ->-  -- | Function that alters the monoid value+  -- | Function that alters the monoid value.   (a -> m a) ->-  -- | Original point index+  -- | Original point index.   Int ->   m () modifyM seg@SegTree2d {..} f rawIdx = do@@ -260,7 +262,7 @@ {-# INLINE prod #-} prod ::   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | Two-dimensional segment tree+  -- | Two-dimensional segment tree.   SegTree2d (PrimState m) a ->   -- | \(x_1\)   Int ->@@ -287,7 +289,7 @@ {-# INLINE count #-} count ::   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>-  -- | Two-dimensional segment tree+  -- | Two-dimensional segment tree.   SegTree2d (PrimState m) a ->   -- | \(x_1\)   Int ->@@ -297,7 +299,7 @@   Int ->   -- | \(y_2\)   Int ->-  -- | The number of points in \([x_1, x_2) \times [y_1, y_2)\)+  -- | The number of points in \([x_1, x_2) \times [y_1, y_2)\).   m Int count seg lx rx ly ry = stToPrim $ countST seg lx rx ly ry
src/AtCoder/Extra/SegTree2d/Dense.hs view
@@ -187,7 +187,8 @@ write seg@DenseSegTree2d {..} x y a = stToPrim $ do   modifyM seg (pure . const a) x y --- | \(O(\log  h \log w)\) Given \(f\), modofies the monoid value at \((x, y)\).+-- | \(O(\log  h \log w)\) Given a user function \(f\), modifies the monoid value at \((x, y)\) with+-- it. -- -- @since 1.2.3.0 {-# INLINE modify #-}@@ -195,7 +196,8 @@ modify seg f x y = stToPrim $ do   modifyM seg (pure . f) x y --- | \(O(\log h \log w)\) Given \(f\), modofies the monoid value at \((x, y)\).+-- | \(O(\log h \log w)\) Given a user function \(f\), modifies the monoid value at \((x, y)\) with+-- it. -- -- @since 1.2.3.0 {-# INLINEABLE modifyM #-}
src/AtCoder/Extra/Semigroup/Matrix.hs view
@@ -138,7 +138,7 @@   where     n = VU.length xs --- | \(O(n^2)\) Maps the `Matrix`.+-- | \(O(n^2)\) Maps the `Matrix` elements. -- -- @since 1.1.0.0 {-# INLINE map #-}
src/AtCoder/Extra/Semigroup/Permutation.hs view
@@ -49,7 +49,8 @@ -- -- @since 1.1.0.0 newtype Permutation = Permutation-  { unPermutation :: VU.Vector Int+  { -- | @since 1.1.0.0+    unPermutation :: VU.Vector Int   }   deriving newtype     ( -- | @since 1.1.0.0
src/AtCoder/Extra/Seq.hs view
@@ -397,7 +397,8 @@     )     0 --- | Amortized \(O(\log n)\). Modifies the \(k\)-th node's monoid value.+-- | Amortized \(O(\log n)\). Given a user function \(f\), modifies the \(k\)-th node's monoid value+-- with it. -- -- ==== Constraints -- - \(0 \le k \lt n\)
src/AtCoder/Extra/Seq/Map.hs view
@@ -15,11 +15,15 @@ -- >>> import Data.Semigroup (Sum (..)) -- >>> import Data.Vector.Unboxed qualified as VU -- >>> m <- M.new @_ @(RangeAdd.RangeAdd (Sum Int)) @Int @(Sum Int) 10--- >>> M.insert m 1 10--- >>> M.insert m 3 30+-- >>> M.insert m 1 10 -- [- 10 - - -]+-- >>> M.insert m 3 30 -- [- 10 - 30 -] -- >>> M.prod m 1 2 -- Sum {getSum = 10} --+-- >>> M.applyIn m 1 4 $ RangeAdd.new 7 -- [-  17 - 37 -]+-- >>> M.prod m 1 4+-- Sum {getSum = 54}+-- -- @since 1.2.1.0 module AtCoder.Extra.Seq.Map   ( -- * Map@@ -115,11 +119,11 @@ -- -- @since 1.2.1.0 data Map s f k v = Map-  { -- | The sequence storage+  { -- | The sequence storage.     --     -- @since 1.2.1.0     seqMap :: !(Seq.Seq s f v),-    -- | Keys+    -- | Keys.     --     -- @since 1.2.1.0     kMap :: !(VUM.MVector s k),@@ -136,7 +140,8 @@   let !_ = ACIA.runtimeAssert (P.nullIndex p) $ "AtCoder.Extra.Seq.Map.assertRootST: not a root (node `" ++ show i ++ "`, parent `" ++ show p ++ "`)"   pure () --- | \(O(n)\) Creates a new `Map` of capacity \(n\). Always prefer `build` to `new` for performance.+-- | \(O(n)\) Creates a new `Map` of capacity \(n\). Always prefer `build` to `new` for better+-- performance. -- -- @since 1.2.1.0 {-# INLINEABLE new #-}@@ -148,7 +153,7 @@   pure Map {..}  -- | \(O(n \log n)\) Creates a new `Map` of capacity \(n\) with initial values. Always prefer `build` to--- `new` for performance.+-- `new` for better performance. -- -- @since 1.2.1.0 {-# INLINEABLE build #-}@@ -265,13 +270,13 @@ {-# INLINE insertWith #-} insertWith ::   (HasCallStack, PrimMonad m, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) =>-  -- | Map+  -- | Map.   Map (PrimState m) f k v ->-  -- | new -> old -> combined+  -- | new -> old -> combined.   (v -> v -> v) ->-  -- | Key+  -- | Key.   k ->-  -- | Value+  -- | Value.   v ->   m () insertWith m f k v = stToPrim $ do@@ -281,13 +286,13 @@ {-# INLINEABLE insertWithST #-} insertWithST ::   (HasCallStack, Eq f, Monoid f, VU.Unbox f, Ord k, VU.Unbox k, Monoid v, VU.Unbox v, SegAct f v) =>-  -- | Map+  -- | Map.   Map s f k v ->-  -- | new -> old -> combined+  -- | new -> old -> combined.   (v -> v -> v) ->-  -- | Key+  -- | Key.   k ->-  -- | Value+  -- | Value.   v ->   ST s () insertWithST Map {..} f k v = stToPrim $ do@@ -472,7 +477,7 @@ -- -- ==== Constraints -- - \(0 \le l \le r \le n\)--- - The root must point to a non-empty sequence.+-- - The root must point a non-empty sequence. -- -- @since 1.2.1.0 {-# INLINEABLE applyIn #-}@@ -486,7 +491,7 @@       Raw.splayST seqMap target True       VGM.write (Seq.unHandle rootMap) 0 target --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Applies a monoid action \(f\) to every element. -- -- @since 1.2.1.0 {-# INLINE applyAll #-}@@ -596,7 +601,7 @@ -- Index-based operations -- ------------------------------------------------------------------------------------------- --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value. -- -- @since 1.2.1.0 {-# INLINE readAt #-}@@ -604,7 +609,7 @@ readAt Map {..} i = stToPrim $ do   Seq.read seqMap rootMap i --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value. -- -- @since 1.2.1.0 {-# INLINE readMaybeAt #-}@@ -612,7 +617,7 @@ readMaybeAt Map {..} i = stToPrim $ do   Seq.readMaybe seqMap rootMap i --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Writes to the \(k\)-th node's monoid value. -- -- @since 1.2.1.0 {-# INLINE writeAt #-}@@ -620,7 +625,8 @@ writeAt Map {..} i v = stToPrim $ do   Seq.write seqMap rootMap i v --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Given a user function \(f\), modifies the \(k\)-th node's monoid value+-- with it. -- -- @since 1.2.1.0 {-# INLINE modifyAt #-}@@ -628,7 +634,7 @@ modifyAt Map {..} f i = stToPrim $ do   Seq.modify seqMap rootMap f i --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Exchanges the \(k\)-th node's monoid value. -- -- @since 1.2.1.0 {-# INLINE exchangeAt #-}@@ -636,7 +642,7 @@ exchangeAt Map {..} i v = stToPrim $ do   Seq.exchange seqMap rootMap i v --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\). -- -- @since 1.2.1.0 {-# INLINE prodInInterval #-}@@ -644,7 +650,7 @@ prodInInterval Map {..} l r = stToPrim $ do   Seq.prod seqMap rootMap l r --- | Amortized \(O(\log n)\).+-- | Amortized \(O(\log n)\). Given an interval \([l, r)\), applies a monoid action \(f\) to it. -- -- @since 1.2.1.0 {-# INLINE applyInInterval #-}@@ -658,11 +664,11 @@ {-# INLINE ilowerBound #-} ilowerBound ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | Map+  -- | Map.   Map (PrimState m) f k a ->-  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value+  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value.   (Int -> a -> Bool) ->-  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)+  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\).   m Int ilowerBound Map {..} f = stToPrim $ do   Seq.ilowerBound seqMap rootMap f@@ -673,11 +679,11 @@ {-# INLINE ilowerBoundM #-} ilowerBoundM ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | Map+  -- | Map.   Map (PrimState m) f k a ->-  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value+  -- | User predicate \(f(i, v_i)\) that takes the index and the monoid value.   (Int -> a -> m Bool) ->-  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)+  -- | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\).   m Int ilowerBoundM Map {..} f = do   Seq.ilowerBoundM seqMap rootMap f@@ -688,11 +694,11 @@ {-# INLINE ilowerBoundProd #-} ilowerBoundProd ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | Map+  -- | Map.   Map (PrimState m) f k a ->-  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product+  -- | User predicate \(f(i, \Pi_{0 \le j \le i} v_j)\) that takes the index and the monoid product.   (Int -> a -> Bool) ->-  -- | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)+  -- | Maximum \(r\), where \(f(i, \Pi_{0 \le j \le i} v_j)\) holds for \(i \in [0, r)\).   m Int ilowerBoundProd Map {..} f = stToPrim $ do   Seq.ilowerBoundProd seqMap rootMap f@@ -703,11 +709,11 @@ {-# INLINE ilowerBoundProdM #-} ilowerBoundProdM ::   (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | Map+  -- | Map.   Map (PrimState m) f k a ->-  -- | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product+  -- | User predicate \(f(i, \Pi_{0 \le j \le i} v_j)\) that takes the index and the monoid product.   (Int -> a -> m Bool) ->-  -- | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)+  -- | Maximum \(r\), where \(f(i, \Pi_{0 \le j \le i} v_j)\) holds for \(i \in [0, r)\).   m Int ilowerBoundProdM Map {..} f = do   Seq.ilowerBoundProdM seqMap rootMap f@@ -716,7 +722,7 @@ -- Conversions -- ------------------------------------------------------------------------------------------- --- | \(O(n)\) Returns the \(k, v\) pairs in the map+-- | \(O(n)\) Returns the \(k, v\) pairs in the map. -- -- @since 1.2.1.0 {-# INLINEABLE freeze #-}
src/AtCoder/Extra/SqrtDecomposition.hs view
@@ -11,8 +11,8 @@ -- ==== Lazy propagation -- Typically, an action to a whole block can be delayed; store the aggregation value for the block, -- delay the internal sequence update, and restore them when part of the block is accessed. Such--- lazy propagation should be handled on the user side on partial block access functions--- (@foldPart@ or @actPart@) are called.+-- lazy propagation should be handled on the user side in partial block access functions (@foldPart@+-- or @actPart@). -- -- @since 1.2.5.0 module AtCoder.Extra.SqrtDecomposition@@ -33,14 +33,19 @@ -- INLINE all the functions, even if the performance gain is just a little bit, in case it matters.  -- | \(O(\sqrt n)\) Runs user function for each block.+--+-- ==== Constraints+-- - \(l \le r\)+--+-- @since 1.2.5.0 {-# INLINE forM_ #-} forM_ ::   (Monad m) =>   -- | Context: block length.   Int ->-  -- | Function: @actFull@ function that takes target block index.+  -- | Function: @actFull@ function that takes a target block index.   (Int -> m ()) ->-  -- | Function: @actPart@ function that takes target block index, left index and right index.+  -- | Function: @actPart@ function that takes a target block index and a half-open interval in it.   (Int -> Int -> Int -> m ()) ->   -- | Input: \(l\).   Int ->@@ -69,7 +74,7 @@ -- -- ==== Constraints -- - \(l \le r\)--- - If an empty interval is queried, the @readPart@ function must return a valid value.+-- - The @readPart@ function must return a valid value for an empty interval. -- -- @since 1.2.5.0 {-# INLINE foldMapM #-}@@ -77,10 +82,11 @@   (Monad m, Semigroup a) =>   -- | Context: block length.   Int ->-  -- | Function: @readFull@ function that takes target block index and returns monoid value of it.+  -- | Function: @readFull@ function that takes a target block index and returns a monoid value for+  -- it.   (Int -> m a) ->-  -- | Function: @readPart@ function that takes target block index, left index and right index, and-  -- returns monoid value for it.+  -- | Function: @readPart@ function that takes a target block index and a half-open interval in it+  -- and returns the monoid value for it.   (Int -> Int -> Int -> m a) ->   -- | Input: \(l\).   Int ->@@ -95,7 +101,7 @@ -- -- ==== Constraints -- - \(l \le r\)--- - If an empty interval is queried, the @readPart@ function must return a valid value.+-- - The @readPart@ function must return a valid value for an empty interval. -- -- @since 1.2.5.0 {-# INLINE foldMapWithM #-}@@ -105,10 +111,11 @@   Int ->   -- | Merges function for output values.   (a -> a -> a) ->-  -- | Function: @readFull@ function that takes target block index and returns monoid value of it.+  -- | Function: @readFull@ function that a takes target block index and returns a monoid value for+  -- it.   (Int -> m a) ->-  -- | Function: @readPart@ function that takes target block index, left index and right index, and-  -- returns output value of it.+  -- | Function: @readPart@ function that a takes target block index, a half-open interval in it,+  -- and returns the output value for it.   (Int -> Int -> Int -> m a) ->   -- | Input: \(l\).   Int ->@@ -150,10 +157,11 @@   (Monad m) =>   -- | Context: block length.   Int ->-  -- | Function: @foldFull@ function that takes target block index and returns monoid value of it.+  -- | Function: @foldFull@ function that a takes target block index and returns a monoid value for+  -- it.   (a -> Int -> m a) ->-  -- | Function: @foldPart@ function that takes target block index, left and right local index and returns monoid-  -- value of it.+  -- | Function: @foldPart@ function that a takes target block index, a half-open interval in it+  -- and returns a monoid value for it.   (a -> Int -> Int -> Int -> m a) ->   -- | Initial folding value.   a ->@@ -197,10 +205,10 @@   (Monad m) =>   -- | Context: Block length.   Int ->-  -- | @readFull@ function that takes target block index and returns monoid value of it.+  -- | @readFull@ function that takes a target block index and returns  amonoid value for it.   (a -> Int -> m a) ->-  -- | @readPart@ function that takes target block index, left and right local index and returns monoid-  -- value of it.+  -- | @readPart@ function that takes a target block index, a half-open interval and returns a+  -- monoid value for it.   (a -> Int -> Int -> Int -> m a) ->   -- | Initial folding value.   a ->
src/AtCoder/Extra/Tree/Hld.hs view
@@ -169,7 +169,7 @@ -- @since 1.1.0.0 type Vertex = Int --- | Vertex reindexed by `indexHld`.+-- | Vertex reindexed by `indexHld`. It's contiguous for each segment. -- -- @since 1.1.0.0 type VertexHld = Vertex@@ -376,7 +376,7 @@         ihv = indexHld VG.! hv  -- | \(O(\log n)\) Returns the \(k\)-th vertex of the path between \(u\) and \(v\) from \(u\).--- Throws an error if `k` is out+-- Returns `Nothing` if \(k\) is bigger than the path length. -- -- @since 1.1.0.0 {-# INLINEABLE jump #-}@@ -459,7 +459,7 @@         phy = parentHld VG.! hy  -- | \(O(1)\) Returns a half-open interval of `VertexHld` \([\mathrm{start}, \mathrm{end})\) that--- corresponds to the subtree segments rooted at the given @subtreeRoot@.+-- corresponds to the subtree vertices rooted at the given vertex. -- -- @since 1.1.0.0 {-# INLINEABLE subtreeSegmentInclusive #-}@@ -469,7 +469,7 @@     ir = indexHld VG.! subtreeRoot     sr = subtreeSizeHld VG.! subtreeRoot --- | \(O(1)\) Returns `True` if \(u\) is in a subtree of \(r\).+-- | \(O(1)\) Returns `True` if \(u\) is a vertex of subtree rooted at \(r\). -- -- @since 1.1.0.0 {-# INLINEABLE isInSubtree #-}
src/AtCoder/Extra/Tree/Lct.hs view
@@ -185,7 +185,8 @@     invOpLct :: !(a -> a)   } --- | \(O(n)\) Creates a link/cut tree with \(n\) vertices and no edges.+-- | \(O(n)\) Creates a link/cut tree with \(n\) vertices and no edges. This setup disables subtree+-- queries (`prodSubtree`). -- -- @since 1.1.1.0 {-# INLINE new #-}@@ -200,7 +201,8 @@ newInv :: (PrimMonad m, Monoid a, VU.Unbox a) => (a -> a) -> Int -> m (Lct (PrimState m) a) newInv !invOpLct nLct = buildInv invOpLct (VU.replicate nLct mempty) VU.empty --- | \(O(n + m \log n)\) Creates a link/cut tree of initial monoid values and initial edges.+-- | \(O(n + m \log n)\) Creates a link/cut tree of initial monoid values and initial edges. This+-- setup disables subtree queries (`prodSubtree`). -- -- @since 1.1.1.0 {-# INLINE build #-}@@ -247,7 +249,8 @@   where     !_ = ACIA.checkIndex "AtCoder.Extra.Lct.write" v (nLct lct) --- | Amortized \(O(\log n)\). Modifies the monoid value of a vertex with a pure function.+-- | Amortized \(O(\log n)\). Given a user function \(f\), modifies the monoid value of a vertex+-- \(v\). -- -- @since 1.1.1.0 {-# INLINE modify #-}@@ -259,7 +262,8 @@   where     !_ = ACIA.checkIndex "AtCoder.Extra.Lct.modify" v (nLct lct) --- | Amortized \(O(\log n)\). Modifies the monoid value of a vertex with a monadic function.+-- | Amortized \(O(\log n)\). Given a user function \(f\), modifies the monoid value of a vertex+-- \(v\). -- -- @since 1.1.1.0 {-# INLINE modifyM #-}@@ -276,7 +280,7 @@ -- -------------------------------------------------------------------------------------------------  -- | Amortized \(O(\log n)\). Creates an edge between \(c\) and \(p\). In the represented tree, the--- parent of \(c\) will be \(p\) after this operation.+-- \(p\) will be the parent of \(c\). -- -- @since 1.1.1.0 {-# INLINE link #-}@@ -286,7 +290,7 @@     !_ = ACIA.checkIndex "AtCoder.Extra.Lct.link" c (nLct lct)     !_ = ACIA.checkIndex "AtCoder.Extra.Lct.link" p (nLct lct) --- | Amortized \(O(\log N)\). Deletes an edge between \(u\) and \(v\).+-- | Amortized \(O(\log n)\). Deletes an edge between \(u\) and \(v\). -- -- @since 1.1.1.0 {-# INLINE cut #-}
src/AtCoder/Extra/Tree/TreeMonoid.hs view
@@ -131,7 +131,8 @@ -- @since 1.1.0.0 type VertexHld = Vertex --- | A wrapper for `Hld` getting product on paths on a tree using `Hld` and segment tree(s).+-- | A wrapper of `Hld` for getting monoid product on paths on a tree using `Hld` and segment+-- tree(s). -- -- @since 1.1.0.0 data TreeMonoid a s = TreeMonoid@@ -175,7 +176,7 @@   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>   -- | `Hld.Hld`.   Hld.Hld ->-  -- | Whether the monoid is commutative or not.+  -- | `Commutativity` of the monoid.   Commutativity ->   -- | The vertex weights.   VU.Vector a ->@@ -183,8 +184,8 @@   m (TreeMonoid a (PrimState m)) fromVerts hld commuteTM xs_ = stToPrim $ fromVertsST hld commuteTM xs_ --- | \(O(n)\) Creates a `TreeMonoid` with weignts on edges. The edges are not required to be--- duplicated: only one of \((u, v, w)\) or \((v, u, w)\) is needed.+-- | \(O(n)\) Creates a `TreeMonoid` with weignts on edges. The don't have to be bi-directed: only+-- one of \((u, v, w)\) or \((v, u, w)\) is needed. -- -- @since 1.1.0.0 {-# INLINE fromEdges #-}@@ -192,7 +193,7 @@   (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) =>   -- | `Hld.Hld`.   Hld.Hld ->-  -- | Whether the monoid is commutative or not.+  -- | `Commutativity` of the monoid.   Commutativity ->   -- | Input edges.   VU.Vector (Vertex, Vertex, a) ->@@ -200,7 +201,8 @@   m (TreeMonoid a (PrimState m)) fromEdges hld commuteTM edges = stToPrim $ fromEdgesST hld commuteTM edges --- | \(O(\log^2 n)\) Returns the product of the path between two vertices \(u\), \(v\) (invlusive).+-- | \(O(\log^2 n)\) Returns the monoid product of the path between two vertices \(u\) and \(v\)+-- (invlusive). -- -- @since 1.1.0.0 {-# INLINE prod #-}@@ -235,14 +237,14 @@ exchange :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => TreeMonoid a (PrimState m) -> Vertex -> a -> m a exchange tm i_ x = stToPrim $ exchangeST tm i_ x --- | \(O(\log n)\) Modifies the monoid value of a vertex with a pure function.+-- | \(O(\log n)\) Given a user function \(f\), modifies the monoid value at \(v\). -- -- @since 1.1.0.0 {-# INLINE modify #-} modify :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => TreeMonoid a (PrimState m) -> (a -> a) -> Int -> m () modify tm f i_ = stToPrim $ modifyST tm f i_ --- | \(O(\log n)\) Modifies the monoid value of a vertex with a monadic function.+-- | \(O(\log n)\) Given a user function \(f\), modifies the monoid value at \(v\). -- -- @since 1.1.0.0 {-# INLINE modifyM #-}
src/AtCoder/Extra/WaveletMatrix.hs view
@@ -21,7 +21,7 @@     rank,     rankBetween, -    -- * Selection+    -- * Selection (finding index)      -- | ==== __Example__     -- >>> import AtCoder.Extra.WaveletMatrix qualified as WM@@ -223,7 +223,7 @@   Rwm.selectKthIn rawWm l r k i  -- | \(O(\log |S|)\) Given the interval \([l, r)\), returns the index of the \(k\)-th (0-based)--- largest value. Note that duplicated values are treated as distinct occurrences.+-- largest value in it. Note that duplicated values are treated as distinct occurrences. -- -- @since 1.1.0.0 {-# INLINEABLE kthLargestIn #-}@@ -244,7 +244,8 @@   | otherwise = Nothing  -- | \(O(\log |S|)\) Given the interval \([l, r)\), returns both the index and the value of the--- \(k\)-th (0-based) largest value. Note that duplicated values are treated as distinct occurrences.+-- \(k\)-th (0-based) largest value in it. Note that duplicated values are treated as distinct+-- occurrences. -- -- @since 1.1.0.0 {-# INLINEABLE ikthLargestIn #-}@@ -264,7 +265,7 @@   | otherwise = Nothing  -- | \(O(\log |S|)\) Given the interval \([l, r)\), returns the index of the \(k\)-th (0-based)--- smallest value. Note that duplicated values are treated as distinct occurrences.+-- smallest value in it. Note that duplicated values are treated as distinct occurrences. -- -- @since 1.1.0.0 {-# INLINEABLE kthSmallestIn #-}@@ -284,7 +285,8 @@   | otherwise = Nothing  -- | \(O(\log |S|)\) Given the interval \([l, r)\), returns both the index and the value of the--- \(k\)-th (0-based) smallest value. Note that duplicated values are treated as distinct occurrences.+-- \(k\)-th (0-based) smallest value in it. Note that duplicated values are treated as distinct+-- occurrences. -- -- @since 1.1.0.0 {-# INLINEABLE ikthSmallestIn #-}@@ -394,7 +396,7 @@   Maybe Int lookupGT wm l r y0 = lookupGE wm l r (y0 + 1) --- | \(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in range \([l, r)\) in+-- | \(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in an interval \([l, r)\) in -- ascending order of \(y\). Note that it's only fast when the \(|S|\) is very small. -- -- @since 1.1.0.0@@ -402,7 +404,7 @@ assocsIn :: WaveletMatrix -> Int -> Int -> [(Int, Int)] assocsIn WaveletMatrix {..} l r = Rwm.assocsWith rawWm l r (yDictWm VG.!) --- | \(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in range \([l, r)\) in+-- | \(O(\min(|S|, L) \log |S|)\) Collects \((y, \mathrm{rank}(y))\) in an interval \([l, r)\) in -- descending order of \(y\). Note that it's only fast when the \(|S|\) is very small. -- -- @since 1.1.0.0
src/AtCoder/Extra/WaveletMatrix/BitVector.hs view
@@ -132,8 +132,8 @@ select1 :: BitVector -> Int -> Maybe Int select1 bv = selectKthIn1 bv 0 (VG.length (bitsBv bv)) --- | \(O(\log n)\) Returns the index of \(k\)-th \(0\) (0-based) in \([l, r)\), or `Nothing` if no--- such bit exists.+-- | \(O(\log n)\) Given an interval \([l, r)\), it returns the index of the first occurrence+-- (0-based) of \(0\) in the sequence, or `Nothing` if no such occurrence exists. -- -- @since 1.1.0.0 {-# INLINE selectKthIn0 #-}@@ -156,8 +156,8 @@     nZeros = rank0 bv r - rankL0     rankL0 = rank0 bv l --- | \(O(\log n)\) Returns the index of \(k\)-th \(1\) (0-based) in \([l, r)\), or `Nothing` if no--- such bit exists.+-- | \(O(\log n)\) Given an interval \([l, r)\), it returns the index of the first occurrence+-- (0-based) of \(1\) in the sequence, or `Nothing` if no such occurrence exists. -- -- @since 1.1.0.0 {-# INLINE selectKthIn1 #-}
src/AtCoder/Extra/WaveletMatrix2d.hs view
@@ -82,7 +82,7 @@ -- - Wavelet matrix methods such as `rank` can be implemented -- - `maxRight` can be implemented. --- | Segment Tree on Wavelet Matrix: points on a 2D plane and rectangle products.+-- | Segment Tree on Wavelet Matrix: points on a 2D plane and rectangle products of them. -- -- @since 1.3.0.0 data WaveletMatrix2d s a = WaveletMatrix2d@@ -182,8 +182,8 @@     i_     $ V.zip (Rwm.bitsRwm rawWm2d) segTreesWm2d --- | \(O(\log^2 n)\) Modifies the monoid value at \((x, y)\). Access to unknown points are--- undefined.+-- | \(O(\log^2 n)\) Given a user function \(f\), odifies the monoid value at \((x, y)\). Access to+-- unknown points are undefined. -- -- @since 1.1.0.0 {-# INLINEABLE modify #-}
src/AtCoder/Internal/Assert.hs view
@@ -102,46 +102,108 @@   | p = ()   | otherwise = error s --- | \(O(1)\) Tests \(i \in [0, n)\).+-- | \(O(1)\) Tests \(0 \le i \lt n\). -- -- @since 1.0.0.0 {-# INLINE testIndex #-}-testIndex :: (HasCallStack) => Int -> Int -> Bool+testIndex ::+  (HasCallStack) =>+  -- | \(i\)+  Int ->+  -- | \(n\)+  Int ->+  -- | \(0 \le i \lt n\)+  Bool testIndex i n = 0 <= i && i < n --- | \(O(1)\) Tests whether \([l, r)\) is a valid interval in \([0, n)\).+-- | \(O(1)\) Tests \(0 \le l \le r \le n\). -- -- @since 1.0.0.0 {-# INLINE testInterval #-}-testInterval :: Int -> Int -> Int -> Bool+testInterval ::+  -- | \(l\)+  Int ->+  -- | \(r\)+  Int ->+  -- | \(n\)+  Int ->+  -- | \(0 \le l \le r \le n\).+  Bool testInterval l r n = 0 <= l && l <= r && r <= n --- | \(O(1)\) Tests whether \([l, r)\) is a valid interval in \([l_0, r_0)\).+-- | \(O(1)\) Tests \(l_0 \le l \le r \le r_0\). -- -- @since 1.2.1.0 {-# INLINE testIntervalBounded #-}-testIntervalBounded :: Int -> Int -> Int -> Int -> Bool+testIntervalBounded ::+  -- | \(l\)+  Int ->+  -- | \(r\)+  Int ->+  -- | \(l_0\)+  Int ->+  -- | \(r_0\)+  Int ->+  -- | \(l_0 \le l \le r \le r_0\)+  Bool testIntervalBounded l r l0 r0 = l0 <= l && l <= r && r <= r0  -- | \(O(1)\) Tests \((x, y) \in [0, w) \times [0, h)\). -- -- @since 1.2.3.0 {-# INLINE testPoint2d #-}-testPoint2d :: (HasCallStack) => Int -> Int -> Int -> Int -> Bool+testPoint2d ::+  (HasCallStack) =>+  -- | \(x\)+  Int ->+  -- | \(y\)+  Int ->+  -- | \(w\)+  Int ->+  -- | \(h\)+  Int ->+  -- | \((x, y) \in [0, w) \times [0, h)\)+  Bool testPoint2d x y w h = 0 <= x && x < w && 0 <= y && y < h  -- | \(O(1)\) Tests \([x_1, x_2) \times [y_1 y_2) \in [0, w) \times [0, h)\). -- -- @since 1.2.3.0 {-# INLINE testRect #-}-testRect :: (HasCallStack) => Int -> Int -> Int -> Int -> Int -> Int -> Bool+testRect ::+  (HasCallStack) =>+  -- | \(x_1\)+  Int ->+  -- | \(x_2\)+  Int ->+  -- | \(y_1\)+  Int ->+  -- | \(y_2\)+  Int ->+  -- | \(w\)+  Int ->+  -- | \(h\)+  Int ->+  -- | \([x_1, x_2) \times [y_1 y_2) \in [0, w) \times [0, h)\).+  Bool testRect x1 x2 y1 y2 w h = 0 <= x1 && x1 <= x2 && x2 <= w && 0 <= y1 && y1 <= y2 && y2 <= h --- | \(O(1)\) Tests \(x_1 \le x_2\) and \(y_1 \le \y_2\).+-- | \(O(1)\) Tests \(x_1 \le x_2 \land y_1 \le \y_2\). -- -- @since 1.2.3.0 {-# INLINE testRectShape #-}-testRectShape :: (HasCallStack) => Int -> Int -> Int -> Int -> Bool+testRectShape ::+  (HasCallStack) =>+  -- | \(x_1\)+  Int ->+  -- | \(x_2\)+  Int ->+  -- | \(y_1\)+  Int ->+  -- | \(y_2\)+  Int ->+  -- | \(x_1 \le x_2 \land y_1 \le \y_2\).+  Bool testRectShape x1 x2 y1 y2 = x1 <= x2 && y1 <= y2  -- | \(O(1)\) Asserts \(0 \leq i \lt n\) for an array index \(i\).
src/AtCoder/Internal/Barrett.hs view
@@ -47,28 +47,28 @@       Show     ) --- | Creates a `Barrett` for a modulus value \(m\) of type `Word32` value.+-- | \(O(1)\) Creates a `Barrett` for a modulus value \(m\) of type `Word32`. -- -- @since 1.0.0.0 {-# INLINE new32 #-} new32 :: Word32 -> Barrett new32 m = Barrett m $ maxBound @Word64 `div` (fromIntegral m :: Word64) + 1 --- | Creates a `Barrett` for a modulus value \(m\) of type `Word64` value.+-- | \(O(1)\) Creates a `Barrett` for a modulus value \(m\) of type `Word64`. -- -- @since 1.0.0.0 {-# INLINE new64 #-} new64 :: Word64 -> Barrett new64 m = Barrett (fromIntegral m) $ maxBound @Word64 `div` m + 1 --- | Retrieves the modulus \(m\).+-- | \(O(1)\) Retrieves the modulus \(m\). -- -- @since 1.0.0.0 {-# INLINE umod #-} umod :: Barrett -> Word32 umod Barrett {mBarrett} = mBarrett --- | Calculates \(a b \bmod m\).+-- | \(O(\log n)\) Calculates \(a b \bmod m\). -- -- @since 1.0.0.0 {-# INLINE mulMod #-}
src/AtCoder/Internal/Queue.hs view
@@ -329,7 +329,7 @@ writeBack que i x = stToPrim $ do   modifyBackM que (pure . const x) i --- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the first element.+-- | \(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the first element with it. -- -- @since 1.2.3.0 {-# INLINE modifyFront #-}@@ -337,7 +337,7 @@ modifyFront que f i = stToPrim $ do   modifyFrontM que (pure . f) i --- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the last element.+-- | \(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the last element with it. -- -- @since 1.2.3.0 {-# INLINE modifyBack #-}@@ -345,7 +345,7 @@ modifyBack que f i = stToPrim $ do   modifyBackM que (pure . f) i --- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the first element.+-- | \(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the first element with it. -- -- @since 1.2.3.0 {-# INLINE modifyFrontM #-}@@ -356,7 +356,7 @@   let !_ = ACIA.runtimeAssert (0 <= i && i < r - l) "AtCoder.Internal.Queue.modifyFrontM: index out of bounds"   VGM.modifyM vecQ f (l + i) --- | \(O(1)\) Given user function \(f\), returns the \(k\)-th value from the last element.+-- | \(O(1)\) Given user function \(f\), modifies the \(k\)-th value from the last element with it. -- -- @since 1.2.3.0 {-# INLINE modifyBackM #-}
src/AtCoder/SegTree.hs view
@@ -171,7 +171,7 @@ write :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> Int -> a -> m () write self p x = stToPrim $ writeST self p x --- | (Extra API) Modifies \(p\)-th value with a function \(f\).+-- | (Extra API) Given a user function \(f\), modifies \(p\)-th value with it. -- -- ==== Constraints -- - \(0 \leq p \lt n\)@@ -184,7 +184,7 @@ modify :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => SegTree (PrimState m) a -> (a -> a) -> Int -> m () modify self f p = stToPrim $ modifyST self f p --- | (Extra API) Modifies \(p\)-th value with a monadic function \(f\).+-- | (Extra API) Given a user function \(f\), modifies \(p\)-th value with it. -- -- ==== Constraints -- - \(0 \leq p \lt n\)