Processing math: 100%
ac-library-hs-1.2.0.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.Monoid.Affine1

Description

Monoid action f:x→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

Synopsis

Affine1

newtype Affine1 a Source #

Monoid action f:x→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: f2(f1v)=(f2∘f1)v. To apply the leftmost transformation first in a segment tree, wrap Affine1 in Data.Monoid.Dual.

Example

Expand
>>> 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

Instances details
Unbox a => Vector Vector (Affine1 a) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.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) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Affine1 a -> Sum a -> Sum a Source #

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

newtype MVector s (Affine1 a) Source #

Since: 1.0.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) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

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

type Affine1Repr a = (a, a) Source #

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 Source #

O(1) Creates a one-dimensional affine transformation: f:x→a×x+b.

Since: 1.0.0.0

unAffine1 :: Affine1 a -> Affine1Repr a Source #

O(1) Retrieves the two components of Affine1.

Since: 1.1.0.0

ident :: Num a => Affine1 a Source #

O(1) Identity transformation.

Since: 1.1.0.0

zero :: Num a => Affine1 a Source #

O(1) Transformation to zero.

Since: 1.1.0.0

Actions

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

O(1) Applies the one-dimensional affine transformation f:x→a×x+b.

Since: 1.0.0.0