AtCoder.Extra.Monoid.RangeSet

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

Since: 1.0.0.0

RangeSet

newtype RangeSet a

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

Example

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

Unbox a => Vector Vector (RangeSet a)

Since: 1.0.0.0

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)

Since: 1.0.0.0

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)

Since: 1.0.0.0

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)

Since: 1.0.0.0

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)

Since: 1.0.0.0

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)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

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

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

Ord a => Ord (RangeSet a)

Since: 1.0.0.0

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)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.RangeSet

Monoid a => SegAct (RangeSet a) a

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

segAct :: RangeSet a -> a -> a

segActWithLength :: Int -> RangeSet a -> a -> a

newtype MVector s (RangeSet a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.RangeSet

newtype MVector s (RangeSet a) = MV_RangeSet (MVector s (RangeSetRepr a))

newtype Vector (RangeSet a)

Since: 1.0.0.0

Defined in AtCoder.Extra.Monoid.RangeSet

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

type RangeSetRepr a = (Bit, a)

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

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

Since: 1.0.0.0

unRangeSet :: RangeSet a -> RangeSetRepr a

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

Since: 1.1.0.0

Actions

act :: RangeSet a -> a -> a

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

Since: 1.0.0.0