Safe Haskell	None
Language	GHC2021

AtCoder.Extra.Monoid.Affine1

Contents

Affine1
Constructor
Action

Description

SegAct instance of one-dimensional affine transformation \(f: x \rightarrow a \times x + b\).

Since: 1.0.0

Synopsis

newtype Affine1 a = Affine1 (Affine1Repr a)
type Affine1Repr a = (a, a)
new :: a -> a -> Affine1 a
act :: Num a => Affine1 a -> a -> a

Affine1

newtype Affine1 a #

SegAct instance of one-dimensional affine transformation \(f: x \rightarrow a \times x + 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

Constructors

Affine1 (Affine1Repr a)

Instances

Instances details

Unbox a => Vector Vector (Affine1 a) #	Since: 1.0.0
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details Defined in AtCoder.Extra.Monoid.Affine1
Num a => SegAct (Affine1 (Sum a)) (Sum a) #	Since: 1.0.0
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details 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
Instance details 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

Constructor

new :: a -> a -> Affine1 a #

Creates Affine1.

Since: 1.0.0

Action

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

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

Since: 1.0.0