ac-library-hs-1.4.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.Extra.Monoid.RangeSet

Description

Monoid action \(f: x \rightarrow a\).

Since: 1.0.0.0

Synopsis

RangeSet

newtype RangeSet a Source #

Monoid action \(f: x \rightarrow a\).

Example

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

Since: 1.0.0.0

Constructors

RangeSet (RangeSetRepr a) 

Instances

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

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

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

basicLength :: Vector (RangeSet a) -> Int

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

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

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

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

Unbox a => MVector MVector (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

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

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

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

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

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

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

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

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

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

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

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

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

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

Monoid a => Monoid (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

mempty :: RangeSet a #

mappend :: RangeSet a -> RangeSet a -> RangeSet a #

mconcat :: [RangeSet a] -> RangeSet a #

Semigroup (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

(<>) :: RangeSet a -> RangeSet a -> RangeSet a #

sconcat :: NonEmpty (RangeSet a) -> RangeSet a #

stimes :: Integral b => b -> RangeSet a -> RangeSet a #

Show a => Show (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

showsPrec :: Int -> RangeSet a -> ShowS #

show :: RangeSet a -> String #

showList :: [RangeSet a] -> ShowS #

Eq a => Eq (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

(==) :: RangeSet a -> RangeSet a -> Bool #

(/=) :: RangeSet a -> RangeSet a -> Bool #

Ord a => Ord (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

compare :: RangeSet a -> RangeSet a -> Ordering #

(<) :: RangeSet a -> RangeSet a -> Bool #

(<=) :: RangeSet a -> RangeSet a -> Bool #

(>) :: RangeSet a -> RangeSet a -> Bool #

(>=) :: RangeSet a -> RangeSet a -> Bool #

max :: RangeSet a -> RangeSet a -> RangeSet a #

min :: RangeSet a -> RangeSet a -> RangeSet a #

Unbox a => Unbox (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Monoid a => SegAct (RangeSet a) a Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

segAct :: RangeSet a -> a -> a Source #

segActWithLength :: Int -> RangeSet a -> a -> a Source #

newtype MVector s (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

newtype MVector s (RangeSet a) = MV_RangeSet (MVector s (RangeSetRepr a))
newtype Vector (RangeSet a) Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

newtype Vector (RangeSet a) = V_RangeSet (Vector (RangeSetRepr a))

type RangeSetRepr a = (Bit, a) Source #

RangeSet internal representation. The first value represents if it is an identity action. Tuples are not the fastest representation, but it's easier to implement Unbox.

Since: 1.1.0.0

Constructors

new :: a -> RangeSet a Source #

\(O(1)\) Creates a new RangeSet action.

Since: 1.0.0.0

unRangeSet :: RangeSet a -> RangeSetRepr a Source #

\(O(1)\) Retrieves the internal representation of RangeSet.

Since: 1.1.0.0

Actions

act :: RangeSet a -> a -> a Source #

\(O(1)\) Applies one-length range set: \(f: x \rightarrow y\).

Since: 1.0.0.0