packages feed

ac-library-hs 1.5.3.0 → 1.5.3.1

raw patch · 17 files changed

+435/−212 lines, 17 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

ac-library-hs.cabal view
@@ -1,11 +1,10 @@-cabal-version:   3.4-name:            ac-library-hs-+cabal-version: 3.4+name: ac-library-hs -- PVP summary:  +-+------- breaking API changes --               | | +----- non-breaking API additions --               | | | +--- code changes with no API change-version:         1.5.3.0-synopsis:        Data structures and algorithms+version: 1.5.3.1+synopsis: Data structures and algorithms description:   Haskell port of [ac-library](https://github.com/atcoder/ac-library), a library for competitive   programming on [AtCoder](https://atcoder.jp/). ([GitHub](https://github.com/toyboot4e/ac-library-hs), [DeepWiki](https://deepwiki.com/toyboot4e/ac-library-hs))@@ -13,21 +12,21 @@   - Functions primarily use half-open interval \([l, r)\).   - The `Extra` module contains additional utilities beyond the original C++ library. -category:        Algorithms, Data Structures-license:         CC0-1.0-license-file:    LICENSE-author:          toyboot4e <toyboot4e@gmail.com>-maintainer:      toyboot4e <toyboot4e@gmail.com>-build-type:      Simple+category: Algorithms, Data Structures+license: CC0-1.0+license-file: LICENSE+author: toyboot4e <toyboot4e@gmail.com>+maintainer: toyboot4e <toyboot4e@gmail.com>+build-type: Simple extra-doc-files:   CHANGELOG.md-  examples/README.md   README.md+  examples/README.md -tested-with:     GHC ==9.8.4+tested-with: ghc ==9.8.4  source-repository head-  type:     git+  type: git   location: https://github.com/toyboot4e/ac-library-hs.git  common warnings@@ -35,22 +34,23 @@  common dependencies   build-depends:-    , base                  >=4.9     && <4.22-    , bitvec                <1.2-    , bytestring            <0.14-    , primitive             >=0.6.4.0 && <0.10-    , random                >=1.2.0   && <1.4-    , transformers          >=0.2.0.0-    , unordered-containers  <0.3-    , vector                >=0.13.0  && <0.14-    , vector-algorithms     <0.10-    , wide-word             <0.2+    base >=4.9 && <4.22,+    bitvec <1.2,+    bytestring <0.14,+    primitive >=0.6.4.0 && <0.10,+    random >=1.2.0 && <1.4,+    transformers >=0.2.0.0,+    unordered-containers <0.3,+    vector >=0.13.0 && <0.14,+    vector-algorithms <0.10,+    wide-word <0.2,    default-language: GHC2021  library-  import:          warnings-  import:          dependencies+  import: warnings+  import: dependencies+  -- cabal-gild: discover src   exposed-modules:     AtCoder.Convolution     AtCoder.Dsu@@ -68,9 +68,9 @@     AtCoder.Extra.DynSparseSegTree.Raw     AtCoder.Extra.Graph     AtCoder.Extra.HashMap-    AtCoder.Extra.IntervalMap     AtCoder.Extra.IntMap     AtCoder.Extra.IntSet+    AtCoder.Extra.IntervalMap     AtCoder.Extra.Ix0     AtCoder.Extra.KdTree     AtCoder.Extra.LazyKdTree@@ -132,22 +132,25 @@    -- other-modules:   -- other-extensions:-  hs-source-dirs:  src+  hs-source-dirs: src  executable example-lazy-segtree-  import:         warnings-  import:         dependencies+  import: warnings+  import: dependencies   hs-source-dirs: examples-  main-is:        LazySegTree.hs-  build-depends:  ac-library-hs+  main-is: LazySegTree.hs+  build-depends: ac-library-hs  test-suite ac-library-hs-test-  import:         warnings-  import:         dependencies+  import: warnings+  import: dependencies+  -- cabal-gild: discover test --exclude=test/Main.hs   other-modules:     Tests.Convolution     Tests.Dsu+    Tests.Extra.AhoCorasick     Tests.Extra.Bisect+    Tests.Extra.DsuMonoid     Tests.Extra.DynLazySegTree     Tests.Extra.DynLazySegTree.Persistent     Tests.Extra.DynSegTree@@ -157,9 +160,9 @@     Tests.Extra.Graph     Tests.Extra.HashMap     Tests.Extra.Hld-    Tests.Extra.IntervalMap     Tests.Extra.IntMap     Tests.Extra.IntSet+    Tests.Extra.IntervalMap     Tests.Extra.Ix0     Tests.Extra.KdTree     Tests.Extra.LazyKdTree@@ -203,32 +206,32 @@     Tests.TwoSat     Tests.Util -  type:           exitcode-stdio-1.0+  type: exitcode-stdio-1.0   hs-source-dirs: test-  main-is:        Main.hs+  main-is: Main.hs   build-depends:-    , ac-library-hs-    , containers-    , hspec-    , mtl-    , QuickCheck-    , quickcheck-classes-    , random-    , semirings-    , tasty-    , tasty-hspec-    , tasty-hunit-    , tasty-quickcheck-    , tasty-rerun-    , transformers-    , unordered-containers+    QuickCheck,+    ac-library-hs,+    containers,+    hspec,+    mtl,+    quickcheck-classes,+    random,+    semirings,+    tasty,+    tasty-hspec,+    tasty-hunit,+    tasty-quickcheck,+    tasty-rerun,+    transformers,+    unordered-containers,  benchmark ac-library-hs-benchmark-  import:         warnings-  import:         dependencies-  ghc-options:    -O2-  type:           exitcode-stdio-1.0-  main-is:        Main.hs+  import: warnings+  import: dependencies+  ghc-options: -O2+  type: exitcode-stdio-1.0+  main-is: Main.hs   hs-source-dirs: benchmarks   other-modules:     Bench.AddMod@@ -258,17 +261,17 @@     BenchLib.Vector.MapAccumL    build-depends:-    , ac-library-hs-    , base-    , criterion-    , mtl-    , random-    , tagged-    , transformers+    ac-library-hs,+    base,+    criterion,+    mtl,+    random,+    tagged,+    transformers,  test-suite benchlib-test-  import:         warnings-  import:         dependencies+  import: warnings+  import: dependencies   other-modules:     BenchLib.AddMod     BenchLib.ModInt.ModIntNats@@ -279,19 +282,19 @@     BenchLib.PowMod     Tests.MulMod -  type:           exitcode-stdio-1.0+  type: exitcode-stdio-1.0   hs-source-dirs: benchmarks-  main-is:        TestMain.hs+  main-is: TestMain.hs   build-depends:-    , ac-library-hs-    , hspec-    , mtl-    , QuickCheck-    , random-    , tagged-    , tasty-    , tasty-hunit-    , tasty-quickcheck-    , tasty-rerun+    QuickCheck,+    ac-library-hs,+    hspec,+    mtl,+    random,+    tagged,+    tasty,+    tasty-hunit,+    tasty-quickcheck,+    tasty-rerun,  -- , quickcheck-instances
examples/LazySegTree.hs view
@@ -4,7 +4,7 @@ {-# LANGUAGE TypeFamilies #-}  import AtCoder.LazySegTree (SegAct (..))-import AtCoder.LazySegTree qualified as LST+import AtCoder.LazySegTree qualified as LSeg import Data.Vector.Generic qualified as VG import Data.Vector.Generic.Mutable qualified as VGM import Data.Vector.Unboxed qualified as VU@@ -64,13 +64,13 @@  main :: IO () main = do-  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]-  !_ <- (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+  seg <- LSeg.build @_ @F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]+  LSeg.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]+  LSeg.write seg 3 $ X 10 -- [1, 5, 7, 10]+  LSeg.modify seg (+ (X 1)) 0 -- [2, 5, 7, 10]+  !_ <- (expect "test 1" (X 5)) <$> LSeg.read seg 1+  !_ <- (expect "test 2" (X 14)) <$> LSeg.prod seg 0 3 -- reads an interval [0, 3)+  !_ <- (expect "test 3" (X 24)) <$> LSeg.allProd seg+  !_ <- (expect "test 4" 2) <$> LSeg.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10+  !_ <- (expect "test 5" 3) <$> LSeg.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10   putStrLn "=> test passed!"
src/AtCoder/Extra/AhoCorasick.hs view
@@ -3,6 +3,7 @@ -- ==== __Example__ -- -- >>> import AtCoder.Extra.AhoCorasick qualified as AC+-- >>> import Data.Vector qualified as V -- >>> import Data.Vector.Unboxed qualified as VU -- -- Pattern strings must be given as @V.Vector (VU.Vector Int)@:@@ -49,7 +50,6 @@  import AtCoder.Extra.Vector qualified as EV import AtCoder.Internal.Queue qualified as Q-import Control.Monad (when) import Control.Monad.Fix (fix) import Control.Monad.ST (runST) import Data.Foldable (for_)@@ -92,7 +92,7 @@     outputAc :: !(VU.Vector Int)   } --- | \(O(\sum_i |S_i|)\)+-- | \(O(\sum_i |S_i|)\) Build an Aho–Corasick automaton. -- -- ==== Constraints -- - \(|S_i| > 0\)@@ -152,7 +152,7 @@         -- fallback to the longest match suffix         | otherwise -> inner $! suffixAc VG.! v --- | \(n\) Applies `next` N times for a given input string.+-- | \(O(n)\) Applies `next` \(n\) times for the input node. -- -- ==== Constraints --@@ -227,7 +227,7 @@    !nNodes <- VGM.read nNodesVec 0 -  let !pattern = VU.create $ do+  let !pat = VU.create $ do         -- We could replace the following with VU.accumulate         patVec <- VUM.replicate nNodes (-1 :: Int)         VU.iforM_ patternVerts $ \iPattern v -> do@@ -235,7 +235,7 @@         pure patVec   !trie <- VG.take nNodes <$> V.unsafeFreeze nextVec   !parent <- VG.take nNodes <$> VU.unsafeFreeze parentVec-  pure (nNodes, pattern, trie, parent)+  pure (nNodes, pat, trie, parent)  -- | \(O(\sum_i |S_i| \Gamma)\) {-# INLINEABLE runBfs #-}
src/AtCoder/Extra/Bisect.hs view
@@ -1,13 +1,9 @@ {-# LANGUAGE LambdaCase #-} --- | Bisection methods and binary search functions. They partition a half-open interval \([l, r)\)--- into two and return either the left or the right point of the boundary.+-- | Bisection methods and binary search functions. ----- @--- 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 and right points of the boundary--- @+-- __Known bug__: `maxRight` and their variants have a bug ([#140](https://github.com/toyboot4e/ac-library-hs/issues/140)),+-- so don't use them. -- -- ==== __Example__ -- Perform index compression with `lowerBound`:@@ -29,6 +25,10 @@     upperBoundIn,      -- * Generic bisection methods++    --+    -- __Known bug_:_ `maxRight` and their variants have a bug ([#140](https://github.com/toyboot4e/ac-library-hs/issues/140)),+    -- so don't use them.     maxRight,     maxRightM,     minLeft,@@ -180,6 +180,8 @@ --           R              R: the right boundary point returned -- @ --+-- __Known bug__: user function \(p\) takes __closed intervals__ \([l, r]\).+-- -- ==== __Example__ -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let xs = VU.fromList [10, 10, 20, 20, 30, 30]@@ -212,6 +214,8 @@  -- | \(O(\log n)\) Monadic variant of `maxRight`. --+-- __Known bug__: user function \(p\) takes __closed intervals__ \([l, r]\).+-- -- @since 1.3.0.0 {-# INLINE maxRightM #-} maxRightM :: (HasCallStack, Monad m) => Int -> Int -> (Int -> m Bool) -> m Int@@ -228,6 +232,8 @@ --         L                L: the left boundary point returned -- @ --+-- __Known bug__: user function \(p\) takes __closed intervals__ \([l, r]\).+-- -- ==== __Example__ -- >>> import Data.Vector.Unboxed qualified as VU -- >>> let xs = VU.fromList [10, 10, 20, 20, 30, 30]@@ -256,6 +262,8 @@ minLeft l r p = runIdentity $ minLeftM l r (pure . p)  -- | \(O(\log n)\) Monadic variant of `minLeft`.+--+-- __Known bug__: user function \(p\) takes __closed intervals__ \([l, r]\). -- -- @since 1.3.0.0 {-# INLINE minLeftM #-}
src/AtCoder/Extra/DsuMonoid.hs view
@@ -1,6 +1,7 @@ {-# LANGUAGE RecordWildCards #-} --- | A disjoint set union with commutative monoid values associated with each group.+-- | A disjoint set union with commutative semigroup (not necessary a monoid) values associated with+-- each group. -- -- ==== __Example__ --@@ -142,7 +143,7 @@ -- ==== Complexity -- - \(O(\alpha(n))\) amortized ----- @since 1.2.4.0+-- @since 1.5.3.0 {-# INLINEABLE mergeMaybe #-} mergeMaybe :: (HasCallStack, PrimMonad m, Semigroup a, VU.Unbox a) => DsuMonoid (PrimState m) a -> Int -> Int -> m (Maybe Int) mergeMaybe DsuMonoid {..} a b = stToPrim $ do
src/AtCoder/Extra/Math.hs view
@@ -47,8 +47,8 @@ import GHC.Stack (HasCallStack) import System.Random --- | \(O(n \log \log n)\) Creates an array of prime numbers up to the given limit, using Sieve of--- Eratosthenes.+-- | \(O(n \log \log n)\) Creates an array of prime numbers up to the given limit (inclusive), using+-- Sieve of Eratosthenes. -- -- The minimum computational complexity is \(\Omega(B \log \log B)\), where \(B = 2^{15}\) is the -- length of segment. This constraint comes from the use of segmented sieve.
src/AtCoder/Extra/Monoid/Affine1.hs view
@@ -44,10 +44,10 @@ -- -- ==== __Example__ -- >>> import AtCoder.Extra.Monoid (SegAct(..), Affine1(..))--- >>> import AtCoder.LazySegTree qualified as LST--- >>> seg <- LST.build @_ @(Affine1 Int) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]--- >>> LST.applyIn seg 0 3 $ Affine1 (2, 1) -- [1, 3, 5]--- >>> getSum <$> LST.allProd seg+-- >>> import AtCoder.LazySegTree qualified as LSeg+-- >>> seg <- LSeg.build @_ @(Affine1 Int) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]+-- >>> LSeg.applyIn seg 0 3 $ Affine1 (2, 1) -- [1, 3, 5]+-- >>> getSum <$> LSeg.allProd seg -- 9 -- -- @since 1.0.0.0
src/AtCoder/Extra/Monoid/Mat2x2.hs view
@@ -48,10 +48,10 @@ -- >>> import AtCoder.Extra.Monoid.Mat2x2 qualified as Mat2x2 -- >>> import AtCoder.Extra.Monoid.V2 qualified as V2 -- >>> import AtCoder.Extra.Monoid (SegAct(..), Mat2x2(..), V2(..))--- >>> import AtCoder.LazySegTree qualified as LST--- >>> seg <- LST.build @_ @(Mat2x2 Int) @(V2 Int) $ VU.generate 3 V2.new -- [0, 1, 2]--- >>> LST.applyIn seg 0 3 $ Mat2x2.new 2 1 -- [1, 3, 5]--- >>> V2.unV2 <$> LST.allProd seg+-- >>> import AtCoder.LazySegTree qualified as LSeg+-- >>> seg <- LSeg.build @_ @(Mat2x2 Int) @(V2 Int) $ VU.generate 3 V2.new -- [0, 1, 2]+-- >>> LSeg.applyIn seg 0 3 $ Mat2x2.new 2 1 -- [1, 3, 5]+-- >>> V2.unV2 <$> LSeg.allProd seg -- 9 -- -- @since 1.1.0.0
src/AtCoder/Extra/Monoid/RangeAdd.hs view
@@ -28,20 +28,20 @@ -- -- ==== __Example (action on @Sum@)__ -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))--- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import AtCoder.LazySegTree qualified as LSeg -- >>> import Data.Semigroup (Sum(..))--- >>> seg <- LST.build @_ @(RangeAdd (Sum Int)) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]--- >>> LST.applyIn seg 0 3 $ RangeAdd (Sum 5) -- [5, 6, 7]--- >>> getSum <$> LST.prod seg 0 3+-- >>> seg <- LSeg.build @_ @(RangeAdd (Sum Int)) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]+-- >>> LSeg.applyIn seg 0 3 $ RangeAdd (Sum 5) -- [5, 6, 7]+-- >>> getSum <$> LSeg.prod seg 0 3 -- 18 -- -- ==== __Example (action on @Max@)__ -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))--- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import AtCoder.LazySegTree qualified as LSeg -- >>> import Data.Semigroup (Max(..))--- >>> seg <- LST.build @_ @(RangeAdd (Max Int)) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]--- >>> LST.applyIn seg 0 3 $ RangeAdd (Max 5) -- [5, 6, 7]--- >>> getMax <$> LST.prod seg 0 3+-- >>> seg <- LSeg.build @_ @(RangeAdd (Max Int)) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]+-- >>> LSeg.applyIn seg 0 3 $ RangeAdd (Max 5) -- [5, 6, 7]+-- >>> getMax <$> LSeg.prod seg 0 3 -- 7 -- -- @since 1.0.0.0
src/AtCoder/Extra/Monoid/RangeSet.hs view
@@ -30,12 +30,12 @@ -- -- ==== __Example__ -- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeSet(..))--- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import AtCoder.LazySegTree qualified as LSeg -- >>> import Data.Bit (Bit (..)) -- >>> import Data.Semigroup (Product(..))--- >>> seg <- LST.build @_ @(RangeSet (Product Int)) @(Product Int) $ VU.generate 4 Product -- [0, 1, 2, 3]--- >>> LST.applyIn seg 0 3 $ RangeSet (Bit True, Product 5) -- [5, 5, 5, 3]--- >>> getProduct <$> LST.prod seg 0 4+-- >>> seg <- LSeg.build @_ @(RangeSet (Product Int)) @(Product Int) $ VU.generate 4 Product -- [0, 1, 2, 3]+-- >>> LSeg.applyIn seg 0 3 $ RangeSet (Bit True, Product 5) -- [5, 5, 5, 3]+-- >>> getProduct <$> LSeg.prod seg 0 4 -- 375 -- -- @since 1.0.0.0
src/AtCoder/Extra/Monoid/RollingHash.hs view
@@ -10,6 +10,48 @@ -- Combining `RollingHash` with `SegTree` enables \(O(\log |s|)\) string slice creation and -- \(O(1)\) slice comparison. --+-- ==== __Example__+--+-- Import:+--+-- >>> import AtCoder.Extra.Monoid.RollingHash qualified as RH+-- >>> import AtCoder.SegTree qualified as Seg+-- >>> import Data.ByteString.Char8 qualified as BS+-- >>> import Data.Char (ord)+-- >>> import Data.Vector.Unboxed qualified as VU+--+-- Create a helper method for creating `RollingHash` for a specific base and a modulus:+--+-- >>> type RH = RH.RollingHash 100 998244353+-- >>> :{+-- newRH :: BS.ByteString -> VU.Vector RH+-- newRH = VU.map (RH.new . ord) . VU.fromList . BS.unpack+-- :}+--+-- Create a segment tree of rolling hash monoids:+--+-- >>> let s = BS.pack "ABC_ABC"+-- >>> seg <- Seg.build $ newRH s+--+-- Now, we can create string slices in \(O(\log n)\) and compare them in \(O(1)\) time:+--+-- >>> h1 <- Seg.prod seg 0 3 -- "ABC"+-- >>> h2 <- Seg.prod seg 1 4 -- "BC_"+-- >>> h3 <- Seg.prod seg 4 7 -- "ABC"+--+-- >>> h1 == h2+-- False+--+-- >>> h1 == h3+-- True+--+-- If you need more accurate result, you could use bigger prime, however, note that the performance+-- gets worse (due to the internal implementation):+--+-- @+-- type RH = RH.RollingHash 100 2305843009213693951+-- @+-- -- @since 1.1.0.0 module AtCoder.Extra.Monoid.RollingHash   ( -- * Rolling hash@@ -94,7 +136,7 @@           !hash' = addMod p (hash1 * digit2 `rem` p) hash2        in RollingHash digit' hash'   | otherwise =-      -- TODO: This is slow+      -- FIXME: This is slow       let !digit' = fromIntegral $! to128 digit1 * to128 digit2 `rem` to128 p           !hash' = fromIntegral $! (to128 hash1 * to128 digit2 + to128 hash2) `rem` to128 p        in RollingHash digit' hash'
src/AtCoder/Extra/Monoid/V2.hs view
@@ -32,11 +32,11 @@ -- >>> import AtCoder.Extra.Monoid.Mat2x2 qualified as Mat2x2 -- >>> import AtCoder.Extra.Monoid.V2 (V2(..)) -- >>> import AtCoder.Extra.Monoid.V2 qualified as V2--- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import AtCoder.LazySegTree qualified as LSeg -- >>> import Data.Vector.Unboxed qualified as VU--- >>> seg <- LST.build @_ @(Mat2x2 Int) @(V2 Int) . VU.map V2.new $ VU.fromList [1, 2, 3, 4]--- >>> LST.applyIn seg 1 3 $ Mat2x2.new 2 1 -- [1, 5, 7, 4]--- >>> V2.unV2 <$> LST.prod seg 1 3+-- >>> seg <- LSeg.build @_ @(Mat2x2 Int) @(V2 Int) . VU.map V2.new $ VU.fromList [1, 2, 3, 4]+-- >>> LSeg.applyIn seg 1 3 $ Mat2x2.new 2 1 -- [1, 5, 7, 4]+-- >>> V2.unV2 <$> LSeg.prod seg 1 3 -- 12 -- -- @since 1.1.0.0
src/AtCoder/LazySegTree.hs view
@@ -22,46 +22,46 @@ -- Here we'll use `AtCoder.Extra.Monoid.Affine1` as a monoid action \(F\) and `Data.Semigroup.Sum` -- as the acted monoid \(S\): ----- >>> import AtCoder.LazySegTree qualified as LST+-- >>> import AtCoder.LazySegTree qualified as LSeg -- >>> import AtCoder.Extra.Monoid (SegAct(..), Affine1(..)) -- `SegAct` is also re-exported in Extra.Monoid. -- >>> import Data.Semigroup (Sum(..)) -- -- Use `build` to construct a `LazySegTree` with initial values. @'build' \@_ \@f \@a@ constructs a -- `LazySegTree` of 'SegAct' @f a@: ----- >>> seg <- LST.build @_ @(Affine1 Int) @(Sum Int) $ VU.fromList [1, 2, 3, 4]+-- >>> seg <- LSeg.build @_ @(Affine1 Int) @(Sum Int) $ VU.fromList [1, 2, 3, 4] -- -- `applyIn` @seg l r f@ applies an action \(f\) to an interval \([l, r)\): ----- >>> LST.applyIn seg 1 3 $ Affine1 (2, 1) -- [1, 5, 7, 4]+-- >>> LSeg.applyIn seg 1 3 $ Affine1 (2, 1) -- [1, 5, 7, 4] -- -- Modify one element with `write`, `modify`, `modifyM` or `applyAt`: ----- >>> LST.write seg 3 $ Sum 10 -- [1, 5, 7, 10]--- >>> LST.modify seg (+ 1) 0   -- [2, 5, 7, 10]+-- >>> LSeg.write seg 3 $ Sum 10 -- [1, 5, 7, 10]+-- >>> LSeg.modify seg (+ 1) 0   -- [2, 5, 7, 10] -- -- Read the values with `read`, `prod` or `allProd`: ----- >>> LST.read seg 1+-- >>> LSeg.read seg 1 -- Sum {getSum = 5} ----- >>> LST.prod seg 0 3 -- product (fold) of `Sum Int` in interval [0, 3)+-- >>> LSeg.prod seg 0 3 -- product (fold) of `Sum Int` in interval [0, 3) -- Sum {getSum = 14} ----- >>> LST.allProd seg+-- >>> LSeg.allProd seg -- Sum {getSum = 24} -- -- Run binary search: ----- >>> LST.maxRight seg 0 (<= (Sum 10)) -- sum [0, 2) = 7 <= 10+-- >>> LSeg.maxRight seg 0 (<= (Sum 10)) -- sum [0, 2) = 7 <= 10 -- 2 ----- >>> LST.minLeft seg 4 (<= (Sum 10)) -- sum [3, 4) = 10 <= 10+-- >>> LSeg.minLeft seg 4 (<= (Sum 10)) -- sum [3, 4) = 10 <= 10 -- 3 -- -- Inspect all the values in \(O(n \log n)\) with `freeze` or `unsafeFreeze`: ----- >>> VU.map getSum <$> LST.freeze seg+-- >>> VU.map getSum <$> LSeg.freeze seg -- [2,5,7,10] -- -- ==== Tips@@ -155,7 +155,7 @@ -- @ -- {-# LANGUAGE TypeFamilies #-} ----- import AtCoder.LazySegTree qualified as LST+-- import AtCoder.LazySegTree qualified as LSeg -- import AtCoder.LazySegTree (SegAct (..)) -- import Data.Monoid -- import Data.Vector.Generic qualified as VG@@ -201,7 +201,7 @@ -- {-# LANGUAGE DerivingStrategies #-} -- {-# LANGUAGE TypeFamilies #-} ----- import AtCoder.LazySegTree qualified as LST+-- import AtCoder.LazySegTree qualified as LSeg -- import AtCoder.LazySegTree (SegAct (..)) -- import Data.Vector.Generic qualified as VG -- import Data.Vector.Generic.Mutable qualified as VGM@@ -260,15 +260,15 @@ -- -- main :: IO () -- main = do---   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]---   !_ \<- (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+--   seg <- LSeg.build @_ @F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]+--   LSeg.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]+--   LSeg.write seg 3 $ X 10 -- [1, 5, 7, 10]+--   LSeg.modify seg (+ (X 1)) 0   -- [2, 5, 7, 10]+--   !_ \<- (expect "test 1" (X 5)) \<$> LSeg.read seg 1+--   !_ \<- (expect "test 2" (X 14)) \<$> LSeg.prod seg 0 3 -- reads an interval [0, 3)+--   !_ \<- (expect "test 3" (X 24)) \<$> LSeg.allProd seg+--   !_ \<- (expect "test 4" 2) \<$> LSeg.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10+--   !_ \<- (expect "test 5" 3) \<$> LSeg.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10 --   putStrLn "=> test passed!" -- @ --
+ test/Tests/Extra/AhoCorasick.hs view
@@ -0,0 +1,107 @@+module Tests.Extra.AhoCorasick where++import AtCoder.Extra.AhoCorasick qualified as Ac+import Data.Char (ord)+import Data.List qualified as L+import Data.Vector qualified as V+import Data.Vector.Algorithms qualified as VA+import Data.Vector.Algorithms.Intro qualified as VAI+import Data.Vector.Generic qualified as VG+import Data.Vector.Unboxed qualified as VU+import Test.Tasty+import Test.Tasty.HUnit+import Test.Tasty.QuickCheck as QC++rng :: (Int, Int)+rng = (1, 32)++-- | Generates non-empty string as a vector.+genString :: Gen (VU.Vector Int)+genString = do+  VU.fromList <$> QC.listOf1 QC.arbitrary++-- | Generates non-empty strings as a vectors.+-- not empty+genStrings :: Gen (V.Vector (VU.Vector Int))+genStrings = do+  n <- QC.chooseInt rng+  V.fromList <$> QC.vectorOf n genString++prop_empty :: QC.Positive Int -> Bool+prop_empty (QC.Positive n) = do+  -- Not dies+  let !ac0 = Ac.build V.empty+   in True++prop_numberOfNodes :: TestTree+prop_numberOfNodes = QC.testProperty "numberOfNodes" $ do+  patterns <- genStrings+  let !ac = Ac.build patterns+  pure $ Ac.size ac <= (1 + VG.sum (VG.map VG.length patterns))++unit_banana :: TestTree+unit_banana = testCase "banana" $ do+  let patterns =+        V.fromList $+          map+            (VU.map ord . VU.fromList)+            ["banana", "benefit", "banapple", "ban", "fit"]+  let text = VU.map ord $ VU.fromList "banana bans, apple benefits."+  --                        positions:+  --                                   0123456789012345678901234567+  --                                   0         1         2+  --                        5 matches:+  --                                   ban*   ban*        benefit*+  --                                   banana*                fit*++  let ac = Ac.build patterns+  let matches = Ac.match ac text+  matches @?= VU.fromList [(3, 3), (6, 0), (10, 3), (26, 1), (26, 4)]++genAlphabet :: Gen [Int]+genAlphabet = do+  n <- QC.chooseInt (1, 26)+  L.nub <$> QC.vectorOf n QC.arbitrary++genPatternIn :: [Int] -> Gen (VU.Vector Int)+genPatternIn alphabet = do+  n <- QC.chooseInt (1, 6)+  VU.fromList <$> QC.vectorOf n (QC.elements alphabet)++genTextIn :: [Int] -> Gen (VU.Vector Int)+genTextIn alphabet = do+  n <- QC.chooseInt (0, 1000)+  VU.fromList <$> QC.vectorOf n (QC.elements alphabet)++-- | Returns a vector of @(endPos, patternId)@+naiveMatch :: (HasCallStack) => V.Vector (VU.Vector Int) -> VU.Vector Int -> VU.Vector (Int, Int)+naiveMatch patterns text = VU.concatMap f $ VU.generate (VU.length text) (+ 1)+  where+    nPatterns = V.length patterns+    f :: (HasCallStack) => Int -> VU.Vector (Int, Int)+    f endPos = VU.map (endPos,) . VU.filter (test endPos) $ VU.generate nPatterns id+    test endPos iPattern = t == pat+      where+        pat = patterns VG.! iPattern+        len = VU.length pat+        t = VU.drop (endPos - len) $ VU.take endPos text++prop_random :: TestTree+prop_random = QC.testProperty "random" $ do+  alphabet <- genAlphabet+  n <- QC.chooseInt (1, 100)+  -- NOTE: Patterns must be deduplicated in order to get exact result+  patterns <- VA.nub . V.fromList <$> QC.vectorOf n (genPatternIn alphabet)+  let !ac = Ac.build patterns+  text <- genTextIn alphabet+  pure+    . QC.counterexample (show (patterns, "in", text))+    $ VG.modify VAI.sort (Ac.match ac text) QC.=== VG.modify VAI.sort (naiveMatch patterns text)++tests :: [TestTree]+tests =+  [ QC.testProperty "empty" prop_empty,+    prop_numberOfNodes,+    unit_banana,+    prop_random+  ]
+ test/Tests/Extra/DsuMonoid.hs view
@@ -0,0 +1,62 @@+-- | Disjoint set union tests.+module Tests.Extra.DsuMonoid (tests) where++import AtCoder.Extra.DsuMonoid qualified as Dsu+import Data.Foldable+import Data.Semigroup (Sum (..))+import Data.Vector qualified as V+import System.IO.Unsafe (unsafePerformIO)+import Test.Hspec+import Test.Tasty+import Test.Tasty.HUnit+import Test.Tasty.Hspec++unit_zero :: TestTree+unit_zero = testCase "zero" $ do+  uf <- Dsu.new @_ @(Sum Int) 0+  (@?= V.empty) =<< Dsu.groups uf++-- empty+-- assign++unit_simple :: TestTree+unit_simple = testCase "simple" $ do+  uf <- Dsu.new @_ @(Sum Int) 2+  (@?= False) =<< Dsu.same uf 0 1+  x <- Dsu.merge uf 0 1+  (@?= x) =<< Dsu.leader uf 0+  (@?= x) =<< Dsu.leader uf 1+  (@?= True) =<< Dsu.same uf 0 1+  (@?= 2) =<< Dsu.size uf 0++unit_line :: TestTree+unit_line = testCase "line" $ do+  let n = 500000+  uf <- Dsu.new @_ @(Sum Int) n+  for_ [0 .. n - 2] $ \i -> do+    Dsu.merge uf i (i + 1)+  (@?= n) =<< Dsu.size uf 0+  (@?= 1) . V.length =<< Dsu.groups uf++unit_lineReverse :: TestTree+unit_lineReverse = testCase "lineReverse" $ do+  let n = 500000+  uf <- Dsu.new @_ @(Sum Int) n+  for_ [n - 2, n - 3 .. 0] $ \i -> do+    Dsu.merge uf i (i + 1)+  (@?= n) =<< Dsu.size uf 0+  (@?= 1) . V.length =<< Dsu.groups uf++spec_invalid :: IO TestTree+spec_invalid = testSpec "invalid" $ do+  it "throws error" $ do+    Dsu.new @_ @(Sum Int) (-1) `shouldThrow` anyException++tests :: [TestTree]+tests =+  [ unit_zero,+    unit_simple,+    unit_line,+    unit_lineReverse,+    unsafePerformIO spec_invalid+  ]
test/Tests/LazySegTree.hs view
@@ -4,7 +4,7 @@ module Tests.LazySegTree (tests) where  import AtCoder.Extra.Monoid (Affine1)-import AtCoder.LazySegTree qualified as LST+import AtCoder.LazySegTree qualified as LSeg import Data.Foldable (for_) import Data.Semigroup (Max (..), Sum (..)) import Data.Vector.Generic qualified as VG@@ -18,97 +18,97 @@ import Test.Tasty.Hspec  -- | AddMax. FIXME: Orphan instance.-instance LST.SegAct (Sum Int) (Max Int) where+instance LSeg.SegAct (Sum Int) (Max Int) where   {-# INLINE segAct #-}   segAct (Sum !dx) (Max !x) = Max $ dx + x  unit_zero :: TestTree unit_zero = testCase "zero" $ do   do-    s <- LST.new @_ @(Sum Int) @(Max Int) 0-    (@?= mempty) =<< LST.allProd s-    (@?= VU.empty) =<< LST.unsafeFreeze s-    (@?= VU.empty) =<< LST.freeze s+    s <- LSeg.new @_ @(Sum Int) @(Max Int) 0+    (@?= mempty) =<< LSeg.allProd s+    (@?= VU.empty) =<< LSeg.unsafeFreeze s+    (@?= VU.empty) =<< LSeg.freeze s   do-    s <- LST.new @_ @(Sum Int) @(Max Int) 10-    (@?= mempty) =<< LST.allProd s+    s <- LSeg.new @_ @(Sum Int) @(Max Int) 10+    (@?= mempty) =<< LSeg.allProd s  -- Extra test for freeze unit_one :: TestTree unit_one = testCase "one" $ do-  s <- LST.build @_ @(Sum Int) @(Max Int) $ VU.singleton (Max 10)-  (@?= Max 10) =<< LST.allProd s-  (@?= VU.singleton (Max 10)) =<< LST.unsafeFreeze s-  (@?= VU.singleton (Max 10)) =<< LST.freeze s+  s <- LSeg.build @_ @(Sum Int) @(Max Int) $ VU.singleton (Max 10)+  (@?= Max 10) =<< LSeg.allProd s+  (@?= VU.singleton (Max 10)) =<< LSeg.unsafeFreeze s+  (@?= VU.singleton (Max 10)) =<< LSeg.freeze s  -- assign  spec_invalid :: IO TestTree spec_invalid = testSpec "invalid" $ do-  it "throws error" $ LST.new @_ @(Sum Int) @(Max Int) (-1) `shouldThrow` anyException-  s <- runIO $ LST.new @_ @(Sum Int) @(Max Int) 10+  it "throws error" $ LSeg.new @_ @(Sum Int) @(Max Int) (-1) `shouldThrow` anyException+  s <- runIO $ LSeg.new @_ @(Sum Int) @(Max Int) 10 -  it "throws error" $ LST.read s (-1) `shouldThrow` anyException-  it "throws error" $ LST.read s 10 `shouldThrow` anyException+  it "throws error" $ LSeg.read s (-1) `shouldThrow` anyException+  it "throws error" $ LSeg.read s 10 `shouldThrow` anyException -  it "throws error" $ LST.prod s (-1) (-1) `shouldThrow` anyException-  it "throws error" $ LST.prod s 3 2 `shouldThrow` anyException-  it "throws error" $ LST.prod s 0 11 `shouldThrow` anyException-  it "throws error" $ LST.prod s (-1) 11 `shouldThrow` anyException+  it "throws error" $ LSeg.prod s (-1) (-1) `shouldThrow` anyException+  it "throws error" $ LSeg.prod s 3 2 `shouldThrow` anyException+  it "throws error" $ LSeg.prod s 0 11 `shouldThrow` anyException+  it "throws error" $ LSeg.prod s (-1) 11 `shouldThrow` anyException -  it "throws error" $ LST.minLeft s (-1) (const True) `shouldThrow` anyException-  it "throws error" $ LST.maxRight s 0 (const False) `shouldThrow` anyException+  it "throws error" $ LSeg.minLeft s (-1) (const True) `shouldThrow` anyException+  it "throws error" $ LSeg.maxRight s 0 (const False) `shouldThrow` anyException  -- TODO: verify yosupo  unit_naiveProd :: TestTree unit_naiveProd = testCase "naiveProd" $ do   for_ [0 .. 50] $ \n -> do-    seg <- LST.new @_ @(Sum Int) @(Max Int) n+    seg <- LSeg.new @_ @(Sum Int) @(Max Int) n     p <- VUM.replicate n mempty     for_ [0 .. n - 1] $ \i -> do       VGM.write p i . Max $ (i * i + 100) `mod` 31-      LST.write seg i =<< VGM.read p i+      LSeg.write seg i =<< VGM.read p i      p' <- VU.unsafeFreeze p     for_ [0 .. n] $ \l -> do       for_ [l .. n] $ \r -> do         let expected = VU.foldl' (<>) mempty $ VU.slice l (r - l) p'-        (@?= expected) =<< LST.prod seg l r+        (@?= expected) =<< LSeg.prod seg l r      if even n       then do         -- read (extra test)         for_ [0 .. n - 1] $ \i -> do-          (@?= p' VG.! i) =<< LST.read seg i+          (@?= p' VG.! i) =<< LSeg.read seg i       else do         -- freeze (extra test)-        (@?= p') =<< LST.unsafeFreeze seg+        (@?= p') =<< LSeg.unsafeFreeze seg  unit_usage :: TestTree unit_usage = testCase "usage" $ do-  seg <- LST.build @_ @(Sum Int) $ VU.replicate 10 (Max (0 :: Int))-  (@?= Max 0) =<< LST.allProd seg-  LST.applyIn seg 0 3 $ Sum 5-  (@?= Max 5) =<< LST.allProd seg-  LST.applyAt seg 2 $ Sum (-10)-  (@?= Max (-5)) =<< LST.prod seg 2 3-  (@?= Max 5) =<< LST.allProd seg-  (@?= Max 0) =<< LST.prod seg 2 4+  seg <- LSeg.build @_ @(Sum Int) $ VU.replicate 10 (Max (0 :: Int))+  (@?= Max 0) =<< LSeg.allProd seg+  LSeg.applyIn seg 0 3 $ Sum 5+  (@?= Max 5) =<< LSeg.allProd seg+  LSeg.applyAt seg 2 $ Sum (-10)+  (@?= Max (-5)) =<< LSeg.prod seg 2 3+  (@?= Max 5) =<< LSeg.allProd seg+  (@?= Max 0) =<< LSeg.prod seg 2 4  unit_prodMaybeBounds :: TestTree unit_prodMaybeBounds = testCase "prodMaybeBounds" $ do-  seg <- LST.new @_ @(Affine1 Int) @(Sum Int) 4-  (@?= Just (Sum {getSum = 0})) =<< LST.prodMaybe seg 0 0-  (@?= Just (Sum {getSum = 0})) =<< LST.prodMaybe seg 0 4-  (@?= Just (Sum {getSum = 0})) =<< LST.prodMaybe seg 4 4-  (@?= Nothing) =<< LST.prodMaybe seg (-1) 4-  (@?= Nothing) =<< LST.prodMaybe seg 0 5-  (@?= Nothing) =<< LST.prodMaybe seg 0 (-1)-  (@?= Nothing) =<< LST.prodMaybe seg (-1) (-1)-  (@?= Nothing) =<< LST.prodMaybe seg (-1) 0-  (@?= Nothing) =<< LST.prodMaybe seg 4 5-  (@?= Nothing) =<< LST.prodMaybe seg 5 5+  seg <- LSeg.new @_ @(Affine1 Int) @(Sum Int) 4+  (@?= Just (Sum {getSum = 0})) =<< LSeg.prodMaybe seg 0 0+  (@?= Just (Sum {getSum = 0})) =<< LSeg.prodMaybe seg 0 4+  (@?= Just (Sum {getSum = 0})) =<< LSeg.prodMaybe seg 4 4+  (@?= Nothing) =<< LSeg.prodMaybe seg (-1) 4+  (@?= Nothing) =<< LSeg.prodMaybe seg 0 5+  (@?= Nothing) =<< LSeg.prodMaybe seg 0 (-1)+  (@?= Nothing) =<< LSeg.prodMaybe seg (-1) (-1)+  (@?= Nothing) =<< LSeg.prodMaybe seg (-1) 0+  (@?= Nothing) =<< LSeg.prodMaybe seg 4 5+  (@?= Nothing) =<< LSeg.prodMaybe seg 5 5  -- maxRight and minLeft are tested in the stress test file.
test/Tests/LazySegTreeStress.hs view
@@ -5,7 +5,7 @@  module Tests.LazySegTreeStress (tests) where -import AtCoder.LazySegTree qualified as LST+import AtCoder.LazySegTree qualified as LSeg import Control.Monad.Primitive (PrimMonad, PrimState) import Control.Monad.State (MonadIO, liftIO) import Control.Monad.State.Strict (StateT (..))@@ -80,7 +80,7 @@ instance Monoid T where   mempty = T (-1) -instance LST.SegAct T S where+instance LSeg.SegAct T S where   segAct t@(T newTime) s@(S (!l, !r, !time))     | t == mempty = s     | time >= newTime = error "unreachable"@@ -109,17 +109,17 @@  -- TODO: write type? -- testDriver :: Int ->---    (Int -> LST.LazySegTree (PrimState (StateT UniformGen IO )+--    (Int -> LSeg.LazySegTree (PrimState (StateT UniformGen IO ) testDriver ::   (MonadIO m, PrimMonad m) =>   (Int, Int) ->   Int ->-  (Int -> LST.LazySegTree (PrimState m) T S -> TimeManager (PrimState m) -> Int -> Int -> Int -> StateT StdGen m Int) ->+  (Int -> LSeg.LazySegTree (PrimState m) T S -> TimeManager (PrimState m) -> Int -> Int -> Int -> StateT StdGen m Int) ->   m () testDriver tyRange@(!_, !_) nRepeat f = do   for_ [1 .. 30] $ \n -> do     for_ [1 .. 10 - 1] $ \_ -> do-      seg0 <- LST.build $ VU.generate n $ \i -> S (i, i + 1, -1)+      seg0 <- LSeg.build $ VU.generate n $ \i -> S (i, i + 1, -1)       tm <- TimeManager <$> VUM.replicate n (-1)       runStateGenT_ (mkStdGen 42) $ \g -> do         VU.foldM'_@@ -135,8 +135,8 @@       expected <- freezeTM tm       actual <-         if even n-          then VU.map (\(S (!_, !_, !t)) -> t) <$> LST.freeze seg0-          else VU.map (\(S (!_, !_, !t)) -> t) <$> LST.unsafeFreeze seg0+          then VU.map (\(S (!_, !_, !t)) -> t) <$> LSeg.freeze seg0+          else VU.map (\(S (!_, !_, !t)) -> t) <$> LSeg.unsafeFreeze seg0       liftIO $ actual @?= expected  -- | prod, read, applyIn, applyAt@@ -145,26 +145,26 @@   testDriver (0, 3) 3000 $ \now seg0 tm ty l r -> case ty of     0 -> do       -- prod-      S (!resL, !resR, !resTime) <- LST.prod seg0 l r+      S (!resL, !resR, !resTime) <- LSeg.prod seg0 l r       liftIO $ l @=? resL       liftIO $ r @=? resR       liftIO . (@=? resTime) =<< prod tm l r       pure now     1 -> do       -- read-      S (!resL, !resR, !resTime) <- LST.read seg0 l+      S (!resL, !resR, !resTime) <- LSeg.read seg0 l       liftIO $ l @=? resL       liftIO $ l + 1 @=? resR       liftIO . (@=? resTime) =<< prod tm l (l + 1)       pure now     2 -> do       -- applyIn-      LST.applyIn seg0 l r (T (now + 1))+      LSeg.applyIn seg0 l r (T (now + 1))       action tm l r (now + 1)       pure $ now + 1     3 -> do       -- applyAt-      LST.applyAt seg0 l (T (now + 1))+      LSeg.applyAt seg0 l (T (now + 1))       action tm l (l + 1) (now + 1)       pure $ now + 1     _ -> error "unreachable"@@ -174,7 +174,7 @@   testDriver (0, 2) 1000 $ \now seg0 tm ty l r -> case ty of     0 -> do       -- maxRight-      !_ <- LST.maxRight seg0 l $ \(S (!lS, !rS, !_)) -> case lS of+      !_ <- LSeg.maxRight seg0 l $ \(S (!lS, !rS, !_)) -> case lS of         _           | lS == -1 -> True           | lS /= l -> error "unreachable"@@ -183,7 +183,7 @@           | otherwise -> rS <= r       pure now     _ -> do-      LST.applyIn seg0 l r $ T (now + 1)+      LSeg.applyIn seg0 l r $ T (now + 1)       action tm l r $ now + 1       pure $ now + 1 @@ -192,7 +192,7 @@   testDriver (0, 2) 1000 $ \now seg0 tm ty l r -> case ty of     0 -> do       -- minLeft-      !_ <- LST.minLeft seg0 r $ \(S (!lS, !rS, !_)) -> case lS of+      !_ <- LSeg.minLeft seg0 r $ \(S (!lS, !rS, !_)) -> case lS of         _           | lS == -1 -> True           | rS /= r -> error "unreachable"@@ -201,7 +201,7 @@           | otherwise -> l <= lS       pure now     _ -> do-      LST.applyIn seg0 l r $ T (now + 1)+      LSeg.applyIn seg0 l r $ T (now + 1)       action tm l r $ now + 1       pure $ now + 1