ac-library-hs 1.4.0.0 → 1.5.0.0

raw patch · 49 files changed

+333/−248 lines, 49 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +7/−2
• README.md +1/−1
• ac-library-hs.cabal +2/−2
• src/AtCoder/Convolution.hs +1/−1
• src/AtCoder/Dsu.hs +1/−1
• src/AtCoder/Extra/Bisect.hs +2/−3
• src/AtCoder/Extra/DynLazySegTree.hs +2/−2
• src/AtCoder/Extra/DynLazySegTree/Persistent.hs +2/−2
• src/AtCoder/Extra/DynSegTree.hs +2/−2
• src/AtCoder/Extra/DynSegTree/Persistent.hs +2/−2
• src/AtCoder/Extra/DynSegTree/Raw.hs +2/−2
• src/AtCoder/Extra/Graph.hs +72/−41
• src/AtCoder/Extra/HashMap.hs +1/−1
• src/AtCoder/Extra/Ix0.hs +5/−5
• src/AtCoder/Extra/Mo.hs +1/−1
• src/AtCoder/Extra/ModInt64.hs +6/−6
• src/AtCoder/Extra/Monoid/Mat2x2.hs +3/−3
• src/AtCoder/Extra/Monoid/RangeAdd.hs +1/−1
• src/AtCoder/Extra/Monoid/V2.hs +1/−1
• src/AtCoder/Extra/MultiSet.hs +1/−1
• src/AtCoder/Extra/Pdsu.hs +3/−3
• src/AtCoder/Extra/Pool.hs +2/−2
• src/AtCoder/Extra/Semigroup/Matrix.hs +2/−2
• src/AtCoder/Extra/Tree.hs +5/−5
• src/AtCoder/Extra/Tree/Hld.hs +7/−7
• src/AtCoder/Extra/Tree/Lct.hs +3/−3
• src/AtCoder/Extra/Tree/TreeMonoid.hs +1/−2
• src/AtCoder/Extra/Vector.hs +1/−1
• src/AtCoder/Extra/WaveletMatrix/BitVector.hs +1/−1
• src/AtCoder/Extra/WaveletMatrix/Raw.hs +1/−1
• src/AtCoder/Extra/WaveletMatrix2d.hs +1/−1
• src/AtCoder/FenwickTree.hs +3/−3
• src/AtCoder/Internal/Assert.hs +1/−1
• src/AtCoder/Internal/Bit.hs +2/−2
• src/AtCoder/Internal/Buffer.hs +3/−3
• src/AtCoder/Internal/Csr.hs +1/−1
• src/AtCoder/Internal/String.hs +2/−2
• src/AtCoder/LazySegTree.hs +3/−3
• src/AtCoder/MaxFlow.hs +2/−2
• src/AtCoder/ModInt.hs +4/−4
• src/AtCoder/SegTree.hs +4/−4
• src/AtCoder/String.hs +1/−1
• test/Main.hs +2/−0
• test/Tests/Extra/Graph.hs +40/−8
• test/Tests/Extra/Hld.hs +36/−0
• test/Tests/Extra/WaveletMatrix2d.hs +0/−4
• test/Tests/SegTree.hs +3/−4
• test/Tests/Util.hs +84/−1
• test/Util.hs +0/−97

@@ -1,9 +1,14 @@ # Revision history for acl-hs +## 1.5.0.0 -- May 2025++- Changed the parameter orders of `bfs01` and `dijkstra` in `AtCoder.Extra.Graph`.+- Fixed `Hld.new` to have `headHld` of `[0]`, not `[-1]`.+ ## 1.4.0.0 -- May 2025 -- Added cycle detection functions to `AtCoder.Extra.Graph`-- Fixed the exteremely slow `Internal.GrowVec` functions with `{-# INLINE #-}`+- Added cycle detection functions to `AtCoder.Extra.Graph`.+- Fixed the exteremely slow `Internal.GrowVec` functions with `{-# INLINE #-}`. - Changed `AtCoder.Extra.Pdsu.merge` to return new representative. - Fixed `AtCoder.Extra.Hld.jump` to return `Nothing` for `k < 0`. 

@@ -2,7 +2,7 @@  Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive programming on [AtCoder](https://atcoder.jp/). -The `main` branch is the version avaiable on AtCoder. See `dev` branch for upcoming updates.+The `main` branch is the version avaiable on AtCoder (+ documentation fixes). See `dev` branch for upcoming updates.  ## Notes 

@@ -4,7 +4,7 @@ -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version:         1.4.0.0+version:         1.5.0.0 synopsis:        Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive@@ -151,6 +151,7 @@     Tests.Extra.DynSparseSegTree.Persistent     Tests.Extra.Graph     Tests.Extra.HashMap+    Tests.Extra.Hld     Tests.Extra.IntervalMap     Tests.Extra.IntMap     Tests.Extra.IntSet@@ -192,7 +193,6 @@     Tests.String     Tests.TwoSat     Tests.Util-    Util    type:           exitcode-stdio-1.0   hs-source-dirs: test

@@ -64,7 +64,7 @@ import GHC.TypeNats (natVal')  -- NOTE(pref): Inlining `convolution` functions makes the compile time extremely too slow, while it--- surely makes beter runtime performance (#51).+-- surely makes better runtime performance (#51).  -- | Calculates the convolution in \(\bmod m\) for a vector of `ACIM.ModInt`. It returns an empty -- array if at least one of \(a\) and \(b\) are empty.

@@ -80,7 +80,7 @@ import Data.Vector.Unboxed.Mutable qualified as VUM import GHC.Stack (HasCallStack) --- | A disjoint set union. Akso known as Union-Find tree.+-- | A disjoint set union. Also known as Union-Find tree. -- -- @since 1.0.0.0 data Dsu s = Dsu

@@ -6,7 +6,7 @@ -- @ -- 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+--         L R              L, R: left and right points of the boundary -- @ -- -- ==== __Example__@@ -64,7 +64,6 @@ -- >>> lowerBound xs 4 -- 4 ----- -- >>> lowerBound xs 5 -- 6 --@@ -256,7 +255,7 @@   Int minLeft l r p = runIdentity $ minLeftM l r (pure . p) --- | \(O(\log n)\) Monadic variant of `maxRight`.+-- | \(O(\log n)\) Monadic variant of `minLeft`. -- -- @since 1.3.0.0 {-# INLINE minLeftM #-}

@@ -2,7 +2,7 @@ {-# LANGUAGE TypeFamilies #-}  -- | A dynamic, lazily propagated segment tree that covers a half-open interval \([l_0, r_0)\).--- Nodes are instantinated as needed, with the required capacity being /approximately/ \(4q \log_2 L\),+-- Nodes are instantiated as needed, with the required capacity being /approximately/ \(4q \log_2 L\), -- where \(q\) is the number of mutable operations and \(L\) is the length of the interval. -- -- ==== __Example__@@ -312,7 +312,7 @@ maxRightM dst root f = do   Raw.maxRightM dst root f --- | \(O(\log L)\) Claers all the nodes from the storage.+-- | \(O(\log L)\) Clears all the nodes from the storage. -- -- @since 1.2.2.0 {-# INLINE clear #-}

@@ -2,7 +2,7 @@ {-# LANGUAGE TypeFamilies #-}  -- | A dynamic, persistent, lazily propagated segment tree that covers a half-open interval--- \([l_0, r_0)\). Nodes are instantinated as needed, with the required capacity being+-- \([l_0, r_0)\). Nodes are instantiated as needed, with the required capacity being -- /approximately/ \(8q \log_2 L\), where \(q\) is the number of mutable operations and \(L\) is the -- length of the interval. --@@ -294,7 +294,7 @@ maxRightM dst root f = do   Raw.maxRightM dst root f --- | \(O(\log L)\) Claers all the nodes from the storage.+-- | \(O(\log L)\) Clears all the nodes from the storage. -- -- @since 1.2.2.0 {-# INLINE clear #-}

@@ -2,7 +2,7 @@ {-# LANGUAGE TypeFamilies #-}  -- | A dynamic segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are--- instantinated as needed, with the required capacity being /approximately/ \(2q \log_2 L\), where+-- instantiated as needed, with the required capacity being /approximately/ \(2q \log_2 L\), where -- \(q\) is the number of mutable operations and \(L\) is the length of the interval. -- -- ==== __Example__@@ -223,7 +223,7 @@ maxRightM dst root f = do   Raw.maxRightM dst root f --- | \(O(\log L)\) Claers all the nodes from the storage.+-- | \(O(\log L)\) Clears all the nodes from the storage. -- -- @since 1.2.2.0 {-# INLINE clear #-}

@@ -2,7 +2,7 @@ {-# LANGUAGE TypeFamilies #-}  -- | A dynamic, persistent segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are--- instantinated as needed, with the required capacity being /approximately/ \(4q \log_2 L\), where+-- instantiated as needed, with the required capacity being /approximately/ \(4q \log_2 L\), where -- \(q\) is the number of mutable operations and \(L\) is the length of the interval. -- -- ==== __Example__@@ -215,7 +215,7 @@ maxRightM dst root f = do   Raw.maxRightM dst root f --- | \(O(\log L)\) Claers all the nodes from the storage.+-- | \(O(\log L)\) Clears all the nodes from the storage. -- -- @since 1.2.2.0 {-# INLINE clear #-}

@@ -47,8 +47,8 @@ import GHC.Stack (HasCallStack) import Prelude hiding (read) --- | A dynamic segment tree that covers a half-open interval \([l_0, r_0)\). Is is dynamic in that--- the nodes are instantinated as needed.+-- | A dynamic segment tree that covers a half-open interval \([l_0, r_0)\). It is dynamic in that+-- the nodes are instantiated as needed. -- -- @since 1.2.1.0 data DynSegTree s a = DynSegTree

@@ -242,8 +242,7 @@  -- TODO: is this minimum cycle? --- | \(O(n + m)\) Given a directed graph, finds a minimal cycle and returns a vector of vertices and--- a vector of @(vertices, csrEdgeIndices)@.+-- | \(O(n + m)\) Given a directed graph, finds a minimal cycle and returns @(vertices, csrEdgeIndices)@. -- -- ==== __Example__ --@@ -346,9 +345,9 @@     then pure Nothing     else pure $ Just (vs', es') --- | \(O(n + m)\) Given an undirected graph, finds a minimal cycle and returns a vector of vertices--- a vector of @(vertices, csrEdgeIndices)@. A single edge index does not make much sense for an--- undirected graph, so map back to the original edge index manually if needed.+-- | \(O(n + m)\) Given an undirected graph, finds a minimal cycle and returns @(vertices, csrEdgeIndices)@.+-- A single edge index does not make much sense for an undirected graph, so map back to the original+-- edge index manually if needed. -- -- ==== Constraints -- - The graph must be created with `swapDupe` or `swapDupe'`. Otherwise the returned edge indices@@ -720,7 +719,7 @@   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+  -- | Graph that represents a block-cut tree, where super vertices \((v \ge n)\) represent each   -- biconnected component.   Csr () blockCut n gr = runST $ do@@ -792,7 +791,7 @@   n' <- VGM.unsafeRead next 0   Csr.build' n' <$> B.unsafeFreeze edges --- | \(O(n + m)\) Returns [blocks (biconnected comopnents)](https://en.wikipedia.org/wiki/Biconnected_component)+-- | \(O(n + m)\) Returns [blocks (biconnected components)](https://en.wikipedia.org/wiki/Biconnected_component) -- of the graph. -- -- ==== __Example__@@ -945,62 +944,74 @@  -- | \(O(n + m)\) Opinionated 01-BFS that returns a distance array. --+-- Unreachable vertices are given distance of `-1`. Note that the third argument is the capacity of+-- deque, not distance of unreachable vertices.+--+-- ==== Constraints+-- - \(\marhrm{capacity} \ge 0\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let es = VU.fromList [(0, 1, 10 :: Int), (0, 2, 0), (2, 1, 1)] -- >>> let gr = Gr.build 4 es--- >>> let capacity = 10--- >>> Gr.bfs01 4 (Gr.adjW gr) capacity (VU.singleton (0, 0))+-- >>> let capacity = VU.length es+-- >>> Gr.bfs01 4 capacity (Gr.adjW gr) (VU.singleton (0, 0)) -- [0,1,0,-1] ----- @since 1.2.4.0+-- @since 1.5.0.0 {-# INLINE bfs01 #-} bfs01 ::   forall i.   (HasCallStack, Ix0 i, VU.Unbox i) =>-  -- | Zero-based index boundary.+  -- | Zero-based vertex boundary. It's \(n\) if the graph is one-dimensional.   Bounds0 i ->+  -- | Capacity of deque, often the number of edges \(m\).+  Int ->   -- | Graph function that takes the vertexand returns adjacent vertices with edge weights, where   -- \(w > 0\).   (i -> VU.Vector (i, Int)) ->-  -- | Capacity of deque, often the number of edges \(m\).-  Int ->   -- | Weighted source vertices.   VU.Vector (i, Int) ->   -- | Distance array in one-dimensional index. Unreachable vertices are assigned distance of @-1@.   VU.Vector Int-bfs01 !bnd0 !gr !capacity !sources =-  let (!dist, !_) = bfs01Impl False bnd0 gr capacity sources+bfs01 !bnd0 !capacity !gr !sources =+  let (!dist, !_) = bfs01Impl False bnd0 capacity gr sources    in dist  -- | \(O(n + m)\) Opinionated 01-BFS that returns a distance array and a predecessor array. --+-- Unreachable vertices are given distance of `-1`. Note that the third argument is the capacity of+-- deque, not distance of unreachable vertices.+--+-- ==== Constraints+-- - \(\marhrm{capacity} \ge 0\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let es = VU.fromList [(0, 1, 10 :: Int), (0, 2, 0), (2, 1, 1)] -- >>> let gr = Gr.build 4 es--- >>> let capacity = 10--- >>> let (!dist, !prev) = Gr.trackingBfs01 4 (Gr.adjW gr) capacity (VU.singleton (0, 0))+-- >>> let capacity = VU.length es+-- >>> let (!dist, !prev) = Gr.trackingBfs01 4 capacity (Gr.adjW gr) (VU.singleton (0, 0)) -- >>> dist -- [0,1,0,-1] -- -- >>> Gr.constructPathFromRoot prev 1 -- [0,2,1] ----- @since 1.2.4.0+-- @since 1.5.0.0 {-# INLINE trackingBfs01 #-} trackingBfs01 ::   forall i.   (HasCallStack, Ix0 i, VU.Unbox i) =>-  -- | Zero-based index boundary.+  -- | Zero-based vertex boundary. It's \(n\) if the graph is one-dimensional.   Bounds0 i ->+  -- | Capacity of deque, often the number of edges \(m\).+  Int ->   -- | Graph function that takes the vertex and returns adjacent vertices with edge weights, where   -- \(w > 0\).   (i -> VU.Vector (i, Int)) ->-  -- | Capacity of deque, often the number of edges \(m\).-  Int ->   -- | Weighted source vertices.   VU.Vector (i, Int) ->   -- | A tuple of (distance array in one-dimensional index, predecessor array). Unreachable vertices@@ -1014,11 +1025,11 @@   (HasCallStack, Ix0 i, VU.Unbox i) =>   Bool ->   Bounds0 i ->-  (i -> VU.Vector (i, Int)) ->   Int ->+  (i -> VU.Vector (i, Int)) ->   VU.Vector (i, Int) ->   (VU.Vector Int, VU.Vector Int)-bfs01Impl !trackPrev !bnd0 !gr !capacity !sources+bfs01Impl !trackPrev !bnd0 !capacity !gr !sources   | VU.null sources && trackPrev = (VU.replicate nVerts (-1), VU.replicate nVerts (-1))   | VU.null sources = (VU.replicate nVerts (-1), VU.replicate 0 (-1))   | otherwise = runST $ do@@ -1029,7 +1040,8 @@           else VUM.replicate @_ @Int 0 (-1)       -- NOTE: Just like Dijkstra, we need capacity of `m`, as the first appearance of a vertex is not       -- always with minimum distance.-      deque <- Q.newDeque @_ @(i, Int) capacity+      -- NOTE: Ensure minimum capacity of |sources| (too conservative?)+      deque <- Q.newDeque @_ @(i, Int) $ capacity + VU.length sources        -- set source values       VU.forM_ sources $ \(!src, !w0) -> do@@ -1072,65 +1084,71 @@  -- | \(O((n + m) \log n)\) Dijkstra's algorithm that returns a distance array. --+-- ==== Constraints+-- - \(\mathrm{capacity} \ge 0\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let es = VU.fromList [(0, 1, 10 :: Int), (1, 2, 20), (2, 3, 1), (1, 3, 40), (4, 3, 0)] -- >>> let gr = Gr.build 5 es--- >>> let capacity = 10--- >>> Gr.dijkstra 5 (Gr.adjW gr) capacity (-1) (VU.singleton (0, 0))+-- >>> let capacity = VU.length es+-- >>> Gr.dijkstra 5 capacity (Gr.adjW gr) (-1) (VU.singleton (0, 0)) -- [0,10,30,31,-1] ----- @since 1.2.4.0+-- @since 1.5.0.0 {-# INLINE dijkstra #-} dijkstra ::   forall i w.   (HasCallStack, Ix0 i, Ord i, VU.Unbox i, Num w, Ord w, VU.Unbox w) =>-  -- | Zero-based vertex boundary.+  -- | Zero-based vertex boundary. It's \(n\) if the graph is one-dimensional.   Bounds0 i ->+  -- | Capacity of the heap, often the number of edges \(m\).+  Int ->   -- | Graph function that takes a vertex and returns adjacent vertices with edge weights, where   -- \(w \ge 0\).   (i -> VU.Vector (i, w)) ->-  -- | Capacity of the heap, often the number of edges \(m\).-  Int ->   -- | Distance assignment for unreachable vertices.   w ->   -- | Source vertices with initial weights.   VU.Vector (i, w) ->   -- | Distance array in one-dimensional index.   VU.Vector w-dijkstra !bnd0 !gr !capacity !undefW !sources =-  let (!dist, !_) = dijkstraImpl False bnd0 gr capacity undefW sources+dijkstra !bnd0 !capacity !gr !undefW !sources =+  let (!dist, !_) = dijkstraImpl False bnd0 capacity gr undefW sources    in dist  -- | \(O((n + m) \log n)\) Dijkstra's algorithm that returns a distance array and a predecessor -- array. --+-- ==== Constraints+-- - \(\mathrm{capacity} \ge 0\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let es = VU.fromList [(0, 1, 10 :: Int), (1, 2, 20), (2, 3, 1), (1, 3, 40), (4, 3, 0)] -- >>> let gr = Gr.build 5 es--- >>> let capacity = 10--- >>> let (!dist, !prev) = Gr.trackingDijkstra 5 (Gr.adjW gr) capacity (-1) (VU.singleton (0, 0))+-- >>> let capacity = VU.length es+-- >>> let (!dist, !prev) = Gr.trackingDijkstra 5 capacity (Gr.adjW gr) (-1) (VU.singleton (0, 0)) -- >>> dist -- [0,10,30,31,-1] -- -- >>> Gr.constructPathFromRoot prev 3 -- [0,1,2,3] ----- @since 1.2.4.0+-- @since 1.5.0.0 {-# INLINE trackingDijkstra #-} trackingDijkstra ::   forall i w.   (HasCallStack, Ix0 i, Ord i, VU.Unbox i, Num w, Ord w, VU.Unbox w) =>-  -- | Zero-based vertex boundary.+  -- | Zero-based vertex boundary. It's \(n\) if the graph is one-dimensional.   Bounds0 i ->+  -- | Capacity of the heap, often the number of edges \(m\).+  Int ->   -- | Graph function that takes a vertex and returns adjacent vertices with edge weights, where   -- \(w \ge 0\).   (i -> VU.Vector (i, w)) ->-  -- | Capacity of the heap, often the number of edges \(m\).-  Int ->   -- | Distance assignment for unreachable vertices.   w ->   -- | Source vertices with initial weights.@@ -1145,18 +1163,19 @@   (HasCallStack, Ix0 i, Ord i, VU.Unbox i, Num w, Ord w, VU.Unbox w) =>   Bool ->   Bounds0 i ->-  (i -> VU.Vector (i, w)) ->   Int ->+  (i -> VU.Vector (i, w)) ->   w ->   VU.Vector (i, w) ->   (VU.Vector w, VU.Vector Int)-dijkstraImpl !trackPrev !bnd0 !gr !capacity !undefW !sources+dijkstraImpl !trackPrev !bnd0 !capacity !gr !undefW !sources   | VU.null sources && trackPrev = (VU.replicate nVerts undefW, VU.replicate nVerts (-1))   | VU.null sources = (VU.replicate nVerts undefW, VU.replicate 0 (-1))   | otherwise = runST $ do       !dist <- VUM.replicate @_ @w nVerts undefW       -- REMARK: (w, i) for sort by width-      !heap <- MH.new @_ @(w, i) capacity+      -- REMARK: We need least capacity of |source|+      !heap <- MH.new @_ @(w, i) $ capacity + VU.length sources       !prev <-         if trackPrev           then VUM.replicate @_ @Int nVerts (-1)@@ -1427,6 +1446,9 @@ -- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@ -- is negative. --+-- ==== Constraints+-- - \(n \ge 1\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1465,6 +1487,9 @@ -- - There's a negative loop if there's any vertex \(v\) where @m VU.! (`index0` (n, n) (v, v))@ -- is negative. --+-- ==== Constraints+-- - \(n \ge 1\)+-- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr -- >>> import Data.Vector.Unboxed qualified as VU@@ -1552,6 +1577,9 @@  -- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight change or new edge addition. --+-- ==== Constraints+-- - \(n \ge 1\)+-- -- @since 1.2.4.0 {-# INLINE updateEdgeFloydWarshall #-} updateEdgeFloydWarshall ::@@ -1577,6 +1605,9 @@   stToPrim $ updateEdgeFloydWarshallST False mat prev nVerts undefW a b w  -- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight chaneg or new edge addition.+--+-- ==== Constraints+-- - \(n \ge 1\) -- -- @since 1.2.4.0 {-# INLINE updateEdgeTrackingFloydWarshall #-}

@@ -17,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)\) in averaged:+-- `insert`, `lookup` and other functions are available in \(O(1)\) on average: -- -- >>> HM.insert hm 0 100 -- >>> HM.insert hm 10 101

@@ -3,18 +3,18 @@ -- | 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})\).+-- | Zero-based \(n\)-dimensional bounds: \([0, d_0) \times [0, d_1) \times \cdots \times [0, d_{n - 1})\). type Bounds0 i = i  -- | Zero-based \(n\)-dimensional index. class Ix0 i where-  -- | Returns the size of the bounds: \(\Pi_i d_i\).+  -- | Returns the size of the bounds: \(\prod_i d_i\).   rangeSize0 :: Bounds0 i -> Int -  -- | Returns zero-based one dimensional 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.+  -- | Returns whether an index is contained in bounds.   inRange0 :: Bounds0 i -> i -> Bool  instance Ix0 Int where@@ -59,7 +59,7 @@  instance Ix0 (Int, Int, Int, Int, Int, Int) where   {-# INLINE rangeSize0 #-}-  rangeSize0 (!d6, !d5, !d4, !d3, !d2, !d1) = d6 + d5 * d4 * d3 * d2 * d1+  rangeSize0 (!d6, !d5, !d4, !d3, !d2, !d1) = d6 * d5 * d4 * d3 * d2 * d1   {-# INLINE index0 #-}   index0 (!_, !d5, !d4, !d3, !d2, !d1) (!x6, !x5, !x4, !x3, !x2, !x1) = ((((x6 * d5 + x5) * d4 + x4) * d3 + x3) * d2 + x2) * d1 + x1   {-# INLINE inRange0 #-}

@@ -1,5 +1,5 @@ -- | Mo's algorithm for handling \([l, r)\) offline queries in \(O((n + q) \sqrt n f)\) time--- complecity, where \(n\) is the length of index, \(q\) is the number of queries and \(f\) is the+-- complexity, where \(n\) is the length of index, \(q\) is the number of queries and \(f\) is the -- time for processing element addition or deletion. Due to the high time complexity, it is -- recommended to choose an efficient data structure such as Fenwick Tree for query processing. --

@@ -110,9 +110,9 @@ unsafeNew :: (KnownNat a) => Word64 -> ModInt64 a unsafeNew = ModInt64 --- | \(O(1)\) Retrieve the mod from a `ModInt64` object.+-- | \(O(1)\) Retrieve the modulus from a `ModInt64` object. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.2.6.0@@ -120,9 +120,9 @@ modulus :: forall a. (KnownNat a) => ModInt64 a -> Int modulus _ = fromIntegral (natVal' (proxy# @a)) --- | \(O(1)\) Returns the internal value in `Int`.+-- | \(O(1)\) Returns the internal value as an `Int`. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.2.6.0@@ -130,9 +130,9 @@ val :: forall a. (KnownNat a) => ModInt64 a -> Int val = fromIntegral . val64 --- | \(O(1)\) Returns the internal value in `Word64`.+-- | \(O(1)\) Returns the internal value as a `Word64`. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.2.6.0

@@ -2,7 +2,7 @@ {-# LANGUAGE TypeFamilies #-}  -- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but is compatible--- with inverse opereations.+-- with inverse operations. -- -- @since 1.1.0.0 module AtCoder.Extra.Monoid.Mat2x2@@ -136,7 +136,7 @@     !a21' = f a21     !a22' = f a22 --- | \(O(1)\) Returns the determinan of the matrix.+-- | \(O(1)\) Returns the determinant of the matrix. -- -- @since 1.1.0.0 {-# INLINE det #-}@@ -146,7 +146,7 @@ -- | \(O(1)\) Returns the inverse matrix, based on `Fractional` instance (mainly for @ModInt@). -- -- ==== Constraints--- - The determinant (`det`) of the matrix must be non-zero, otherwise an error is thrown.+-- - The determinant (`det`) of the matrix must be nonzero, otherwise an error is thrown. -- -- @since 1.1.0.0 {-# INLINE inv #-}

@@ -8,7 +8,7 @@   ( -- * RangeAdd     RangeAdd (..), -    -- * Constructor+    -- * Constructors     new,     unRangeAdd, 

@@ -4,7 +4,7 @@ -- | A monoid acted on by `Mat2x2` or `Affine1`, an affine transformation target. -- -- ==== As an `Affine1` action target--- Compared to `Sum`, `V2` hold the length in the second value.+-- Compared to `Sum`, `V2` holds the length in the second value. -- -- @since 1.1.0.0 module AtCoder.Extra.Monoid.V2

@@ -2,7 +2,7 @@ {-# LANGUAGE RecordWildCards #-}  -- | A fast, mutable multiset for `Int` keys backed by a @HashMap@. Most operations are performed--- in \(O(1)\) in average.+-- in \(O(1)\) on average. -- -- ==== Capacity limitation -- Access to each key creates a new entry. Note that entries cannot be invalidated due to the

@@ -3,12 +3,12 @@ -- original implementation: -- <https://qiita.com/drken/items/cce6fc5c579051e64fab> --- | A potentialized disjoint set union on a [group](https://en.wikipedia.org/wiki/Group_(mathematics\))+-- | 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 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+-- The group type is represented as a `Monoid` with an inverse operator, passed on `new`. This -- approach avoids defining a separate typeclass for groups. -- -- ==== Invariant@@ -166,7 +166,7 @@ diff dsu v1 v2 = stToPrim $ diffST dsu v1 v2  -- | \(O(\alpha(n))\) Returns the potential of \(v_1\) relative to \(v_2\): \(p(v_1) \cdot p^{-1}(v_2)\)--- if the two vertices belong to the same group. Returns meaningless value if the two vertices are+-- if the two vertices belong to the same group. Returns a meaningless value if the two vertices are -- not connected. -- -- @since 1.1.0.0

@@ -50,7 +50,7 @@ import GHC.Stack (HasCallStack) import Prelude hiding (read) --- | Fixed-sized array for \(O(1)\) allocation and \(O(1)\) clearing after \(O(n)\) construction.+-- | Fixed-size array for \(O(1)\) allocation and \(O(1)\) clearing after \(O(n)\) construction. -- -- @since 1.2.0.0 data Pool s a = Pool@@ -166,9 +166,9 @@ -- | \(O(1)\) Writes to the \(k\)-th value. -- -- ==== Constraints+-- - \(0 \le i \lt n\) -- -- @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

@@ -1,7 +1,7 @@ {-# LANGUAGE MagicHash #-} {-# LANGUAGE RecordWildCards #-} --- | A simple HxW matrix backed by a vector, mainly for binary exponention.+-- | A simple HxW matrix backed by a vector, mainly for binary exponentiation. -- -- The matrix is a left semigroup action: \(m_2 (m_1 v) = (m_2 \circ m_1) v\). --@@ -65,7 +65,7 @@ import GHC.TypeNats (KnownNat, natVal') import Prelude hiding (map) --- | A simple HxW matrix backed by a vector, mainly for binary exponention.+-- | A simple HxW matrix backed by a vector, mainly for binary exponentiation. -- -- The matrix is a left semigroup action: \(m_2 (m_1 v) = (m_2 \circ m_1) v\). --

@@ -12,7 +12,7 @@      -- * Tree folding -    -- | These function are built around the three type parameters: \(w\), \(f\) and \(a\).+    -- | These functions are built around the three type parameters: \(w\), \(f\), and \(a\).     --     -- - \(w\): Edge weight.     -- - \(f\): Monoid action to a vertex value. These actions are created from vertex value \(a\)@@ -70,7 +70,7 @@       !w = VU.maximum bfs2    in ((from, to), w) --- | \(O(n + m)\) Returns the path longest path in a tree and the distance of it.+-- | \(O(n + m)\) Returns the longest path in a tree and the distance of it. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr@@ -101,9 +101,9 @@       !w = bfs2 VG.! to    in (Gr.constructPathFromRoot parents to, w) --- | \(O(m \log m)\) Kruscal's algorithm. Returns edge indices for building a minimum spanning tree.+-- | \(O(m \log m)\) Kruskal's algorithm. Returns edge indices for building a minimum spanning tree. ----- NOTE: The edges should not be duplicated: only one of \((u, v, w)\) or \((v, u w)\) is required+-- NOTE: The edges should not be duplicated: only one of \((u, v, w)\) or \((v, u, w)\) is required -- for each edge. -- -- ==== __Example__@@ -127,7 +127,7 @@ mst :: (Num w, Ord w, VU.Unbox w) => Int -> VU.Vector (Int, Int, w) -> (w, VU.Vector Bit, Gr.Csr w) mst = mstBy (comparing id) --- | \(O(m \log m)\) Kruscal's algorithm. Returns edge indices for building a minimum/maximum+-- | \(O(m \log m)\) Kruskal's algorithm. Returns edge indices for building a minimum/maximum -- spanning tree. -- -- NOTE: The edges should not be duplicated: only one of \((u, v, w)\) or \((v, u, w)\) is required

@@ -27,14 +27,14 @@ -- -- @ --  0==1==2==3==4==5==6==7==8==9     XX: VertexHld---     |        |                    ==: edges on the same semgent+--     |        |                    ==: edges on the same segment -- 14==13       10==11==12           |: edge between different segments --     | --     15 -- @ -- -- Note that vertices on higher (closer to the root) segments are assigned smaller indices. This is--- very internally very important when calculating `lca`.+-- internally very important when calculating `lca`. -- -- ===== `headHld`: Vertex -> Vertex --@@ -60,7 +60,7 @@ -- @ -- (-1)==0==8==7==3==1==2==12==13==15     XX: original Vertex --       |        |---    5==8        1==11=8+--    5==8        1==11==8 --       | --       5 -- @@@ -218,7 +218,7 @@ -- -- ==== Constraints -- - \(n \ge 1\)--- - The input graph must be a tree; the edges must be non-directed (both \((u, v, w)\) and+-- - The input graph must be a tree; the edges must be undirected (both \((u, v, w)\) and --   \((v, u, w)\) edges are required). -- -- @since 1.1.0.0@@ -230,7 +230,7 @@ -- -- ==== Constraints -- - \(n \ge 1\)--- - The input graph must be a tree; the edges must be non-directed (both \((u, v, w)\) and+-- - The input graph must be a tree; the edges must be undirected (both \((u, v, w)\) and --   \((v, u, w)\) edges are required). -- -- @since 1.1.0.0@@ -242,9 +242,9 @@         0         (VU.singleton (-1))         (VU.singleton 0)-        (VU.singleton (-1))         (VU.singleton 0)         (VU.singleton 0)+        (VU.singleton 0)         (VU.singleton 1)   | otherwise = runST $ do       -- Re-create adjacent vertices so that the biggest subtree's head vertex comes first.@@ -364,7 +364,7 @@ ancestor :: (HasCallStack) => Hld -> Vertex -> Int -> Vertex ancestor Hld {..} parent k0 = inner parent k0   where-    !_ = ACIA.runtimeAssert (0 <= k0 && k0 <= depthHld VG.! parent) $ "AtCoder.Extra.Tree.Hld.ancestor: k-th ancestor is out of the bounds (`k = " ++ show k0 ++ "`)"+    !_ = ACIA.runtimeAssert (0 <= k0 && k0 <= depthHld VG.! parent) $ "AtCoder.Extra.Tree.Hld.ancestor: k-th ancestor is out of bounds (`k = " ++ show k0 ++ "`)"     inner v k       -- on this segment       | k <= iv - ihv = revIndexHld VG.! (iv - k)

@@ -360,7 +360,7 @@ jump :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => Lct (PrimState m) a -> Vertex -> Vertex -> Int -> m Vertex jump lct u v k = stToPrim $ jumpST lct u v k --- | \(O(\log n)\) Returns the LCA of \(u\) and \(v\). Because the root of the underlying changes+-- | \(O(\log n)\) Returns the LCA of \(u\) and \(v\). Because the root of the underlying tree changes -- in almost every operation, one might want to use `evert` beforehand. -- -- ==== Constraints@@ -397,10 +397,10 @@     !_ = ACIA.checkIndex "AtCoder.Extra.Lct.prodPath" v (nLct lct)  -- | Amortized \(O(\log n)\). Fold the subtree under \(v\), considering \(p\) as the root-side--- vertex. Or, if \(p\) equals to \(v\), \(v\) will be the new root.+-- vertex. Or, if \(p\) equals \(v\), \(v\) will be the new root. -- -- ==== Constraints--- - The inverse operator has to be set on consturction (`newInv` or `buildInv`).+-- - The inverse operator has to be set on construction (`newInv` or `buildInv`). -- -- @since 1.1.1.0 {-# INLINE prodSubtree #-}

@@ -17,7 +17,7 @@ -- o--o--o  --> o-x-o-x-o -- @ ----- Idea 2. Assign edge weight to the deeper vertex. The is the internal implementation of+-- Idea 2. Assign edge weight to the deeper vertex. This is the internal implementation of -- `fromEdges` and LCAs are ignored on `prod`: -- -- @@@ -66,7 +66,6 @@ -- >>> let edges = VU.fromList [(0, 1, Sum (1 :: Int)), (1, 2, Sum 2), (2, 3, Sum 3), (1, 4, Sum 4), (4, 5, Sum 5)] -- >>> -- note that the edges must be bi-directed: -- >>> let tree = Gr.build n $ Gr.swapDupe edges--- >>> let hld = Hld.new tree -- >>> let hld = Hld.new tree -- >>> -- note that the edge doesn't have to be bi-directed: -- >>> tm <- TM.fromEdges hld {- `Sum` is commutative -} Commute edges

@@ -31,5 +31,5 @@     )     $ VU.generate (VU.length xs) id --- TODO: maybe add lexical permutations, combinations and subsequences.+-- TODO: maybe add lexicographic permutations, combinations, and subsequences. 

@@ -11,7 +11,7 @@     -- * Constructor     build, -    -- * (Internal) Word-based cumultaive sum+    -- * (Internal) Word-based cumulative sum     wordSize,     csumInPlace, 

@@ -7,7 +7,7 @@ -- NOTE: We could integrate cumulative sum / fenwick tree / segment tree. -- NOTE: `topK` and `intersects` are not implemented as they are slow. --- | A static Wavelet Matrix without automatic index comperssion. Consider using+-- | A static Wavelet Matrix without automatic index compression. Consider using -- @AtCoder.Extra.WaveletMatrix@ instead. -- -- @since 1.1.0.0

@@ -45,7 +45,7 @@   ( -- * Wavelet matrix 2D     WaveletMatrix2d (..), -    -- * Counstructor+    -- * Constructor     new,     build, 

@@ -1,6 +1,6 @@ {-# LANGUAGE RecordWildCards #-} --- | A Fenwick tree, also known as binary indexed tree. Given an array of length \(n\), it processes+-- | A Fenwick tree, also known as a binary indexed tree. Given an array of length \(n\), it processes -- the following queries in \(O(\log n)\) time. -- -- - Updating an element@@ -270,7 +270,7 @@ -- ==== Constraints -- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect. -- - \(f(0)\) returns `True`--- - \(0 \leq l \leq n\)+-- - \(0 \leq r \leq n\) -- -- ==== Complexity -- - \(O(\log n)\)@@ -284,7 +284,7 @@   FenwickTree (PrimState m) a ->   -- | \(r\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> m Bool) ->   -- | \(l\): \(p\) holds for \([l, r)\)   m Int

@@ -356,7 +356,7 @@ errorRect funcName x1 x2 y1 y2 w h =   error $ funcName ++ ": given invalid rectangle `[" ++ show x1 ++ ", " ++ show x2 ++ ") x [" ++ show y1 ++ ", " ++ show y2 ++ ")` for rectangle `[0, " ++ show w ++ ") x [0, " ++ show h ++ ")`" --- | \(O(1)\) Asserts \(x_1 \le x_2\) and \(y_1 \le \y_2\).+-- | \(O(1)\) Asserts \(x_1 \le x_2\) and \(y_1 \le y_2\). -- -- @since 1.2.3.0 {-# INLINE checkRectShape #-}

@@ -25,9 +25,9 @@   ) where --- TODO: faster implmentation+-- TODO: faster implementation --- | \(O(w)\) Returns minimum \(2^i s.t. 2^i \geq n\).+-- | \(O(w)\) Returns minimum \(2^i\) s.t. \(2^i \geq n\). -- -- @since 1.0.0.0 {-# INLINE bitCeil #-}

@@ -15,12 +15,12 @@ -- -- Append elements with `pushBack`: ----- >>> B.pushBack buf 10 -- [10  _  _ _]+-- >>> B.pushBack buf 10 -- [10  _   _  _] -- >>> B.pushBack buf 11 -- [10, 11  _  _] -- >>> length buf -- 2 ----- Access each elements with `read`, `readMaybe`, `write`, `modify` or `modifyM`:+-- Access each element with `read`, `readMaybe`, `write`, `modify` or `modifyM`: -- -- >>> B.read buf 0 -- 10@@ -36,7 +36,7 @@ -- -- >>> B.write buf 1 0   -- [10, 0,  _  _] ----- Remove elements with `pushBack`:+-- Remove elements with `popBack`: -- -- >>> B.popBack buf     -- [10  _  _  _] -- Just 0

@@ -1,6 +1,6 @@ {-# LANGUAGE RecordWildCards #-} --- | Immutable Compresed Sparse Row. It is re-exported from the @AtCoder.Extra.Graph@ module with+-- | Immutable Compressed Sparse Row. It is re-exported from the @AtCoder.Extra.Graph@ module with -- additional functionalities. -- -- ==== __Example__

@@ -90,9 +90,9 @@ {-# INLINEABLE saIsImpl #-} saIsImpl ::   (HasCallStack) =>-  -- | naive threshould+  -- | naive threshold   Int ->-  -- | doubling threshould+  -- | doubling threshold   Int ->   -- | string   VU.Vector Int ->

@@ -1,6 +1,6 @@ {-# LANGUAGE RecordWildCards #-} --- | A lazily propagted segment tree. It is the data structure for the pair of a [monoid](https://en.wikipedia.org/wiki/Monoid)+-- | A lazily propagated segment tree. It is the data structure for the pair of a [monoid](https://en.wikipedia.org/wiki/Monoid) -- \((S, \cdot: S \times S \to S, e \in S)\) and a set \(F\) of \(S \to S\) mappings that satisfies -- the following properties. --@@ -15,8 +15,8 @@ -- - Calculating the product of the elements of an interval -- -- In Haskell types, \(F\) is a `SegAct` (@'segAct' f@) and \(S\) is a `Monoid`. For simplicity, in--- this document, we assume that the relevant methods work in constant time. If these they work in--- \(O(T)\) time, each time complexity appear in this document is multipled by \(O(T)\).+-- this document, we assume that the relevant methods work in constant time. If these work in+-- \(O(T)\) time, each time complexity appear in this document is multiplied by \(O(T)\). -- -- ==== __Example__ -- Here we'll use `AtCoder.Extra.Monoid.Affine1` as a monoid action \(F\) and `Data.Semigroup.Sum`

@@ -264,10 +264,10 @@ edges g = stToPrim $ edgesST g  -- | \(O(1)\) Changes the capacity and the flow amount of the $i$-th edge to @newCap@ and--- @newFlow@, respectively. It oes not change the capacity or the flow amount of other edges.+-- @newFlow@, respectively. It does not change the capacity or the flow amount of other edges. -- -- ==== Constraints--- - \(0 \leq \mathrm{newflow} \leq \mathrm{newcap}\)+-- - \(0 \leq \mathrm{newFlow} \leq \mathrm{newCap}\) -- -- ==== Complexity -- - \(O(1)\)

@@ -236,7 +236,7 @@  -- | Retrieve the mod from a `ModInt` object. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.0.0.0@@ -246,7 +246,7 @@  -- | Returns the internal value in `Int`. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.0.0.0@@ -257,7 +257,7 @@ -- | Returns the internal value as `Word32` without type conversion. It is the function for -- constant-factor speedup. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.0.0.0@@ -267,7 +267,7 @@  -- | Returns the internal value in `Word32`. ----- ==== Complecity+-- ==== Complexity -- - \(O(1)\) -- -- @since 1.0.0.0

@@ -4,8 +4,8 @@ -- \((S, \cdot: S \times S \to S, e \in S)\), i.e., the algebraic structure that satisfies the -- following properties. ----- - associativity: \((a \cdot b) \cdot c\) = \(a \cdot (b \cdot c)\) for all \(a, b, c \in S\)--- - existence of the identity element: \(a \cdot e\) = \(e \cdot a\) = \(a\) for all \(a \in S\)+-- - associativity: \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) for all \(a, b, c \in S\)+-- - existence of the identity element: \(a \cdot e = e \cdot a = a\) for all \(a \in S\) -- -- Given an array \(S\) of length \(N\), it processes the following queries in \(O(\log N)\) time -- (see [Appendix](./appendix.html) for further details).@@ -14,8 +14,8 @@ -- - Calculating the product of the elements of an interval -- -- For simplicity, in this document, we assume that the oracles @op@ and @e@ work in constant time.--- If these oracles work in \(O(T)\) time, each time complexity appear in this document is--- multipled by \(O(T)\).+-- If these oracles work in \(O(T)\) time, each time complexity appearing in this document is+-- multiplied by \(O(T)\). -- -- ==== __Example__ -- Create a `SegTree` of @'Sum' Int@:

@@ -1,6 +1,6 @@ -- | It contains string algorithms. ----- Let \(s\) be a string. We denote the substring of \(s\) between \(a\)-th and \(b - 1\)-th+-- Let \(s\) be a string. We denote the substring of \(s\) between the \(a\)-th and \(b - 1\)-th -- character by \(s[a..b)\). -- -- ==== __Examples__

@@ -13,6 +13,7 @@ import Tests.Extra.DynSparseSegTree.Persistent qualified import Tests.Extra.Graph qualified import Tests.Extra.HashMap qualified+import Tests.Extra.Hld qualified import Tests.Extra.IntMap qualified import Tests.Extra.IntSet qualified import Tests.Extra.IntervalMap qualified@@ -71,6 +72,7 @@             testGroup "DynSparseSegTree.Persistent" Tests.Extra.DynSparseSegTree.Persistent.tests,             testGroup "Graph" Tests.Extra.Graph.tests,             testGroup "HashMap" Tests.Extra.HashMap.tests,+            testGroup "Hld" Tests.Extra.Hld.tests,             testGroup "IntervalMap" Tests.Extra.IntervalMap.tests,             testGroup "Ix0" Tests.Extra.Ix0.tests,             testGroup "IntMap" Tests.Extra.IntMap.tests,

@@ -11,12 +11,7 @@ import Test.Tasty import Test.Tasty.HUnit import Test.Tasty.QuickCheck as QC--genDag :: Int -> QC.Gen (Gr.Csr ())-genDag n = do-  edges <- VU.fromList <$> QC.sublistOf [(u, v) | u <- [0 .. n - 1], v <- [u + 1 .. n - 1]]-  verts <- VU.fromList <$> QC.shuffle [0 .. n - 1]-  pure $ Gr.build n $ VU.map (\(!u, !v) -> (verts VG.! u, verts VG.! v, ())) edges+import Tests.Util (genDag)  reachableFlags :: Int -> (Int -> VU.Vector Int) -> Int -> VU.Vector Bool reachableFlags n gr u0 = VU.create $ do@@ -44,7 +39,7 @@ prop_topSort :: QC.Gen QC.Property prop_topSort = do   n <- QC.chooseInt (1, 3)-  dag <- genDag n+  dag <- genDag @() n   let vs = Gr.topSort n (dag `Gr.adj`)   let perms = map (VU.fromListN n) $ L.permutations [0 .. n - 1]   pure $ vs QC.=== minimum (filter (testTopSort n dag) perms)@@ -89,9 +84,46 @@   let path = Gr.constructPathFromRoot parents 3   path @?= VU.fromList [0, 1, 2, 3] +unit_one :: TestTree+unit_one = testCase "one" $ do+  let !gr = Gr.build @Int 1 VU.empty+  Gr.topSort 1 (Gr.adj gr) @?= VU.singleton 0+  Gr.scc gr @?= V.singleton (VU.singleton 0)+  Gr.rev gr @?= gr+  Gr.findCycleDirected gr @?= Nothing+  Gr.findCycleUndirected gr @?= Nothing+  Gr.connectedComponents 1 (Gr.adj gr) @?= V.singleton (VU.singleton 0)+  (VU.length <$> (Gr.bipartiteVertexColors 1 (Gr.adj gr))) @?= Just 1+  -- Gr.blockCut 1 (Gr.adj gr)+  -- Gr.blockCutComponents 1 (Gr.adj gr)+  Gr.bfs 1 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= (VU.singleton 7)+  Gr.trackingBfs 1 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= (VU.singleton 7, VU.singleton (-1))+  Gr.bfs01 1 0 (Gr.adjW gr) (VU.singleton (0, 7)) @?= (VU.singleton 7)+  Gr.trackingBfs01 1 0 (Gr.adjW gr) (VU.singleton (0, 7)) @?= (VU.singleton 7, VU.singleton (-1))+  Gr.dijkstra 1 0 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= (VU.singleton 7)+  Gr.trackingDijkstra 1 0 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= (VU.singleton 7, VU.singleton (-1))+  Gr.bellmanFord 1 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= Just (VU.singleton 7)+  Gr.trackingBellmanFord 1 (Gr.adjW gr) (-1 :: Int) (VU.singleton (0, 7)) @?= Just (VU.singleton 7, VU.singleton (-1))+  Gr.floydWarshall 1 VU.empty (maxBound `div` 2 :: Int) @?= VU.singleton 0+  Gr.trackingFloydWarshall 1 VU.empty (maxBound `div` 2 :: Int) @?= (VU.singleton 0, VU.singleton (-1))+  (!fw, !prev) <- Gr.newTrackingFloydWarshall 1 VU.empty (maxBound `div` 2 :: Int)+  let test = do+        fw' <- VU.unsafeFreeze fw+        prev' <- VU.unsafeFreeze prev+        (fw', prev') @?= (VU.singleton 0, VU.singleton (-1))+  test+  -- add positive self-loop edge+  Gr.updateEdgeFloydWarshall fw 1 (maxBound `div` 2) 0 0 1+  test+  -- add negative self-loop edge+  Gr.updateEdgeFloydWarshall fw 1 (maxBound `div` 2) 0 0 (-1)+  {- TODO: write test here -}+  pure ()+ tests :: [TestTree] tests =   [ QC.testProperty "topSort" prop_topSort,     -- not writing much tests, as we have verification problems-    QC.testProperty "floydWarshall" prop_floydWarshall+    QC.testProperty "floydWarshall" prop_floydWarshall,+    unit_one   ]

@@ -0,0 +1,36 @@+module Tests.Extra.Hld where++import AtCoder.Extra.Graph qualified as Gr+import AtCoder.Extra.Tree.Hld qualified as Hld+import AtCoder.Extra.Tree.TreeMonoid qualified as Tm+import Data.Monoid (Sum (..))+import Data.Vector.Unboxed qualified as VU+import Test.Tasty+import Test.Tasty.HUnit++unit_one :: TestTree+unit_one = testCase "one" $ do+  let hld = Hld.new $ Gr.build @() 1 VU.empty+  (@?= 0) $ Hld.lca hld 0 0+  (@?= 0) $ Hld.ancestor hld 0 0+  (@?= Just 0) $ Hld.jump hld 0 0 0+  (@?= 0) $ Hld.lengthBetween hld 0 0+  (@?= [0]) $ Hld.path hld 0 0+  (@?= [(0, 0)]) $ Hld.pathSegmentsInclusive Hld.WeightsAreOnVertices hld 0 0+  (@?= []) $ Hld.pathSegmentsInclusive Hld.WeightsAreOnEdges hld 0 0+  (@?= (0, 0)) $ Hld.subtreeSegmentInclusive hld 0+  (@?= True) $ Hld.isInSubtree hld 0 0++  tm <- Tm.fromVerts hld Tm.Commute (VU.singleton (Sum (1 :: Int)))+  (@?= Sum 1) =<< Tm.prod tm 0 0+  (@?= Sum 1) =<< Tm.read tm 0+  Tm.write tm 0 $ Sum 2+  (@?= Sum 2) =<< Tm.exchange tm 0 (Sum 3)+  Tm.modify tm (+ (Sum 1)) 0+  (@?= Sum 4) =<< Tm.read tm 0+  (@?= Sum 4) =<< Tm.prod tm 0 0++tests :: [TestTree]+tests =+  [ unit_one+  ]

@@ -9,14 +9,10 @@ import Data.List qualified as L import Data.Map qualified as M import Data.Maybe (fromMaybe)-import Data.Ord (comparing) import Data.Semigroup (Sum (..))-import Data.Vector.Algorithms.Intro qualified as VAI import Data.Vector.Unboxed qualified as VU-import Test.Hspec import Test.QuickCheck.Monadic as QCM import Test.Tasty-import Test.Tasty.HUnit import Test.Tasty.QuickCheck as QC import Tests.Util (intervalGen) 

@@ -20,7 +20,6 @@ import Test.Tasty import Test.Tasty.HUnit import Test.Tasty.Hspec-import Util (DoNotUnboxLazy (..))  data SegTreeNaive s a = SegTreeNaive   { nStn :: {-# UNPACK #-} !Int,@@ -71,7 +70,7 @@ freezeStn :: (Monoid a, VU.Unbox a, PrimMonad m) => SegTreeNaive (PrimState m) a -> m (VU.Vector a) freezeStn = VU.freeze . dStn -type FooRepr = DoNotUnboxLazy String+type FooRepr = VU.DoNotUnboxStrict String  newtype Foo = Foo String   deriving (Eq, Ord, Show)@@ -90,9 +89,9 @@  instance VU.IsoUnbox Foo FooRepr where   {-# INLINE toURepr #-}-  toURepr (Foo s) = DoNotUnboxLazy s+  toURepr (Foo s) = VU.DoNotUnboxStrict s   {-# INLINE fromURepr #-}-  fromURepr (DoNotUnboxLazy s) = Foo s+  fromURepr (VU.DoNotUnboxStrict s) = Foo s  newtype instance VU.MVector s Foo = MV_Foo (VU.MVector s FooRepr) 

@@ -1,7 +1,25 @@-module Tests.Util (myForAllShrink, laws, intervalGen, intervalGen') where+module Tests.Util+  ( myForAllShrink,+    laws,+    intervalGen,+    intervalGen',+    Dag (..),+    genDag,+    Tree (..),+    genTree,+  )+where +import AtCoder.Extra.Graph qualified as Gr+import AtCoder.Internal.Assert qualified as ACIA+import Data.Foldable (for_)+import Data.Maybe (fromJust) import Data.Proxy (Proxy (..)) import Data.Typeable (Typeable, typeRep)+import Data.Vector.Generic qualified as VG+import Data.Vector.Generic.Mutable qualified as VGM+import Data.Vector.Unboxed qualified as VU+import Data.Vector.Unboxed.Mutable qualified as VUM import Test.QuickCheck.Classes qualified as QCC import Test.QuickCheck.Property qualified as QC import Test.Tasty@@ -51,3 +69,68 @@   l <- QC.chooseInt (xl, xr)   r <- QC.chooseInt (l, xr)   pure (l, r)++genDag :: forall w. (QC.Arbitrary w, VU.Unbox w) => Int -> QC.Gen (Gr.Csr w)+genDag n = do+  edges <- VU.fromList <$> QC.sublistOf [(u, v) | u <- [0 .. n - 1], v <- [u + 1 .. n - 1]]+  verts <- VU.fromList <$> QC.shuffle [0 .. n - 1]+  ws <- VU.fromList <$> QC.vectorOf n (QC.arbitrary @w)+  let es = VU.zipWith (\(!u, !v) !w -> (verts VG.! u, verts VG.! v, w)) edges ws+  pure $ Gr.build n es++-- | Newtype for generating a random DAG.+newtype Dag w = Dag (Gr.Csr w)++instance (QC.Arbitrary w, VU.Unbox w) => QC.Arbitrary (Dag w) where+  arbitrary = do+    QC.Positive n <- QC.arbitrary+    Dag <$> genDag n++-- TODO: commit the upper code first++-- | Prüfer sequence: https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence+genTreeEdge :: Int -> QC.Gen (VU.Vector (Int, Int))+genTreeEdge n = case n of+  1 -> pure VU.empty+  2 -> pure $ VU.singleton (0, 1)+  _ -> do+    prufer <- QC.vectorOf (n - 2) (QC.chooseInt (0, n - 1))+    pure $ VU.create $ do+      -- sum(deg) = n + (n - 2) at the beginning+      deg <- VUM.replicate n (1 :: Int)+      for_ prufer $ \v -> do+        VGM.modify deg (+ 1) v++      edges <- VUM.unsafeNew (n - 1)++      -- sum(deg) will be 2(n - 1) - 2(n - 2) = 2+      for_ (zip [0 :: Int ..] prufer) $ \(!i, !u) -> do+        -- NOTE: At the beginning, deg[u] > 1, and deg[i] is never decreaesed until iterated+        !v <- fromJust . VU.findIndex (== 1) <$> VU.unsafeFreeze deg+        -- So we're sure u /= v+        let !_ = ACIA.runtimeAssert (u /= v) "u /= v"+        VGM.write edges i (u, v)+        VGM.modify deg (subtract 1) u+        VGM.modify deg (subtract 1) v++      -- The last two vertices with degree one make up the last edge+      uv <- VU.findIndices (== 1) <$> VU.unsafeFreeze deg+      let !_ = ACIA.runtimeAssert (VU.length uv == 2) "not found uv?"+      VGM.write edges (n - 1) (uv VG.! 0, uv VG.! 1)++      -- done+      pure edges++genTree :: forall w. (QC.Arbitrary w, VU.Unbox w) => Int -> QC.Gen (Gr.Csr w)+genTree n = do+  es <- genTreeEdge n+  ws <- VU.fromList <$> QC.vectorOf (n - 1) (QC.arbitrary @w)+  pure . Gr.build n . Gr.swapDupe $ VU.zipWith (\(!u, !v) !w -> (u, v, w)) es ws++-- | Newtype for generating a random tree.+newtype Tree w = Tree (Gr.Csr w)++instance (QC.Arbitrary w, VU.Unbox w) => QC.Arbitrary (Tree w) where+  arbitrary = do+    QC.Positive n <- QC.arbitrary+    Tree <$> genTree n

@@ -1,97 +0,0 @@-{-# LANGUAGE TypeFamilies #-}---- | For compatibility. FIXME: Remove with latest vector-module Util (DoNotUnboxLazy (..)) where--import Data.Coerce (coerce)-import Data.Vector qualified as V-import Data.Vector.Generic qualified as VG-import Data.Vector.Generic.Mutable qualified as VGM-import Data.Vector.Mutable qualified as VM-import Data.Vector.Unboxed qualified as VU-import Data.Vector.Unboxed.Mutable qualified as VUM---- | Newtype which allows to derive unbox instances for type @a@ which--- is normally a "boxed" type. The newtype does not alter the strictness--- semantics of the underlying type and inherits the laizness of said type.--- For a strict newtype wrapper, see 'DoNotUnboxStrict'.------ 'DoNotUnboxLazy' is intended to be unsed in conjunction with the newtype 'As'--- and the type class 'IsoUnbox'. Here's an example which uses the following--- explicit 'IsoUnbox' instance:--------- >>> :set -XTypeFamilies -XStandaloneDeriving -XDerivingVia--- >>> :set -XMultiParamTypeClasses -XTypeOperators -XFlexibleInstances--- >>> import qualified Data.Vector.Unboxed         as VU--- >>> import qualified Data.Vector.Unboxed.Mutable as VUM--- >>> import qualified Data.Vector.Generic         as VG--- >>> import qualified Data.Vector.Generic.Mutable as VGM--- >>> :{--- >>> data Foo a = Foo Int a--- >>>   deriving (Eq, Ord, Show)--- >>> instance VU.IsoUnbox (Foo a) (Int, VU.DoNotUnboxLazy a) where--- >>>   toURepr (Foo i a) = (i, VU.DoNotUnboxLazy a)--- >>>   fromURepr (i, VU.DoNotUnboxLazy a) = Foo i a--- >>>   {-# INLINE toURepr #-}--- >>>   {-# INLINE fromURepr #-}--- >>> newtype instance VU.MVector s (Foo a) = MV_Foo (VU.MVector s (Int, VU.DoNotUnboxLazy a))--- >>> newtype instance VU.Vector    (Foo a) = V_Foo  (VU.Vector    (Int, VU.DoNotUnboxLazy a))--- >>> deriving via (Foo a `VU.As` (Int, VU.DoNotUnboxLazy a)) instance VGM.MVector VUM.MVector (Foo a)--- >>> deriving via (Foo a `VU.As` (Int, VU.DoNotUnboxLazy a)) instance VG.Vector   VU.Vector   (Foo a)--- >>> instance VU.Unbox (Foo a)--- >>> :}------ >>> VU.fromListN 3 [ Foo 4 "Haskell's", Foo 8 "strong", Foo 16 "types" ]--- [Foo 4 "Haskell's",Foo 8 "strong",Foo 16 "types"]------ @since 0.13.2.0-newtype DoNotUnboxLazy a = DoNotUnboxLazy a--newtype instance VUM.MVector s (DoNotUnboxLazy a) = MV_DoNotUnboxLazy (VM.MVector s a)--newtype instance VU.Vector (DoNotUnboxLazy a) = V_DoNotUnboxLazy (V.Vector a)--instance VGM.MVector VUM.MVector (DoNotUnboxLazy a) where-  {-# INLINE basicLength #-}-  {-# INLINE basicUnsafeSlice #-}-  {-# INLINE basicOverlaps #-}-  {-# INLINE basicUnsafeNew #-}-  {-# INLINE basicInitialize #-}-  {-# INLINE basicUnsafeReplicate #-}-  {-# INLINE basicUnsafeRead #-}-  {-# INLINE basicUnsafeWrite #-}-  {-# INLINE basicClear #-}-  {-# INLINE basicSet #-}-  {-# INLINE basicUnsafeCopy #-}-  {-# INLINE basicUnsafeGrow #-}-  basicLength = coerce $ VGM.basicLength @V.MVector @a-  basicUnsafeSlice = coerce $ VGM.basicUnsafeSlice @V.MVector @a-  basicOverlaps = coerce $ VGM.basicOverlaps @V.MVector @a-  basicUnsafeNew = coerce $ VGM.basicUnsafeNew @V.MVector @a-  basicInitialize = coerce $ VGM.basicInitialize @V.MVector @a-  basicUnsafeReplicate = coerce $ VGM.basicUnsafeReplicate @V.MVector @a-  basicUnsafeRead = coerce $ VGM.basicUnsafeRead @V.MVector @a-  basicUnsafeWrite = coerce $ VGM.basicUnsafeWrite @V.MVector @a-  basicClear = coerce $ VGM.basicClear @V.MVector @a-  basicSet = coerce $ VGM.basicSet @V.MVector @a-  basicUnsafeCopy = coerce $ VGM.basicUnsafeCopy @V.MVector @a-  basicUnsafeMove = coerce $ VGM.basicUnsafeMove @V.MVector @a-  basicUnsafeGrow = coerce $ VGM.basicUnsafeGrow @V.MVector @a--instance VG.Vector VU.Vector (DoNotUnboxLazy a) where-  {-# INLINE basicUnsafeFreeze #-}-  {-# INLINE basicUnsafeThaw #-}-  {-# INLINE basicLength #-}-  {-# INLINE basicUnsafeSlice #-}-  {-# INLINE basicUnsafeIndexM #-}-  {-# INLINE elemseq #-}-  basicUnsafeFreeze = coerce $ VG.basicUnsafeFreeze @V.Vector @a-  basicUnsafeThaw = coerce $ VG.basicUnsafeThaw @V.Vector @a-  basicLength = coerce $ VG.basicLength @V.Vector @a-  basicUnsafeSlice = coerce $ VG.basicUnsafeSlice @V.Vector @a-  basicUnsafeIndexM = coerce $ VG.basicUnsafeIndexM @V.Vector @a-  basicUnsafeCopy = coerce $ VG.basicUnsafeCopy @V.Vector @a-  elemseq _ = seq--instance VU.Unbox (DoNotUnboxLazy a)