AtCoder.Extra.Monoid.Affine1

Monoid action \(f: x \rightarrow ax + b\).

• Use Mat2x2 if inverse operations are required, or if it's necessary to store the monoid length in the acted monoid (V2).

Since: 1.0.0.0

Affine1

newtype Affine1 a

Monoid action \(f: x \rightarrow ax + b\).

• Use Mat2x2 if 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 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

Constructors

new :: a -> a -> Affine1 a

\(O(1)\) Creates a one-dimensional affine transformation: \(f: x \rightarrow a \times x + b\).

Since: 1.0.0.0

unAffine1 :: Affine1 a -> Affine1Repr a

\(O(1)\) Retrieves the two components of Affine1.

Since: 1.1.0.0

ident :: Num a => Affine1 a

\(O(1)\) Identity transformation.

Since: 1.1.0.0

zero :: Num a => Affine1 a

\(O(1)\) Transformation to zero.

Since: 1.1.0.0

Actions

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

\(O(1)\) Applies the one-dimensional affine transformation \(f: x \rightarrow a \times x + b\).

Since: 1.0.0.0