AtCoder.Extra.Monoid.Affine1

Range add monoid action for \([l, r)\) intervals: \(f: x \rightarrow ax + b\).

Since: 1.0.0.0

Affine1

newtype Affine1 a

Range add monoid action for \([l, r)\) intervals: \(f: x \rightarrow ax + b\).

Composition and dual

Semigroup for Affine1 is implemented like function composition, and rightmost affine transformation is applied first: \((f_1 \circ f_2) v := f_1 (f_2(v))\). If you need foldr of \([f_l, f_{l+1}, .., f_r)\) on a segment tree, be sure to wrap Affine1 in 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 seg
9

Since: 1.0.0.0

Constructors

Affine1 (Affine1Repr a)

Instances

Unbox a => Vector Vector (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

basicUnsafeFreeze :: Mutable Vector s (Affine1 a) -> ST s (Vector (Affine1 a))

basicUnsafeThaw :: Vector (Affine1 a) -> ST s (Mutable Vector s (Affine1 a))

basicLength :: Vector (Affine1 a) -> Int

basicUnsafeSlice :: Int -> Int -> Vector (Affine1 a) -> Vector (Affine1 a)

basicUnsafeIndexM :: Vector (Affine1 a) -> Int -> Box (Affine1 a)

basicUnsafeCopy :: Mutable Vector s (Affine1 a) -> Vector (Affine1 a) -> ST s ()

elemseq :: Vector (Affine1 a) -> Affine1 a -> b -> b

Unbox a => MVector MVector (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

basicLength :: MVector s (Affine1 a) -> Int

basicUnsafeSlice :: Int -> Int -> MVector s (Affine1 a) -> MVector s (Affine1 a)

basicOverlaps :: MVector s (Affine1 a) -> MVector s (Affine1 a) -> Bool

basicUnsafeNew :: Int -> ST s (MVector s (Affine1 a))

basicInitialize :: MVector s (Affine1 a) -> ST s ()

basicUnsafeReplicate :: Int -> Affine1 a -> ST s (MVector s (Affine1 a))

basicUnsafeRead :: MVector s (Affine1 a) -> Int -> ST s (Affine1 a)

basicUnsafeWrite :: MVector s (Affine1 a) -> Int -> Affine1 a -> ST s ()

basicClear :: MVector s (Affine1 a) -> ST s ()

basicSet :: MVector s (Affine1 a) -> Affine1 a -> ST s ()

basicUnsafeCopy :: MVector s (Affine1 a) -> MVector s (Affine1 a) -> ST s ()

basicUnsafeMove :: MVector s (Affine1 a) -> MVector s (Affine1 a) -> ST s ()

basicUnsafeGrow :: MVector s (Affine1 a) -> Int -> ST s (MVector s (Affine1 a))

Num a => Monoid (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

mempty :: Affine1 a

mappend :: Affine1 a -> Affine1 a -> Affine1 a

mconcat :: [Affine1 a] -> Affine1 a

Num a => Semigroup (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

(<>) :: Affine1 a -> Affine1 a -> Affine1 a

sconcat :: NonEmpty (Affine1 a) -> Affine1 a

stimes :: Integral b => b -> Affine1 a -> Affine1 a

Show a => Show (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

showsPrec :: Int -> Affine1 a -> ShowS

show :: Affine1 a -> String

showList :: [Affine1 a] -> ShowS

Eq a => Eq (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

(==) :: Affine1 a -> Affine1 a -> Bool

(/=) :: Affine1 a -> Affine1 a -> Bool

Ord a => Ord (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

compare :: Affine1 a -> Affine1 a -> Ordering

(<) :: Affine1 a -> Affine1 a -> Bool

(<=) :: Affine1 a -> Affine1 a -> Bool

(>) :: Affine1 a -> Affine1 a -> Bool

(>=) :: Affine1 a -> Affine1 a -> Bool

max :: Affine1 a -> Affine1 a -> Affine1 a

min :: Affine1 a -> Affine1 a -> Affine1 a

Unbox a => Unbox (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Num a => SegAct (Affine1 (Sum a)) (Sum a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Affine1 (Sum a) -> Sum a -> Sum a

segActWithLength :: Int -> Affine1 (Sum a) -> Sum a -> Sum a

Num a => SegAct (Affine1 a) (Sum a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Affine1 a -> Sum a -> Sum a

segActWithLength :: Int -> Affine1 a -> Sum a -> Sum a

Num a => SegAct (Dual (Affine1 (Sum a))) (Sum a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Dual (Affine1 (Sum a)) -> Sum a -> Sum a

segActWithLength :: Int -> Dual (Affine1 (Sum a)) -> Sum a -> Sum a

Num a => SegAct (Dual (Affine1 a)) (Sum a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Dual (Affine1 a) -> Sum a -> Sum a

segActWithLength :: Int -> Dual (Affine1 a) -> Sum a -> Sum a

newtype MVector s (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

newtype MVector s (Affine1 a) = MV_Affine1 (MVector s (Affine1Repr a))

newtype Vector (Affine1 a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.Affine1

newtype Vector (Affine1 a) = V_Affine1 (Vector (Affine1Repr a))

type Affine1Repr a = (a, a)

Affine1 internal representation. Tuples are not the fastest representation, but it's easier to implement Unbox.

Since: 1.0.0.0

Constructor

new :: a -> a -> Affine1 a

Creates Affine1.

Since: 1.0.0.0

Action

act :: Num a => Affine1 a -> a -> a

Applies \(f: x \rightarrow a \times x + b\).

Since: 1.0.0.0