Storages of dynamic sequences of monoid values with monoid actions on them through the SegAct instance.

Since: 1.2.0.0

Mutable Handle of an Index.

Since: 1.2.0.0

$O(1)$ Creates a new sequence Handle from a root node index.

Since: 1.2.0.0

$O(1)$ Returns whether the sequence is empty.

Since: 1.2.0.0

$O(1)$ Invalidates a sequence handle. Note that it does not change or free the sequence.

Since: 1.2.0.0

Typeclass reprentation of the LazySegTree properties. User can implement either segAct or segActWithLength.

Instances should satisfy the follwing properties:

Left monoid action

segAct (f2 <> f1) x = segAct f2 (segAct f1 x)

Identity map

segAct mempty x = x

Endomorphism

segAct f (x1 <> x2) = (segAct f x1) <> (segAct f x2)

If you implement SegAct via segActWithLength, satisfy one more propety:

Linear left monoid action

segActWithLength len f (stimes len a) = stimes len (segAct f a).

Invariant

In SegAct instances, new semigroup values are always given from the left: new <> old. The order is important for non-commutative monoid implementations.

Example instance

{-# LANGUAGE TypeFamilies #-}

import AtCoder.LazySegTree qualified as LST
import AtCoder.LazySegTree (SegAct (..))
import Data.Monoid
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

-- | f x = a * x + b. It's implemented as a newtype of `(a, a)` for easy Unbox deriving.
newtype Affine1 a = Affine1 (Affine1 a)
  deriving newtype (Eq, Ord, Show)

-- | This type alias makes the Unbox deriving easier, described velow.
type Affine1Repr a = (a, a)

instance (Num a) => Semigroup (Affine1 a) where
  {-# INLINE (<>) #-}
  (Affine1 (!a1, !b1)) <> (Affine1 (!a2, !b2)) = Affine1 (a1 * a2, a1 * b2 + b1)

instance (Num a) => Monoid (Affine1 a) where
  {-# INLINE mempty #-}
  mempty = Affine1 (1, 0)

instance (Num a) => SegAct (Affine1 a) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength len (Affine1 (!a, !b)) !x = a * x + b * fromIntegral len

newtype instance VU.MVector s (Affine1 a) = MV_Affine1 (VU.MVector s (Affine1 a))
newtype instance VU.Vector (Affine1 a) = V_Affine1 (VU.Vector (Affine1 a))
deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1 a)
deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1 a)
instance (VU.Unbox a) => VU.Unbox (Affine1 a)

Example contest template

{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE TypeFamilies #-}

import AtCoder.LazySegTree qualified as LST
import AtCoder.LazySegTree (SegAct (..))
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

{- ORMOLU_DISABLE -}
-- | F is a custom monoid action, defined as a newtype of FRepr.
newtype F = F FRepr deriving newtype (Eq, Ord, Show) ; unF :: F -> FRepr ; unF (F x) = x ; newtype instance VU.MVector s F = MV_F (VU.MVector s FRepr) ; newtype instance VU.Vector F = V_F (VU.Vector FRepr) ; deriving instance VGM.MVector VUM.MVector F ; deriving instance VG.Vector VU.Vector F ; instance VU.Unbox F ;
{- ORMOLU_ENABLE -}

-- | Affine: f x = a * x + b
type FRepr = (Int, Int)

instance Semigroup F where
  -- new <> old
  {-# INLINE (<>) #-}
  (F (!a1, !b1)) <> (F (!a2, !b2)) = F (a1 * a2, a1 * b2 + b1)

instance Monoid F where
  {-# INLINE mempty #-}
  mempty = F (1, 0)

{- ORMOLU_DISABLE -}
-- | X is a custom acted monoid, defined as a newtype of XRepr.
newtype X = X XRepr deriving newtype (Eq, Ord, Show) ; unX :: X -> XRepr ; unX (X x) = x; newtype instance VU.MVector s X = MV_X (VU.MVector s XRepr) ; newtype instance VU.Vector X = V_X (VU.Vector XRepr) ; deriving instance VGM.MVector VUM.MVector X ; deriving instance VG.Vector VU.Vector X ; instance VU.Unbox X ;
{- ORMOLU_ENABLE -}

-- | Acted Int (same as `Sum Int`).
type XRepr = Int

deriving instance Num X; -- in our case X is a Num.

instance Semigroup X where
  {-# INLINE (<>) #-}
  (X x1) <> (X x2) = X $! x1 + x2

instance Monoid X where
  {-# INLINE mempty #-}
  mempty = X 0

instance SegAct F X where
  -- {-# INLINE segAct #-}
  -- segAct len (F (!a, !b)) (X x) = X $! a * x + b
  {-# INLINE segActWithLength #-}
  segActWithLength len (F (!a, !b)) (X x) = X $! a * x + len * b

expect :: (Eq a, Show a) => String -> a -> a -> ()
expect msg a b
  | a == b = ()
  | otherwise = error $ msg ++ ": expected " ++ show a ++ ", found " ++ show b

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
  putStrLn "=> test passed!"

Since: 1.0.0.0

$O(n)$ Creates a new Seq of length $n$.

Since: 1.2.0.0

$O(1)$ Clears the sequence storage. All the handles must not be used again.

Since: 1.2.0.0

$O(n)$ Frees a sequence and invalidates the handle.

Since: 1.2.0.0

$O(1)$ Allocates a new sequence of length $1$.

Since: 1.2.0.0

$O(n)$ Allocates a new sequence.

Since: 1.2.0.0

$O(1)$ Returns the capacity of the sequence storage.

Since: 1.2.1.0

$O(1)$ Returns the length of the sequence.

Since: 1.2.1.0

Amortized $O(\log n)$. Merges two sequences $l, r$ into one in the given order, ignoring empty sequences. The right sequence handle will be invalidated.

Since: 1.2.0.0

Amortized $O(\log n)$. Merges three sequences $l, m, r$ into one in the given order, ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.

Since: 1.2.0.0

Amortized $O(\log n)$. Merges four sequences $a, b, c, d$ into one in the given order, ignoring empty sequences. All handles, except for the leftmost one, will be invalidated.

Constraints

• The vertices must be roots.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequences into two: $[0, k), [k, n)$. The handle will point to the left sequence. Returns the right sequence handle.

Constraints

• $0 \le k \le n$.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequences into three: $[0, l), [l, r), [r, n)$. The handle will point to the leftmost sequence. Returns the middle and the right sequence handles.

Constraints

• $0 \le l \le r \le n$.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequences into four: $[0, i), [i, j), [j, k), [k, n)$. The handle will point to the leftmost sequence. Returns the non-leftmost sequence handles.

Constraints

• $0 \le i \le j \le k \le n$.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequence into three: $[0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)$.

Constraints

• The sequence must be non-empty.

Since: 1.2.0.0

Amortized $O(\log n)$. Reads the $k$-th node's monoid value.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Reads the $k$-th node's monoid value.

Since: 1.2.0.0

Amortized $O(\log n)$. Writes to the $k$-th node's monoid value.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Modifies the $k$-th node's monoid value.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Exchanges the $k$-th node's monoid value.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Returns the monoid product in an interval $[l, r)$.

Constraints

• $0 \le l \le r \le n$

Since: 1.2.0.0

Amortized $O(\log n)$. Returns the monoid product in an interval $[l, r)$. Returns Nothing if the interval is invalid.

Since: 1.2.0.0

Amortized $O(\log n)$. Returns the monoid product of the whole sequence.

Since: 1.2.0.0

Amortized $O(\log n)$. Given an interval $[l, r)$, applies a monoid action $f$.

Constraints

• $0 \le l \le r \le n$

Since: 1.2.0.0

$O(1)$ Applies a monoid action $f$ to the root of a sequence.

Since: 1.2.0.0

Amortized $O(\log n)$. Reverses the sequence in $[l, r)$.

Constraints

• The monoid action $f$ must be commutative.
• The monoid value $v$ must be commutative.

Since: 1.2.0.0

Amortized $O(\log n)$. Inserts a new node at $k$ with initial monoid value $v$. This function works for an empty sequence handle.

Constraints

• $0 \le k \le n$

Since: 1.2.0.0

Amortized $O(\log n)$. Frees the $k$-th node and returns the monoid value of it.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Frees the $k$-th node.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$. Detaches the $k$-th node and returns a handle for it.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Amortized $O(\log n)$.

Since: 1.2.0.0

Amortized $O(\log n)$.

Since: 1.2.0.0

Amortized $O(\log n)$.

Since: 1.2.0.0

Amortized $O(\log n)$.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequence into two with the user predicate and returns the right sequence handle.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequence into two with the user predicate and returns the right sequence handle.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequence into two with the user predicate and returns the right sequence handle.

Since: 1.2.0.0

Amortized $O(\log n)$. Splits a sequence into two with the user predicate and returns the right sequence handle.

Since: 1.2.0.0

Amortized $O(n)$. Returns the sequence of monoid values.

Since: 1.2.0.0