ac-library-hs 1.5.2.0 → 1.5.2.1

raw patch · 88 files changed

+180/−177 lines, 88 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• ac-library-hs.cabal +2/−2
• benchmarks/Bench/AddMod.hs +1/−2
• benchmarks/Bench/Matrix.hs +1/−0
• benchmarks/Bench/ModInt.hs +2/−5
• benchmarks/Bench/PowMod.hs +2/−1
• benchmarks/Bench/RepeatWithIndex.hs +2/−2
• benchmarks/Bench/RepeatWithoutIndex.hs +2/−2
• benchmarks/Bench/Vector/ConcatMapM.hs +1/−1
• benchmarks/Bench/Vector/IConcatMapM.hs +1/−1
• benchmarks/BenchLib/AddMod.hs +2/−2
• benchmarks/BenchLib/MulMod/Montgomery.hs +2/−2
• examples/LazySegTree.hs +3/−5
• examples/README.md +6/−3
• src/AtCoder/Extra/DynLazySegTree/Raw.hs +3/−3
• src/AtCoder/Extra/DynSegTree.hs +1/−1
• src/AtCoder/Extra/DynSegTree/Raw.hs +2/−2
• src/AtCoder/Extra/DynSparseSegTree.hs +3/−3
• src/AtCoder/Extra/DynSparseSegTree/Persistent.hs +4/−4
• src/AtCoder/Extra/DynSparseSegTree/Raw.hs +2/−2
• src/AtCoder/Extra/Graph.hs +4/−4
• src/AtCoder/Extra/HashMap.hs +1/−1
• src/AtCoder/Extra/IntMap.hs +1/−1
• src/AtCoder/Extra/IntSet.hs +1/−1
• src/AtCoder/Extra/IntervalMap.hs +2/−2
• src/AtCoder/Extra/KdTree.hs +2/−2
• src/AtCoder/Extra/LazyKdTree.hs +4/−4
• src/AtCoder/Extra/Math.hs +6/−6
• src/AtCoder/Extra/Math/Montgomery64.hs +4/−5
• src/AtCoder/Extra/ModInt64.hs +2/−1
• src/AtCoder/Extra/Monoid/Mat2x2.hs +1/−1
• src/AtCoder/Extra/Monoid/RollingHash.hs +1/−1
• src/AtCoder/Extra/MultiSet.hs +1/−1
• src/AtCoder/Extra/Pdsu.hs +3/−3
• src/AtCoder/Extra/Pool.hs +1/−1
• src/AtCoder/Extra/SegTree2d/Dense.hs +2/−2
• src/AtCoder/Extra/Seq.hs +1/−1
• src/AtCoder/Extra/Seq/Map.hs +1/−1
• src/AtCoder/Extra/Seq/Raw.hs +2/−2
• src/AtCoder/Extra/SqrtDecomposition.hs +1/−1
• src/AtCoder/Extra/Tree.hs +1/−1
• src/AtCoder/Extra/Tree/Hld.hs +3/−3
• src/AtCoder/Extra/Tree/Lct.hs +2/−2
• src/AtCoder/Extra/Tree/TreeMonoid.hs +1/−1
• src/AtCoder/Extra/Vector.hs +1/−1
• src/AtCoder/Extra/Vector/Prim.hs +4/−2
• src/AtCoder/Extra/WaveletMatrix.hs +1/−1
• src/AtCoder/Extra/WaveletMatrix/Raw.hs +1/−1
• src/AtCoder/Extra/WaveletMatrix2d.hs +1/−1
• src/AtCoder/FenwickTree.hs +2/−2
• src/AtCoder/Internal/Assert.hs +6/−6
• src/AtCoder/Internal/Buffer.hs +1/−1
• src/AtCoder/Internal/Csr.hs +1/−1
• src/AtCoder/Internal/GrowVec.hs +1/−1
• src/AtCoder/Internal/McfCsr.hs +1/−1
• src/AtCoder/Internal/Queue.hs +2/−2
• src/AtCoder/MaxFlow.hs +1/−1
• src/AtCoder/MinCostFlow.hs +3/−3
• src/AtCoder/SegTree.hs +6/−6
• src/AtCoder/String.hs +2/−2
• test/Tests/Convolution.hs +1/−1
• test/Tests/Extra/DynLazySegTree.hs +1/−1
• test/Tests/Extra/DynLazySegTree/Persistent.hs +1/−1
• test/Tests/Extra/DynSegTree.hs +1/−1
• test/Tests/Extra/DynSegTree/Persistent.hs +1/−1
• test/Tests/Extra/DynSparseSegTree.hs +1/−1
• test/Tests/Extra/DynSparseSegTree/Persistent.hs +1/−1
• test/Tests/Extra/HashMap.hs +2/−2
• test/Tests/Extra/IntMap.hs +2/−2
• test/Tests/Extra/IntSet.hs +2/−2
• test/Tests/Extra/IntervalMap.hs +1/−1
• test/Tests/Extra/KdTree.hs +7/−5
• test/Tests/Extra/LazyKdTree.hs +2/−2
• test/Tests/Extra/MultiSet.hs +1/−1
• test/Tests/Extra/SegTree2d.hs +1/−1
• test/Tests/Extra/SegTree2d/Dense.hs +1/−1
• test/Tests/Extra/Semigroup/Matrix.hs +1/−1
• test/Tests/Extra/Seq.hs +2/−2
• test/Tests/Extra/Seq/Map.hs +5/−5
• test/Tests/Extra/Tree/Lct.hs +1/−1
• test/Tests/Extra/WaveletMatrix.hs +6/−6
• test/Tests/Extra/WaveletMatrix/Raw.hs +6/−6
• test/Tests/Extra/WaveletMatrix2d.hs +1/−1
• test/Tests/Internal/Bit.hs +2/−2
• test/Tests/Internal/Math.hs +2/−2
• test/Tests/Math.hs +1/−1
• test/Tests/ModInt.hs +1/−1
• test/Tests/TwoSat.hs +1/−1
• test/Tests/Util.hs +1/−1

@@ -4,7 +4,7 @@ -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version:         1.5.2.0+version:         1.5.2.1 synopsis:        Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive@@ -39,8 +39,8 @@     , bitvec             <1.2     , bytestring         <0.14     , primitive          >=0.6.4.0 && <0.10-    , transformers       >= 0.2.0.0     , random             >=1.2.0   && <1.3+    , transformers       >=0.2.0.0     , vector             >=0.13.0  && <0.14     , vector-algorithms  <0.10     , wide-word          <0.2

@@ -16,8 +16,7 @@ benches =   bgroup     "addMod"-    [-      bench "addModMod" $ whnf (VU.foldl' (addModMod 998244353) w32) randomVec32,+    [ bench "addModMod" $ whnf (VU.foldl' (addModMod 998244353) w32) randomVec32,       bench "addModRem" $ whnf (VU.foldl' (addModRem 998244353) w32) randomVec32,       bench "addModSub" $ whnf (VU.foldl' (addModSub 998244353) w32) randomVec32,       bench "addModRem#" $ whnf (VU.foldl' (addModRem# 998244353) w32) randomVec32,

@@ -1,4 +1,5 @@ {-# LANGUAGE DataKinds #-}+ module Bench.Matrix (benches) where  import AtCoder.Extra.Math qualified as ACEM

@@ -1,8 +1,8 @@ module Bench.ModInt (benches) where  import AtCoder.ModInt qualified as M-import BenchLib.PowMod qualified as PowMod import BenchLib.ModInt.ModIntNats qualified as MN+import BenchLib.PowMod qualified as PowMod import Criterion import Data.Vector.Unboxed qualified as VU import System.Random@@ -11,13 +11,10 @@ benches =   bgroup     "modInt"-    [--    ]+    []   where     n = 10000     randomVec :: VU.Vector Int     randomVec =       VU.map fromIntegral $         VU.unfoldrExactN n (genWord64R (998244383 - 2)) (mkStdGen 123456789)-

@@ -1,9 +1,10 @@ {-# LANGUAGE DataKinds #-}+ module Bench.PowMod (benches) where  import AtCoder.ModInt qualified as M-import BenchLib.PowMod qualified as PowMod import BenchLib.ModInt.ModIntNats qualified as MN+import BenchLib.PowMod qualified as PowMod import Criterion import Data.Vector.Unboxed qualified as VU import System.Random

@@ -1,9 +1,9 @@ -- | Benchmark for monadic streams. module Bench.RepeatWithIndex (benches) where -import Criterion-import Control.Monad (when, replicateM_)+import Control.Monad (replicateM_, when) import Control.Monad.ST (runST)+import Criterion import Data.Foldable (for_) import Data.Vector.Fusion.Stream.Monadic qualified as MS import Data.Vector.Generic.Mutable as VGM

@@ -1,9 +1,9 @@ -- | Benchmark for monadic streams. module Bench.RepeatWithoutIndex (benches) where -import Criterion-import Control.Monad (when, replicateM_)+import Control.Monad (replicateM_, when) import Control.Monad.ST (runST)+import Criterion import Data.Foldable (for_) import Data.Vector.Fusion.Stream.Monadic qualified as MS import Data.Vector.Generic.Mutable as VGM

@@ -3,8 +3,8 @@ import BenchLib.Vector.ConcatMapM qualified as ConcatMapM import Control.Monad.Primitive (PrimMonad) import Control.Monad.ST (runST)-import Control.Monad.Trans.State.Strict (StateT (..), evalState, evalStateT) import Control.Monad.State.Class (MonadState, modify')+import Control.Monad.Trans.State.Strict (StateT (..), evalState, evalStateT) import Criterion import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM

@@ -3,8 +3,8 @@ import BenchLib.Vector.ConcatMapM qualified as ConcatMapM import Control.Monad.Primitive (PrimMonad) import Control.Monad.ST (runST)-import Control.Monad.Trans.State.Strict (State (..), StateT (..), evalState, evalStateT) import Control.Monad.State.Class (MonadState, modify')+import Control.Monad.Trans.State.Strict (State (..), StateT (..), evalState, evalStateT) import Criterion import Data.Vector.Fusion.Bundle.Monadic qualified as BundleM import Data.Vector.Generic qualified as VG

@@ -60,12 +60,12 @@ -- addMod3 :: Word32 -> Word32 -> Word32 -> Word32 -- addMod3 (W32# m#) (W32# x#) (W32# y#) = case x# `plusWord32#` y# of --   r# -> W32# (r# `subWord32#` ((r# `geWord32#` m#) `timesWord32#` m#))--- +-- -- {-# INLINE addMod4 #-} -- addMod4 :: Word32 -> Word32 -> Word32 -> Word32 -- addMod4 (W32# m#) (W32# x#) (W32# y#) = case x# plusWord32# y# of --   r# -> W32# (r# -# (m# *# (r# >=# m#)))--- +-- -- {-# INLINE addMod5 #-} -- addMod5 :: Word32 -> Word32 -> Word32 -> Word32 -- addMod5 (W32# m#) (W32# x#) (W32# y#) = W32# (x# plusWord32# y# -# (m# *# (x# plusWord32# y# >=# m#)))

@@ -40,8 +40,8 @@     inner !negInv 32 !_ !_ = negInv     inner !negInv !i !s !t       -- REMARK: `!>>.` does not work here.-      -- | even t = inner (negInv + s) (i + 1) (2 * s) ((t + m) !>>. 2)-      -- | otherwise = inner negInv (i + 1) (2 * s) (t !>>. 2)+      -- \| even t = inner (negInv + s) (i + 1) (2 * s) ((t + m) !>>. 2)+      -- \| otherwise = inner negInv (i + 1) (2 * s) (t !>>. 2)       | even t = inner (negInv + s) (i + 1) (2 * s) ((t + m) `div` 2)       | otherwise = inner negInv (i + 1) (2 * s) (t `div` 2) 

@@ -1,11 +1,10 @@ -- This is a possible template of LazySegTree monoid instances for AtCoder contests. -- This code is copy-pasted to the lazy segtree document's example.- {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE TypeFamilies #-} -import AtCoder.LazySegTree qualified as LST import AtCoder.LazySegTree (SegAct (..))+import AtCoder.LazySegTree qualified as LST import Data.Vector.Generic qualified as VG import Data.Vector.Generic.Mutable qualified as VGM import Data.Vector.Unboxed qualified as VU@@ -36,7 +35,7 @@ -- | Acted `Int` (same as `Sum Int`). type XRepr = Int -deriving instance Num X; -- in our case `X` is a `Num`.+deriving instance Num X -- in our case `X` is a `Num`.  instance Semigroup X where   {-# INLINE (<>) #-}@@ -68,11 +67,10 @@   seg <- LST.build @_ @F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]   LST.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]   LST.write seg 3 $ X 10 -- [1, 5, 7, 10]-  LST.modify seg (+ (X 1)) 0   -- [2, 5, 7, 10]+  LST.modify seg (+ (X 1)) 0 -- [2, 5, 7, 10]   !_ <- (expect "test 1" (X 5)) <$> LST.read seg 1   !_ <- (expect "test 2" (X 14)) <$> LST.prod seg 0 3 -- reads an interval [0, 3)   !_ <- (expect "test 3" (X 24)) <$> LST.allProd seg   !_ <- (expect "test 4" 2) <$> LST.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10   !_ <- (expect "test 5" 3) <$> LST.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10   putStrLn "=> test passed!"-

@@ -9,7 +9,10 @@  ## Other examples -- See documentation page for most examples.-- See `verify/` directroy under the repository root for [AtCoder Library Practice Contest](https://atcoder.jp/contests/practice2) problem solutions.-- See `test/` directroy under the repository root for test code.+- See [Hackage API documentation](https://hackage.haskell.org/package/ac-library-hs) for most examples.+- See `:/verify/` for problem solutions. It contains+  - [AtCoder Library Practice Contest](https://atcoder.jp/contests/practice2) problem solutions.+  - [Library Checker](https://judge.yosupo.jp/) (Yosupo) problem solutions.+  - [Aizu Online Judge](https://judge.u-aizu.ac.jp/onlinejudge/) (AOJ) problem solutions.+- See `:/test/` for test code. 

@@ -56,7 +56,7 @@ import Prelude hiding (read)  -- | A dynamic, lazily propagated segment tree that covers a half-open interval \([l_0, r_0)\).--- The nodes are instantinated as needed.+-- The nodes are instantiated as needed. -- -- @since 1.2.1.0 data DynLazySegTree s f a = DynLazySegTree@@ -170,7 +170,7 @@ {-# INLINE newNodeInST #-} newNodeInST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> Int -> Int -> ST s P.Index newNodeInST dst@DynLazySegTree {initialProdLdst} l r = do-  let !_ = ACIA.runtimeAssert (r > l) $ "AtCoder.Extra.DynLazySegTree.Raw.nodeNodeInST: not empty or negative interval: " ++ show (l, r)+  let !_ = ACIA.runtimeAssert (r > l) $ "AtCoder.Extra.DynLazySegTree.Raw.newNodeInST: not empty or negative interval: " ++ show (l, r)   newNodeST dst $! initialProdLdst l r  -- | \(O(\log L)\)@@ -397,7 +397,7 @@   | ql0 == qr0 = pure root   | P.nullIndex root = pure P.undefIndex   | ql0 == l0Ldst && qr0 == r0Ldst = do-      -- for the case of non-persistent segment tere, we should update the root in-place:+      -- for the case of non-persistent segment tree, we should update the root in-place:       root' <- cloneOnWriteST dst root       VGM.write xLdst (coerce root') $! initialProdLdst l0Ldst r0Ldst       VGM.write lLdst (coerce root') P.undefIndex

@@ -92,7 +92,7 @@   Int ->   -- | Right index boundary \(r_0\)   Int ->-  -- | Dynamic propagated segment tree+  -- | Dynamic segment tree   m (Raw.DynSegTree (PrimState m) a) new nDst l r = stToPrim $ Raw.newST False nDst l r (\_ _ -> mempty) 

@@ -156,7 +156,7 @@ {-# INLINE newNodeInST #-} newNodeInST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSegTree s a -> Int -> Int -> ST s P.Index newNodeInST dst@DynSegTree {initialProdDst} l r = do-  let !_ = ACIA.runtimeAssert (r > l) $ "AtCoder.Extra.DynSegTree.Raw.nodeNodeInST: not empty or negative interval: " ++ show (l, r)+  let !_ = ACIA.runtimeAssert (r > l) $ "AtCoder.Extra.DynSegTree.Raw.newNodeInST: not empty or negative interval: " ++ show (l, r)   newNodeST dst $! initialProdDst l r  -- | \(O(\log L)\)@@ -257,7 +257,7 @@   | ql0 == qr0 = pure root   | P.nullIndex root = pure P.undefIndex   | ql0 == l0Dst && qr0 == r0Dst = do-      -- for the case of non-persistent segment tere, we should update the root in-place:+      -- for the case of non-persistent segment tree, we should update the root in-place:       root' <- cloneOnWriteST dst root       VGM.write xDst (coerce root') $! initialProdDst l0Dst r0Dst       VGM.write lDst (coerce root') P.undefIndex

@@ -3,8 +3,8 @@ {-# LANGUAGE TypeFamilies #-}  -- | A dynamic, sparse segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are--- instantinated as needed, with the required capacity being \(q\), where \(q\) is the number of--- mutable operations. The traid-off compared to the non-sparse variant is that initial monoid+-- instantiated as needed, with the required capacity being \(q\), where \(q\) is the number of+-- mutable operations. The trade-off compared to the non-sparse variant is that initial monoid -- values are fixed at `mempty`. -- -- ==== __Example__@@ -189,7 +189,7 @@   root <- VGM.read handle 0   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,9 +2,9 @@ {-# LANGUAGE NamedFieldPuns #-} {-# LANGUAGE TypeFamilies #-} --- | A dynamic, sparse, persitent segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are--- instantinated as needed, with the required capacity being \(2q \log_2 L\), where \(q\) is the number of--- mutable operations. The traid-off compared to the non-sparse variant is that initial monoid+-- | A dynamic, sparse, persistent segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are+-- instantiated as needed, with the required capacity being \(2q \log_2 L\), where \(q\) is the number of+-- mutable operations. The trade-off compared to the non-sparse variant is that initial monoid -- values are fixed at `mempty`. -- -- ==== __Example__@@ -172,7 +172,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 #-}

@@ -44,8 +44,8 @@ import GHC.Stack (HasCallStack) import Prelude hiding (read) --- | A dynamic, sparse 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, sparse 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 DynSparseSegTree s a = DynSparseSegTree

@@ -379,7 +379,7 @@       -- This is not optimal, but we need a dedicated `buildUndirected` function and different edge ID       -- (not index) handling in CSR if we go with the optimal approach.       ---      --  Note that the implementations are suspecious..+      --  Note that the implementations are suspicious..       findCycleComplexUndirected gr <|> findCycleSimpleUndirected gr  {-# INLINEABLE findCycleComplexUndirected #-}@@ -473,7 +473,7 @@   es <- GV.new @_ @Int 16   dep' <- VU.unsafeFreeze dep -  -- Find edge with minimum depth difference, which makes up a loop (not used in the DFS forets):+  -- Find edge with minimum depth difference, which makes up a loop (not used in the DFS forests):   minLen <- VUM.replicate 1 (maxBound `div` 2 :: Int)   backE <- VUM.replicate 1 (-1 :: Int, -1 :: Int)   for_ [0 .. nCsr - 1] $ \vA -> do@@ -1308,7 +1308,7 @@       VGM.write dist v w   updated <- VUM.replicate 1 False -  -- look around adjaenct vertices+  -- look around adjacent vertices   let update v1 = do         d1 <- VGM.read dist v1         when (d1 /= undefW) $ do@@ -1603,7 +1603,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 chaneg or new edge addition.+-- | \(O(n^2)\) Updates distance matrix of Floyd–Warshall on edge weight change or new edge addition. -- -- ==== Constraints -- - \(n \ge 1\)

@@ -1,6 +1,6 @@ {-# LANGUAGE RecordWildCards #-} --- original implementaion:+-- original implementation: -- <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

@@ -47,7 +47,7 @@     member,     notMember, -    -- ** Compartive lookups+    -- ** Comparative lookups     lookupGE,     lookupGT,     lookupLE,

@@ -48,7 +48,7 @@     member,     notMember, -    -- ** Compartive lookups+    -- ** Comparative lookups     lookupGE,     lookupGT,     lookupLE,

@@ -8,8 +8,8 @@ -- changes during `buildM`, `insertM` and `deleteM` operations. -- -- ==== Invariant--- Each interval is operated as a whole, similar to a persistant data structure. When part of an--- inerval is modified, the whole interval is deleted first, and the subintervals are re-inserted.+-- Each interval is operated as a whole, similar to a persistent data structure. When part of an+-- interval is modified, the whole interval is deleted first, and the subintervals are re-inserted. -- It's important for tracking non-linear interval information with the @onAdd@ and @onDel@ hooks -- (callbacks). --

@@ -69,9 +69,9 @@ {-# INLINEABLE build #-} build ::   (HasCallStack) =>-  -- | \(x\) coordnates+  -- | \(x\) coordinates   VU.Vector Int ->-  -- | \(y\) coordnates+  -- | \(y\) coordinates   VU.Vector Int ->   -- | `KdTree`   KdTree

@@ -116,9 +116,9 @@ {-# INLINE new #-} new ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>-  -- | \(x\) coordnates.+  -- | \(x\) coordinates.   VU.Vector Int ->-  -- | \(y\) coordnates.+  -- | \(y\) coordinates.   VU.Vector Int ->   -- | `LazyKdTree`.   m (LazyKdTree (PrimState m) f a)@@ -133,9 +133,9 @@ {-# INLINE build #-} build ::   (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Semigroup a, VU.Unbox a) =>-  -- | \(x\) coordnates.+  -- | \(x\) coordinates.   VU.Vector Int ->-  -- | \(y\) coordnates.+  -- | \(y\) coordinates.   VU.Vector Int ->   -- | monoid \(v\)alues.   VU.Vector a ->

@@ -102,7 +102,7 @@       let !maxPrimeCount :: Int             -- NOTE: 1,700 is a point where the next function estimates better as far as I tested:             | limit < 1700 = round (1.25506 * fromIntegral limit / log (fromIntegral limit) :: Double)-            -- Rosser and Schoenfeld Boundsh (1962): holds for x > e^{3/2}:+            -- Rosser and Schoenfeld Bounds (1962): holds for x > e^{3/2}:             | limit < 60184 = round (fromIntegral limit / (log (fromIntegral limit) - 1.5) :: Double)             -- Pierre Dusart (2010): holds for x >= 60184:             | otherwise = ceiling (fromIntegral limit / (log (fromIntegral limit) - 1.1) :: Double)@@ -117,7 +117,7 @@       -- FIXME: carry index?       nPrimes <- VUM.replicate 1 (1 :: Int) -      -- Sieve of Eratosthenes by block of size `s`, ignoring even numers+      -- Sieve of Eratosthenes by block of size `s`, ignoring even numbers       -- FIXME: block length of size `s/2` should make more sense?       block <- VUM.unsafeNew s       let !r = limit `div` 2@@ -151,7 +151,7 @@       pure $ VGM.take len result  -- | \(O(w \log^3 n)\) Miller–Rabin primality test, where \(w = 3\) for \(x \lt 2^{32}\) and--- \(w = 7\) for \(x \ge 3^{32}\).+-- \(w = 7\) for \(x \ge 2^{32}\). -- -- ==== __Example__ -- >>> isPrime 100055128505716009@@ -233,7 +233,7 @@  -- | Tries to find a prime factor for the given value, running Pollard's Rho algorithm. ----- ==== Constrants+-- ==== Constraints -- - \(x \gt 1\) {-# INLINEABLE findPrimeFactor #-} findPrimeFactor :: (HasCallStack) => StdGen -> Int -> (Maybe Int, StdGen)@@ -305,8 +305,8 @@                   error $ "unable to find prime factor for " ++ show cur             | otherwise = pure iWrite -      -- NOTE: The seed value ifs fixed here. We could decide it at runtime for possibly faster-      -- submissions on TLE redjuge, however, 're rather preferring deterministic result:+      -- NOTE: The seed value is fixed here. We could decide it at runtime for possibly faster+      -- submissions on TLE redjuge, however, we're rather preferring deterministic result:       len <- runRho (mkStdGen 123456789) n' iWrite0       pure $ VUM.take len buf   where

@@ -129,8 +129,8 @@ {-# INLINE addMod #-} addMod :: Word64 -> Word64 -> Word64 -> Word64 addMod m a b-    | x' >= m = x' - m-    | otherwise = x'+  | x' >= m = x' - m+  | otherwise = x'   where     !x' = a + b @@ -138,8 +138,8 @@ {-# INLINE subMod #-} subMod :: Word64 -> Word64 -> Word64 -> Word64 subMod m a b-    | a >= b = a - b-    | otherwise = a - b + m+  | a >= b = a - b+  | otherwise = a - b + m  -- | \(O(1)\) Calculates \(a^n \bmod m\) in the Montgomery form. --@@ -174,4 +174,3 @@   where     !a' = if a < mM64 then a else a - mM64     !b' = if b < mM64 then b else b - mM64-

@@ -37,8 +37,8 @@   ) where -import AtCoder.Internal.Assert qualified as ACIA import AtCoder.Extra.Math.Montgomery64 qualified as M64+import AtCoder.Internal.Assert qualified as ACIA import Data.Ratio (denominator, numerator) import Data.Vector.Generic qualified as VG import Data.Vector.Generic.Mutable qualified as VGM@@ -209,6 +209,7 @@   abs = id   {-# INLINE signum #-}   signum _ = ModInt64 $ M64.encode (M64.new (proxy# @p)) 1+   -- because the input value can be negative, be sure to take the mod:   {-# INLINE fromInteger #-}   fromInteger = ModInt64 . M64.encode (M64.new (proxy# @p)) . fromInteger . (`mod` m)

@@ -38,7 +38,7 @@ import Prelude hiding (map)  -- | Monoid action \(f: x \rightarrow ax + b\). Less efficient than @Affine1@, but is compatible--- with inverse opereations.+-- with inverse operations. -- -- ==== Composition and dual -- The affine transformation acts as a left monoid action: \(f_2 (f_1 v) = (f_2 \circ f_1) v\). To

@@ -49,7 +49,7 @@ -- >>> seg <- ST.build @_ @RH . VU.map (RH.unsafeNew . ord) $ VU.fromList "abcba" -- >>> seg' <- ST.build @_ @(Dual RH) . VU.map (Dual . RH.unsafeNew . ord) $ VU.fromList "abcba" -- >>> hash1 <- ST.prod seg 2 5       --   cba  (left to right)--- >>> Dual hash2 <- ST.prod seg' 0 3 -- abc    (right to lett)+-- >>> Dual hash2 <- ST.prod seg' 0 3 -- abc    (right to left) -- >>> hash1 == hash2 -- True --

@@ -64,7 +64,7 @@   ( -- * MultiSet     MultiSet, -    -- * Construtors+    -- * Constructors     new,      -- * Metadata

@@ -45,8 +45,8 @@   ) where -import AtCoder.Internal.Assert qualified as ACIA import AtCoder.Extra.Vector.Prim qualified as EVP+import AtCoder.Internal.Assert qualified as ACIA import Control.Monad import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim) import Control.Monad.ST (ST)@@ -111,7 +111,7 @@     nPdsu :: {-# UNPACK #-} !Int,     -- | Parent: non-positive, size: positive     parentOrSizePdsu :: !(VUM.MVector s Int),-    -- | Diffierencial potential of each vertex.+    -- | Differential potential of each vertex.     potentialPdsu :: !(VUM.MVector s a),     invertPdsu :: !(a -> a)   }@@ -142,7 +142,7 @@     !_ = ACIA.checkIndex "AtCoder.Extra.Pdsu.leader" v0 $ nPdsu pdsu  -- | \(O(\alpha(n))\) Returns \(p(v)\), the potential value of vertex \(v\) relative to the--- reprensetative of its group.+-- representative of its group. -- -- @since 1.1.0.0 {-# INLINE pot #-}

@@ -62,7 +62,7 @@     nextPool :: !(VUM.MVector s Index)   } --- | Strongly typed index of pool items. User has to explicitly @corece@ on raw index use.+-- | Strongly typed index of pool items. User has to explicitly @coerce@ on raw index use. -- -- @since 1.2.0.0 newtype Index = Index {unIndex :: Int}

@@ -275,7 +275,7 @@       VGM.write dataDst (idx wDst y x) $! xl <> xr    -- extend each column as a segment tree:-  -- NOTE (pref): interate from y then x for contiguous memory access+  -- NOTE (pref): iterate from y then x for contiguous memory access   for_ [hDst - 1, hDst - 2 .. 0] $ \y -> do     for_ [0 .. 2 * wDst - 1] $ \x -> do       xl <- VGM.read dataDst (idx wDst (2 * y + 0) x)@@ -311,7 +311,7 @@     -- inclusive interval [xl, xr]     inner !acc xl xr       | xl > xr = pure acc-      | otherwise =do+      | otherwise = do           acc' <-             if testBit xl 0               then (acc <>) <$> VGM.read dataDst (idx wDst y xl)

@@ -283,7 +283,7 @@   a <- VGM.unsafeRead hA 0   b <- VGM.unsafeRead hB 0   c <- VGM.unsafeRead hC 0-  d <- VGM.unsafeRead hC 0+  d <- VGM.unsafeRead hD 0   root' <- Seq.merge4ST seq a b c d   VGM.unsafeWrite hA 0 root'   VGM.unsafeWrite hB 0 P.undefIndex

@@ -178,7 +178,7 @@   VGM.write (Seq.unHandle rootMap) 0 P.undefIndex  -- ---------------------------------------------------------------------------------------------- Metadta+-- Metadata -- -------------------------------------------------------------------------------------------  -- | \(O(1)\) Returns the maximum number of elements the map can store.

@@ -1351,7 +1351,7 @@   -- lazily propagate new reverse or cancel:   VGM.modify revSeq (xor (Bit True)) $ coerce i --- | Amortized \(O(\log n)\). Propgates the lazily propagated values on a node.+-- | Amortized \(O(\log n)\). Propagates the lazily propagated values on a node. -- -- @since 1.2.1.0 {-# INLINE propNodeST #-}@@ -1392,7 +1392,7 @@         inner p       inner i --- | Amortized \(O(\log n)\). Propgates at a node.+-- | Amortized \(O(\log n)\). Propagates at a node. -- -- @since 1.2.1.0 {-# INLINE applyNodeST #-}

@@ -205,7 +205,7 @@   (Monad m) =>   -- | Context: Block length.   Int ->-  -- | @readFull@ function that takes a target block index and returns  amonoid value for it.+  -- | @readFull@ function that takes a target block index and returns a monoid value for it.   (a -> Int -> m a) ->   -- | @readPart@ function that takes a target block index, a half-open interval and returns a   -- monoid value for it.

@@ -247,7 +247,7 @@   foldImpl tree valAt toF act root (\_ _ -> pure ())  -- | \(O(n)\) Folds a tree from a root vertex, also known as tree DP. The calculation process on--- every vertex is recoreded and returned as a vector.+-- every vertex is recorded and returned as a vector. -- -- ==== __Example__ -- >>> import AtCoder.Extra.Graph qualified as Gr

@@ -107,7 +107,7 @@ -- -- ===== Segment queries -- Products and segment queries are primarily used by the @TreeMonoid@ module and is not intended--- for diretct use, but here's some examples. This time the reindex by the HLD is identity:+-- for direct use, but here's some examples. This time the reindex by the HLD is identity: -- -- >>> Hld.indexHld hld -- [0,1,2,3,4,5]@@ -178,7 +178,7 @@ -- @since 1.1.0.0 type VertexHld = Vertex --- | `Hld` partitions a tree into segments and assignes contiguous `VertexHld` for each segment.+-- | `Hld` partitions a tree into segments and assigns contiguous `VertexHld` for each segment. -- -- @since 1.1.0.0 data Hld = Hld@@ -335,7 +335,7 @@         <*> pure subtreeSize   where     !n = Gr.nCsr tree-    !_ = ACIA.runtimeAssert (2 * (Gr.nCsr tree - 1) == Gr.mCsr tree) "AtCoder.Extra.Hld.newAt: not a non-directed tree"+    !_ = ACIA.runtimeAssert (2 * (Gr.nCsr tree - 1) == Gr.mCsr tree) "AtCoder.Extra.Hld.newAt: not an undirected tree"     !_ = ACIA.runtimeAssert (n >= 1) "AtCoder.Extra.Hld.newAt: the tree must have at least one vertex"  -- | \(O(\log n)\) Calculates the lowest common ancestor of \(u\) and \(v\).

@@ -451,7 +451,7 @@ -- ==== Constraints -- - \(0 \le u, v \lt n\) -- - \(0 \le k \lt \mathrm{|path|}\)--- - \(u\) and \(v\) must be in the same connected component, otherwise the vehavior is undefined.+-- - \(u\) and \(v\) must be in the same connected component, otherwise the behavior is undefined. -- -- @since 1.1.1.0 {-# INLINE jump #-}@@ -464,7 +464,7 @@ -- -- ==== Constraints -- - \(0 \le u, v \lt n\)--- - \(u\) and \(v\) must be in the same connected component, otherwise the vehavior is undefined.+-- - \(u\) and \(v\) must be in the same connected component, otherwise the behavior is undefined. -- -- @since 1.5.1.0 {-# INLINE jumpMaybe #-}

@@ -201,7 +201,7 @@ fromEdges hld commuteTM edges = stToPrim $ fromEdgesST hld commuteTM edges  -- | \(O(\log^2 n)\) Returns the monoid product of the path between two vertices \(u\) and \(v\)--- (invlusive).+-- (inclusive). -- -- @since 1.1.0.0 {-# INLINE prod #-}

@@ -36,9 +36,9 @@  -- TODO: maybe add lexicographic permutations, combinations, and subsequences. +import AtCoder.Extra.Bisect (lowerBound) import AtCoder.Internal.Assert qualified as ACIA import AtCoder.Internal.Queue qualified as Q-import AtCoder.Extra.Bisect (lowerBound) import Control.Monad (when) import Control.Monad.Fix (fix) import Control.Monad.Primitive (PrimMonad)

@@ -14,6 +14,8 @@     iterateNM,      -- ** Unfolding++    -- TODO: implement unfoldrM     constructNM,     constructrNM, @@ -101,7 +103,7 @@   v' <- VG.unsafeFreeze v   fill v' 0   where-    fill :: v a ->Int -> m (v a)+    fill :: v a -> Int -> m (v a)     fill !v i       | i < n = do           x <- f (VG.unsafeTake i v)@@ -123,7 +125,7 @@   v' <- VG.unsafeFreeze v   fill v' 0   where-    fill :: v a ->Int -> m (v a)+    fill :: v a -> Int -> m (v a)     fill !v i       | i < n = do           x <- f (VG.unsafeSlice (n - i) i v)

@@ -100,7 +100,7 @@ -- -- @since 1.1.0.0 {-# INLINE access #-}-access ::  WaveletMatrix -> Int -> Maybe Int+access :: WaveletMatrix -> Int -> Maybe Int access WaveletMatrix {..} i = (yDictWm VG.!) <$> Rwm.access rawWm i  -- | \(O(\log |S|)\) Returns the number of \(y\) in \([l, r)\).

@@ -75,7 +75,7 @@ import Data.Vector.Unboxed.Mutable qualified as VUM import GHC.Stack (HasCallStack) --- | A static Wavelet Matrix without automatic index comperssion.+-- | A static Wavelet Matrix without automatic index compression. -- -- @since 1.1.0.0 data RawWaveletMatrix = RawWaveletMatrix

@@ -182,7 +182,7 @@     i_     $ V.zip (Rwm.bitsRwm rawWm2d) segTreesWm2d --- | \(O(\log^2 n)\) Given a user function \(f\), odifies the monoid value at \((x, y)\). Access to+-- | \(O(\log^2 n)\) Given a user function \(f\), modifies the monoid value at \((x, y)\). Access to -- unknown points are undefined. -- -- @since 1.1.0.0

@@ -71,7 +71,7 @@ -- -- @since 1.0.0.0 data FenwickTree s a = FenwickTree-  { -- | 1.0.0 The number of vertices.+  { -- | The number of vertices.     --     -- @since 1.0.0.0     nFt :: {-# UNPACK #-} !Int,@@ -259,7 +259,7 @@   FenwickTree (PrimState m) a ->   -- | \(r\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> Bool) ->   -- | \(l\): \(p\) holds for \([l, r)\)   m Int

@@ -166,7 +166,7 @@   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)\).+-- | \(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 #-}@@ -184,11 +184,11 @@   Int ->   -- | \(h\)   Int ->-  -- | \([x_1, x_2) \times [y_1 y_2) \in [0, w) \times [0, h)\).+  -- | \([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 \land 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 #-}@@ -202,7 +202,7 @@   Int ->   -- | \(y_2\)   Int ->-  -- | \(x_1 \le x_2 \land y_1 \le \y_2\).+  -- | \(x_1 \le x_2 \land y_1 \le y_2\).   Bool testRectShape x1 x2 y1 y2 = x1 <= x2 && y1 <= y2 @@ -283,7 +283,7 @@   | testIndex i n = ()   | otherwise = errorCustom funcName indexName i setName n --- | \(O(1)\) Emis custom index error.+-- | \(O(1)\) Emits custom index error. -- -- @since 1.0.0.0 {-# INLINE errorCustom #-}@@ -339,7 +339,7 @@ errorPoint2d funcName x y w h =   error $ funcName ++ ": given invalid point `(" ++ show x ++ ", " ++ show y ++ ")` for rectangle `[0, " ++ show w ++ ") x [0, " ++ show h ++ ")`" --- | \(O(1)\) Asserts \([x_1, x_2) \times [y_1 y_2) \in [0, w) \times [0, h)\).+-- | \(O(1)\) Asserts \([x_1, x_2) \times [y_1, y_2) \in [0, w) \times [0, h)\). -- -- @since 1.2.3.0 {-# INLINE checkRect #-}

@@ -296,7 +296,7 @@ {-# INLINEABLE popBackST_ #-} popBackST_ :: (VU.Unbox a) => Buffer s a -> ST s () popBackST_ buf = do-  _ <- popBack buf+  _ <- popBackST buf   pure ()  {-# INLINEABLE writeST #-}

@@ -57,7 +57,7 @@ import Data.Vector.Unboxed.Mutable qualified as VUM import GHC.Stack (HasCallStack) --- | Comperssed Sparse Row representation of a graph.+-- | Compressed Sparse Row representation of a graph. -- -- @since 1.0.0.0 data Csr w = Csr

@@ -87,7 +87,7 @@   ) where --- NOTE (perf): we have to inine all the functions for reasonable performance+-- NOTE (perf): we have to inline all the functions for reasonable performance  import AtCoder.Internal.Assert qualified as ACIA import Control.Monad (when)

@@ -65,7 +65,7 @@ buildST :: (HasCallStack, Num cap, VU.Unbox cap, VU.Unbox cost, Num cost) => Int -> VU.Vector (Int, Int, cap, cap, cost) -> ST s (VU.Vector Int, Csr s cap cost) buildST n edges = do   let m = VU.length edges-  -- craete the offsets first (this is a different step from ac-librar)+  -- create the offsets first (this is a different step from ac-library)   let startCsr = VU.create $ do         start <- VUM.replicate (n + 1) (0 :: Int)         -- count degrees

@@ -111,7 +111,7 @@ -- -- >>> Q.freeze que -- [0,1]-+-- -- >>> Q.clear que -- >>> Q.freeze que -- []@@ -194,7 +194,7 @@ new n = stToPrim $ newST n  -- | \(O(n)\) Creates a `Queue` with capacity \(2n + 1\), where the internal front/back position is--- initialzed at \(n\).+-- initialized at \(n\). -- -- @since 1.2.4.0 {-# INLINEABLE newDeque #-}

@@ -15,7 +15,7 @@ -- -- >>> MF.addEdge_ g 1 2 (1 :: Int) --  0 --> 1 --> 2 ----- Augument the flow with `flow`. `maxFlow` can also be used when there's no flow limit:+-- Augment the flow with `flow`. `maxFlow` can also be used when there's no flow limit: -- -- >>> MF.flow g 0 2 {- flowLimit -} maxBound -- same as `MF.maxFlow g 0 2` -- 1

@@ -15,7 +15,7 @@ -- -- >>> MCF.addEdge_ g 1 2 2 5   --  0 --> 1 --> 2 ----- Augument flow with `flow`, `maxFlow` or `slope`:+-- Augment flow with `flow`, `maxFlow` or `slope`: -- -- >>> MCF.slope g 0 2 maxBound -- slope g from to flowLimit -- [(0,0),(2,16)]@@ -169,7 +169,7 @@   (HasCallStack, PrimMonad m, Integral cap, Ord cap, VU.Unbox cap, Num cost, Ord cost, Bounded cost, VU.Unbox cost) =>   -- | Graph   McfGraph (PrimState m) cap cost ->-  -- | Fource @s@+  -- | Source @s@   Int ->   -- | Sink @t@   Int ->@@ -342,7 +342,7 @@ slopeST McfGraph {..} s t flowLimit = do   let !_ = ACIA.checkCustom "AtCoder.MinCostFlow.slopeST" "`source` vertex" s "the number of vertices" nG   let !_ = ACIA.checkCustom "AtCoder.MinCostFlow.slopeST" "`sink` vertex" t "the number of vertices" nG-  let !_ = ACIA.runtimeAssert (s /= t) "AtCoder.MinCostFlow.slopeST: `source` and `sink` vertex must be distict"+  let !_ = ACIA.runtimeAssert (s /= t) "AtCoder.MinCostFlow.slopeST: `source` and `sink` vertex must be distinct"    edges_@(VU.V_5 _ _ _ caps _ _) <- ACIGV.unsafeFreeze edgesG   (!edgeIdx, !g) <- ACIMCSR.build nG edges_

@@ -119,7 +119,7 @@ -- -- @since 1.0.0.0 data SegTree s a = SegTree-  { -- | THe number of vertices.+  { -- | The number of vertices.     --     -- @since 1.0.0.0     nSt :: {-# UNPACK #-} !Int,@@ -298,7 +298,7 @@   SegTree (PrimState m) a ->   -- | \(r\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> Bool) ->   -- | \(l\): \(p\) holds for \([l, r)\)   m Int@@ -324,7 +324,7 @@   SegTree (PrimState m) a ->   -- | \(r\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> m Bool) ->   -- | \(l\): \(p\) holds for \([l, r)\)   m Int@@ -386,13 +386,13 @@   SegTree (PrimState m) a ->   -- | \(l\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> Bool) ->   -- | \(r\): \(p\) holds for \([l, r)\)   m Int maxRight seg l0 f = maxRightM seg l0 (pure . f) --- | Moandic variant of `maxRight`.+-- | Monadic variant of `maxRight`. -- -- ==== Constraints -- - if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.@@ -410,7 +410,7 @@   SegTree (PrimState m) a ->   -- | \(l\)   Int ->-  -- | \(p\): user prediate+  -- | \(p\): user predicate   (a -> m Bool) ->   -- | \(r\): \(p\) holds for \([l, r)\)   m Int

@@ -203,7 +203,7 @@ -- \(i\)-th element is the length of the LCP (Longest Common Prefix) of \(s[0..n)\) and \(s[i..n)\). -- -- ==== Constraints--- - \(n \leq n\)+-- - \(0 \leq n\) -- -- ==== Complexity -- - \(O(n)\)@@ -246,7 +246,7 @@ -- element is the length of the LCP (Longest Common Prefix) of \(s[0..n)\) and \(s[i..n)\). -- -- ==== Constraints--- - \(n \leq n\)+-- - \(0 \leq n\) -- -- ==== Complexity -- - \(O(n)\)

@@ -123,7 +123,7 @@   $ \a b -> convMintNaive a b QC.=== ACC.convolution a b  prop_simpleSMod2 :: TestTree-prop_simpleSMod2 = QC.testProperty "simpleSMod1"+prop_simpleSMod2 = QC.testProperty "simpleSMod2"   . testWithRangeMint @924844033   $ \a b -> convMintNaive a b QC.=== ACC.convolution a b 

@@ -87,7 +87,7 @@     i = intervalGen n     f = Affine1.new <$> (modInt <$> arbitrary) <*> (modInt <$> arbitrary) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef l0 vec q = case q of   Write k v -> do

@@ -88,7 +88,7 @@     i = intervalGen n     f = Affine1.new <$> (modInt <$> arbitrary) <*> (modInt <$> arbitrary) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef l0 vec q = case q of   Write k v -> do

@@ -77,7 +77,7 @@     v = Sum . modInt <$> QC.arbitrary     i = intervalGen n --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef l0 vec q = case q of   Write k v -> do

@@ -78,7 +78,7 @@     v = Sum . modInt <$> QC.arbitrary     i = intervalGen n --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef l0 vec q = case q of   Write k v -> do

@@ -69,7 +69,7 @@     v = Sum . modInt <$> QC.arbitrary     i = intervalGen n --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef vec q = case q of   Write k v -> do

@@ -70,7 +70,7 @@     v = Sum . modInt <$> QC.arbitrary     i = intervalGen n --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VUM.MVector RealWorld (Sum Mint) -> Query -> IO Result handleRef vec q = case q of   Write k v -> do

@@ -6,7 +6,7 @@ import Control.Monad (foldM_) import Control.Monad.Primitive (PrimMonad, PrimState) import Control.Monad.ST (RealWorld)-import Data.HashMap.Strict qualified as HMR -- R: referencial implementation+import Data.HashMap.Strict qualified as HMR -- R: referential implementation import Data.Vector.Algorithms.Intro qualified as VAI import Data.Vector.Unboxed qualified as VU import System.IO.Unsafe (unsafePerformIO)@@ -84,7 +84,7 @@   | M (Maybe Int)   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: HMR.HashMap Int Int -> Query -> (HMR.HashMap Int Int, Result) handleRef hm q = case q of   Size -> (hm, I $ HMR.size hm)

@@ -6,7 +6,7 @@ import Control.Monad (foldM_) import Control.Monad.Primitive (PrimMonad, PrimState) import Control.Monad.ST (RealWorld)-import Data.Map.Strict qualified as IMR -- R: referencial implementation+import Data.Map.Strict qualified as IMR -- R: referential implementation import Data.Vector.Unboxed qualified as VU import GHC.Stack (HasCallStack) import Test.QuickCheck.Monadic as QCM@@ -85,7 +85,7 @@     insertKeyGen = QC.chooseInt (0, n - 1)     valGen = QC.chooseInt (-10, 10) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: IMR.Map Int Int -> Query -> (IMR.Map Int Int, Result) handleRef im q = case q of   Size -> (im, I $ IMR.size im)

@@ -6,7 +6,7 @@ import Control.Monad (foldM_) import Control.Monad.Primitive (PrimMonad, PrimState) import Control.Monad.ST (RealWorld)-import Data.Set qualified as ISR -- R: referencial implementation+import Data.Set qualified as ISR -- R: referential implementation import Data.Vector.Unboxed qualified as VU import GHC.Stack (HasCallStack) import Test.QuickCheck.Monadic as QCM@@ -75,7 +75,7 @@     -- for partial functions     insertKeyGen = QC.chooseInt (0, n - 1) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: ISR.Set Int -> Query -> (ISR.Set Int, Result) handleRef is q = case q of   Member k -> (is, B $ ISR.member k is)

@@ -106,7 +106,7 @@   let intervals = zipWith (\xs l -> (l, l + VU.length xs, VU.head xs)) groups lens   pure . VU.fromList $ filter (\(!_, !_, !x) -> x /= undef) intervals --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: (PrimMonad m) => VUM.MVector (PrimState m) Int -> Query -> m Result handleRef vec q = do   intervals <- toIntervals vec

@@ -8,9 +8,9 @@ import Data.Vector.Unboxed qualified as VU import Test.QuickCheck.Monadic as QCM import Test.Tasty+import Test.Tasty.HUnit import Test.Tasty.QuickCheck as QC import Tests.Util-import Test.Tasty.HUnit  data Init = Init   { n :: {-# UNPACK #-} !Int,@@ -62,16 +62,18 @@     r = (,) <$> intervalGen' (-rngI) rngI <*> intervalGen' (-rngI) rngI     xy = intervalGen' (-rngI) rngI --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VU.Vector (Int, Int) -> Query -> Result handleRef vec q = case q of   FindPointsIn ((!x1, !x2), (!y1, !y2)) -> do     V $ VU.findIndices (\(!x, !y) -> x1 <= x && x < x2 && y1 <= y && y < y2) vec   FindNearestPoint (!x, !y)     | VU.null vec -> MI Nothing-    | otherwise -> MI-      . Just . VU.minIndex-        $ VU.map (\(!x', !y') -> (x - x') * (x - x') + (y - y') * (y - y')) vec+    | otherwise ->+        MI+          . Just+          . VU.minIndex+          $ VU.map (\(!x', !y') -> (x - x') * (x - x') + (y - y') * (y - y')) vec  -- | ACL handleAcl :: Kt.KdTree -> Query -> Result

@@ -16,9 +16,9 @@ import Data.Vector.Unboxed.Mutable qualified as VUM import Test.QuickCheck.Monadic as QCM import Test.Tasty+import Test.Tasty.HUnit import Test.Tasty.QuickCheck as QC import Tests.Util-import Test.Tasty.HUnit  type Mint = M.ModInt998244353 @@ -85,7 +85,7 @@     v = Sum . modInt <$> QC.arbitrary     f = Affine1.new <$> (modInt <$> QC.arbitrary) <*> (modInt <$> QC.arbitrary) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VUM.MVector RealWorld (Int, Int, Sum Mint) -> Query -> IO Result handleRef vec q = case q of   Write i v -> do

@@ -93,7 +93,7 @@     deltaGen = QC.chooseInt (-n, n)     insertValGen = QC.chooseInt (1, n) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: IM.IntMap Int -> Query -> (IM.IntMap Int, Result) handleRef im q = case q of   Member key -> (im, B $ IM.member key im)

@@ -77,7 +77,7 @@   | MS !(Maybe (Sum Int))   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VUM.MVector RealWorld (Int, Int, Sum Int) -> Query -> IO Result handleRef vec q = case q of   -- Read i -> do

@@ -75,7 +75,7 @@   | MS !(Maybe (Sum Int))   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> Int -> VUM.MVector RealWorld (Sum Int) -> Query -> IO Result handleRef w h vec q = case q of   Read (!x, !y) -> do

@@ -35,7 +35,7 @@   col <- VU.fromList <$> QC.vectorOf w (QC.arbitrary @Int)   let lhs = Mat.mulToCol mat col   let rhs = Mat.vecM $ Mat.mul mat (Mat.new w 1 col)-  pure  $ lhs QC.=== rhs+  pure $ lhs QC.=== rhs  m :: Int m = 998244353

@@ -186,12 +186,12 @@     keyGen = QC.chooseInt (0, n - 1)     maybeKeyGen = QC.chooseInt (-1, n)     maybeIntervalGen = (,) <$> QC.chooseInt (-1, n + 1) <*> QC.chooseInt (-1, n + 1)-    -- use non-negative values for monotoniously increasing sum+    -- use non-negative values for monotonically increasing sum     valGen = Sum <$> QC.chooseInt (0, 10)     -- NOTE: it might throw an error on overflow:     fGen = Affine1.new <$> QC.chooseInt (0, 4) <*> QC.chooseInt (0, 4) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: S.Seq (Sum Int) -> Query -> (S.Seq (Sum Int), Result) handleRef seq q = case q of   Reset -> (S.empty, None)

@@ -60,9 +60,9 @@   | ExchangeAt !Int !(Sum Int)   | ProdInInterval !(Int, Int)   | ApplyInInterval !(Int, Int) !(Affine1 Int)-  -- | ILowerBound !(Sum Int)-  -- | ILowerBoundM !(Sum Int)-  | ILowerBoundProd !(Sum Int)+  | -- | ILowerBound !(Sum Int)+    -- | ILowerBoundM !(Sum Int)+    ILowerBoundProd !(Sum Int)   | ILowerBoundProdM !(Sum Int)   | Freeze   deriving (Show)@@ -125,14 +125,14 @@       l <- QC.chooseInt (-30, 30)       r <- QC.chooseInt (l, 30)       pure (l, r)-    -- use non-negative values for monotoniously increasing sum+    -- use non-negative values for monotonically increasing sum     valGen = Sum <$> QC.chooseInt (0, 10)     -- NOTE: it might throw an error on overflow:     fGen = Affine1.new <$> QC.chooseInt (0, 4) <*> QC.chooseInt (0, 4)     iGen = QC.chooseInt (0, n - 1)     maybeIGen = QC.chooseInt (-1, n) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: Int -> M.Map Int (Sum Int) -> Query -> (M.Map Int (Sum Int), Result) handleRef capacity m q = case q of   Reset -> (M.empty, None)

@@ -10,7 +10,7 @@ import Control.Monad (when) import Control.Monad.Primitive (PrimMonad, PrimState) import Data.Foldable (for_)-import Data.Maybe (isJust, fromJust)+import Data.Maybe (fromJust, isJust) import Data.Semigroup (Sum (..)) import Data.Vector qualified as V import Data.Vector.Generic qualified as VG

@@ -82,7 +82,7 @@   | Assocs [(Int, Int)]   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VU.Vector Int -> Query -> Result handleRef xs q = case q of   Access i -> M $ xs VU.!? i@@ -181,10 +181,10 @@   try WM.kthLargestIn k   try WM.ikthLargestIn k --- try WM.unsafeKthSmallestIn--- try WM.unsafeIKthSmallestIn--- try WM.unsafeKthLargestIn--- try WM.unsafeIKthLargestIn+  -- try WM.unsafeKthSmallestIn+  -- try WM.unsafeIKthSmallestIn+  -- try WM.unsafeKthLargestIn+  -- try WM.unsafeIKthLargestIn    let tryRank :: (HasCallStack) => (WM.WaveletMatrix -> Int -> Int -> Int -> Int) -> Int -> IO ()       tryRank f x = do@@ -217,7 +217,7 @@   tryRank WM.rank 1   tryRank WM.rank (-1) --- TODO: test +-- TODO: test  -- (@?= Nothing) $ WM.select wm -- (@?= Nothing) $ WM.selectKth wm

@@ -98,7 +98,7 @@   | Assocs [(Int, Int)]   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: VU.Vector Int -> Query -> Result handleRef xs q = case q of   Access i -> M $ xs VU.!? i@@ -205,10 +205,10 @@   try WM.kthLargestIn k   try WM.ikthLargestIn k --- try WM.unsafeKthSmallestIn--- try WM.unsafeIKthSmallestIn--- try WM.unsafeKthLargestIn--- try WM.unsafeIKthLargestIn+  -- try WM.unsafeKthSmallestIn+  -- try WM.unsafeIKthSmallestIn+  -- try WM.unsafeKthLargestIn+  -- try WM.unsafeIKthLargestIn    let tryRank :: (HasCallStack) => (WM.RawWaveletMatrix -> Int -> Int -> Int -> Int) -> Int -> IO ()       tryRank f x = do@@ -244,7 +244,7 @@   tryRank WM.rank 1   tryRank WM.rank (-1) --- TODO: test +-- TODO: test  -- (@?= Nothing) $ WM.select wm -- (@?= Nothing) $ WM.selectKth wm

@@ -61,7 +61,7 @@   | MS !(Maybe (Sum Int))   deriving (Show, Eq) --- | containers. (referencial implementation)+-- | containers. (referential implementation) handleRef :: M.Map (Int, Int) (Sum Int) -> Query -> (Result, M.Map (Int, Int) (Sum Int)) handleRef map q = case q of   Read (!x, !y) -> (S . fromMaybe mempty $ M.lookup (x, y) map, map)

@@ -3,9 +3,9 @@ module Tests.Internal.Bit (tests) where  import AtCoder.Internal.Bit qualified as ACIBIT+import Data.Bits (countTrailingZeros, (.<<.)) import Test.Tasty import Test.Tasty.HUnit-import Data.Bits ((.<<.), countTrailingZeros)  unit_bitCeil :: TestTree unit_bitCeil = testCase "bitCeil" $ do@@ -29,7 +29,7 @@   (1 .<<. 62) @=? ACIBIT.bitCeil (1 .<<. 62)  unit_countrZero :: TestTree-unit_countrZero = testCase "coutrZero" $ do+unit_countrZero = testCase "countrZero" $ do   0 @=? countTrailingZeros (1 :: Int)   1 @=? countTrailingZeros (2 :: Int)   0 @=? countTrailingZeros (3 :: Int)

@@ -67,12 +67,12 @@         (a64 * b64) `mod` modulo64 @=? ACIBT.mulMod bt a64 b64  unit_barrettIntBorder :: TestTree-unit_barrettIntBorder = testCase "barrettIntBobrder" $ do+unit_barrettIntBorder = testCase "barrettIntBorder" $ do   let modUpper :: Word32 = fromIntegral $ maxBound @Int32   testBarrettWithModulo modUpper  unit_barrettWord32Border :: TestTree-unit_barrettWord32Border = testCase "barrettWord32Bobrder" $ do+unit_barrettWord32Border = testCase "barrettWord32Border" $ do   let modUpper = maxBound @Word32   testBarrettWithModulo modUpper 

@@ -1,4 +1,4 @@--- | Fenwick tree tests.+-- | Math tests. module Tests.Math (tests) where  import AtCoder.Math qualified as AM

@@ -82,7 +82,7 @@   modInt 2147483647 * modInt 2147483647 @?= 0  unit_int128 :: TestTree-unit_int128 = testCase "intMax" $ do+unit_int128 = testCase "int128" $ do   let modInt :: Int -> ModInt.ModInt998244353       modInt = ModInt.new 

@@ -1,7 +1,7 @@ module Tests.TwoSat (tests) where  import AtCoder.TwoSat qualified as TS-import Data.Bit (Bit(..))+import Data.Bit (Bit (..)) import Data.Vector.Unboxed qualified as VU import Test.Tasty import Test.Tasty.HUnit

@@ -105,7 +105,7 @@        -- 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+        -- NOTE: At the beginning, deg[u] > 1, and deg[i] is never decreased until iterated         !v <- fromJust . VU.findIndex (== 1) <$> VU.unsafeFreeze deg         -- So we're sure u /= v         let !_ = ACIA.runtimeAssert (u /= v) "u /= v"