| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Monoid
Description
Extra module of pre-defined SegAct instances and helpful monoids.
Since: 1.0.0.0
Synopsis
- class Monoid f => SegAct f a where
- segAct :: f -> a -> a
- segActWithLength :: Int -> f -> a -> a
- newtype Affine1 a = Affine1 (Affine1Repr a)
- type Affine1Repr a = (a, a)
- newtype Mat2x2 a = Mat2x2 (Mat2x2Repr a)
- type Mat2x2Repr a = (a, a, a, a)
- newtype V2 a = V2 (V2Repr a)
- type V2Repr a = (a, a)
- newtype RangeAdd a = RangeAdd a
- newtype RangeSet a = RangeSet (RangeSetRepr a)
- type RangeSetRepr a = (Bit, a)
- data RollingHash b p
Re-exports
It's mainly a list. It is recommended to use specific submodules.
SegAct
class Monoid f => SegAct f a where Source #
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 =segActf2 (segActf1 x)- Identity map
segActmemptyx = x- Endomorphism
segActf (x1<>x2) = (segActf x1)<>(segActf x2)
If you implement SegAct via segActWithLength, satisfy one more propety:
- Linear left monoid action
segActWithLengthlen f a =stimeslen (segActf a) a
Invariant
In SegAct instances, new semigroup values are always given from the left: new . The
order is important for non-commutative monoid implementations.<> old
Example instance
Take Affine1 as an example of type \(F\).
{-# 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
Deriving Unbox is very easy for such a newtype (though the efficiency is
not the maximum):
newtype instance VU.MVector s (Affine1a) = MV_Affine1 (VU.MVector s (Affine1a)) newtype instance VU.Vector (Affine1a) = V_Affine1 (VU.Vector (Affine1a)) deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1a) deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1a) instance (VU.Unbox a) => VU.Unbox (Affine1a)
Example contest template
Define your monoid action F and your acted monoid X:
{-# 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
It's tested as below:
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
Minimal complete definition
Nothing
Methods
segAct :: f -> a -> a Source #
Lazy segment tree action \(f(x)\).
Since: 1.0.0.0
segActWithLength :: Int -> f -> a -> a Source #
Lazy segment tree action \(f(x)\) with the target monoid's length.
If you implement SegAct with this function, you don't have to store the monoid's length,
since it's given externally.
Since: 1.0.0.0
Instances
| Monoid a => SegAct (RangeSet a) a Source # | Since: 1.0.0.0 |
Defined in AtCoder.Extra.Monoid.RangeSet | |
| Num a => SegAct (Affine1 (Sum a)) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Affine1 a) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Mat2x2 a) (V2 a) Source # | Since: 1.1.0.0 |
| Monoid (Max a) => SegAct (RangeAdd (Max a)) (Max a) Source # | Since: 1.1.0.0 |
| Monoid (Min a) => SegAct (RangeAdd (Min a)) (Min a) Source # | Since: 1.1.0.0 |
| Monoid (Sum a) => SegAct (RangeAdd (Sum a)) (Sum a) Source # | Since: 1.1.0.0 |
| Num a => SegAct (Dual (Affine1 (Sum a))) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Dual (Affine1 a)) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source # | Since: 1.1.0.0 |
Affine1
Monoid action \(f: x \rightarrow ax + b\).
- Use
Mat2x2if inverse operations are required, or if it's necessary to store the monoid length in the acted monoid (V2).
Composition and dual
The affine transformation acts as a left monoid action: \(f_2 (f_1 v) = (f_2 \circ f_1) v\). To
apply the leftmost transformation first in a segment tree, wrap Affine1 in Data.Monoid.Dual.
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 seg9
Since: 1.0.0.0
Constructors
| Affine1 (Affine1Repr a) |
Instances
type Affine1Repr a = (a, a) Source #
Mat2x2
Monoid action \(f: x \rightarrow ax + b\). Less efficient than Affine1, but compatible with
inverse opereations.
Composition and dual
The affine transformation acts as a left monoid action: \(f_2 (f_1 v) = (f_2 \circ f_1) v\). To
apply the leftmost transformation first in a segment tree, wrap Mat2x2 in Data.Monoid.Dual.
Example
>>>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 seg9
Since: 1.1.0.0
Constructors
| Mat2x2 (Mat2x2Repr a) |
Instances
type Mat2x2Repr a = (a, a, a, a) Source #
A monoid acted on by Mat2x2, an affine transformation target.
Since: 1.1.0.0
Instances
| Unbox a => Vector Vector (V2 a) Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Monoid.V2 Methods basicUnsafeFreeze :: Mutable Vector s (V2 a) -> ST s (Vector (V2 a)) basicUnsafeThaw :: Vector (V2 a) -> ST s (Mutable Vector s (V2 a)) basicLength :: Vector (V2 a) -> Int basicUnsafeSlice :: Int -> Int -> Vector (V2 a) -> Vector (V2 a) basicUnsafeIndexM :: Vector (V2 a) -> Int -> Box (V2 a) basicUnsafeCopy :: Mutable Vector s (V2 a) -> Vector (V2 a) -> ST s () | |
| Unbox a => MVector MVector (V2 a) Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Monoid.V2 Methods basicLength :: MVector s (V2 a) -> Int basicUnsafeSlice :: Int -> Int -> MVector s (V2 a) -> MVector s (V2 a) basicOverlaps :: MVector s (V2 a) -> MVector s (V2 a) -> Bool basicUnsafeNew :: Int -> ST s (MVector s (V2 a)) basicInitialize :: MVector s (V2 a) -> ST s () basicUnsafeReplicate :: Int -> V2 a -> ST s (MVector s (V2 a)) basicUnsafeRead :: MVector s (V2 a) -> Int -> ST s (V2 a) basicUnsafeWrite :: MVector s (V2 a) -> Int -> V2 a -> ST s () basicClear :: MVector s (V2 a) -> ST s () basicSet :: MVector s (V2 a) -> V2 a -> ST s () basicUnsafeCopy :: MVector s (V2 a) -> MVector s (V2 a) -> ST s () basicUnsafeMove :: MVector s (V2 a) -> MVector s (V2 a) -> ST s () basicUnsafeGrow :: MVector s (V2 a) -> Int -> ST s (MVector s (V2 a)) | |
| Num a => Monoid (V2 a) Source # | Since: 1.1.0.0 |
| Num a => Semigroup (V2 a) Source # | Since: 1.1.0.0 |
| Show a => Show (V2 a) Source # | Since: 1.1.0.0 |
| Eq a => Eq (V2 a) Source # | Since: 1.1.0.0 |
| Ord a => Ord (V2 a) Source # | Since: 1.1.0.0 |
| Unbox a => Unbox (V2 a) Source # | Since: 1.1.0.0 |
Defined in AtCoder.Extra.Monoid.V2 | |
| Num a => SegAct (Mat2x2 a) (V2 a) Source # | Since: 1.1.0.0 |
| Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source # | Since: 1.1.0.0 |
| newtype MVector s (V2 a) Source # | Since: 1.1.0.0 |
| newtype Vector (V2 a) Source # | Since: 1.1.0.0 |
Range add
Monoid action \(f: x \rightarrow x + d\).
Example
>>>import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))>>>import AtCoder.LazySegTree qualified as LST>>>import Data.Semigroup (Max(..))>>>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 318
Since: 1.0.0.0
Constructors
| RangeAdd a |
Instances
Range set
Monoid action \(f: x \rightarrow a\).
Example
>>>import AtCoder.Extra.Monoid (SegAct(..), RangeSet(..))>>>import AtCoder.LazySegTree qualified as LST>>>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 4375
Since: 1.0.0.0
Constructors
| RangeSet (RangeSetRepr a) |
Instances
type RangeSetRepr a = (Bit, a) Source #
Rolling hash
data RollingHash b p Source #
Rolling hash algorithm implemented as a monoid, typically stored in a segment tree. The type parameters \(b\) and \(p\) represent the B-adic base and the modulus, respectively.
Combining RollingHash with SegTree enables \(O(\log |s|)\) string slice creation and
\(O(1)\) slice comparison.
Example
It's convenient to define a type alias of RollingHash:
>>>import AtCoder.Extra.Monoid.RollingHash qualified as RH>>>import AtCoder.SegTree qualified as ST>>>import Data.Char (ord)>>>import Data.Semigroup (Dual (..))>>>type RH = RH.RollingHash 100 998244353
Let's test whether "abcba" is a palindrome:
>>>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)>>>hash1 == hash2True
Since: 1.1.0.0