RangeAdd.hs

{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE TypeFamilies #-}

-- | Monoid action \(f: x \rightarrow x + d\).
--
-- @since 1.0.0.0
module AtCoder.Extra.Monoid.RangeAdd
  ( -- * RangeAdd
    RangeAdd (..),

    -- * Constructors
    new,
    unRangeAdd,

    -- * Actions
    act,
  )
where

import AtCoder.LazySegTree (SegAct (..))
import Data.Semigroup (Max (..), Min (..), Sum (..), stimes)
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM

-- | Monoid action \(f: x \rightarrow x + d\).
--
-- ==== __Example (action on @Sum@)__
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Sum(..))
-- >>> seg <- LST.build @_ @(RangeAdd (Sum Int)) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAdd (Sum 5) -- [5, 6, 7]
-- >>> getSum <$> LST.prod seg 0 3
-- 18
--
-- ==== __Example (action on @Max@)__
-- >>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import Data.Semigroup (Max(..))
-- >>> seg <- LST.build @_ @(RangeAdd (Max Int)) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]
-- >>> LST.applyIn seg 0 3 $ RangeAdd (Max 5) -- [5, 6, 7]
-- >>> getMax <$> LST.prod seg 0 3
-- 7
--
-- @since 1.0.0.0
newtype RangeAdd a = RangeAdd a
  deriving newtype
    ( -- | @since 1.0.0.0
      Eq,
      -- | @since 1.0.0.0
      Ord,
      -- | @since 1.0.0.0
      Show
    )

-- | Creates `RangeAdd`.
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: a -> RangeAdd a
new = RangeAdd

-- | \(O(1)\) Retrieves the internal value of `RangeAdd`.
--
-- @since 1.1.0.0
{-# INLINE unRangeAdd #-}
unRangeAdd :: RangeAdd a -> a
unRangeAdd (RangeAdd a) = a

-- | \(O(1)\) Applies one-length range add: \(f: x \rightarrow d + x\).
--
-- @since 1.0.0.0
{-# INLINE act #-}
act :: (Semigroup a) => RangeAdd a -> a -> a
act (RangeAdd dx) x = dx <> x

-- | \(O(1)\) Acts on @a@ with length in terms of `SegAct`. Be warned that it doesn't work well with
-- idempotent monoids such as `Max` or `Min`.
--
-- @since 1.0.0.0
{-# INLINE actWithLength #-}
actWithLength :: (Semigroup a) => Int -> RangeAdd a -> a -> a
actWithLength len (RangeAdd f) x = stimes len f <> x

-- | @since 1.2.0.0
instance (Semigroup a, Num a) => Semigroup (RangeAdd a) where
  {-# INLINE (<>) #-}
  (RangeAdd a) <> (RangeAdd b) = RangeAdd $! a + b

-- | @since 1.2.0.0
instance (Num a, Semigroup a) => Monoid (RangeAdd a) where
  {-# INLINE mempty #-}
  mempty = RangeAdd 0

-- | @since 1.2.0.0
instance (Num a) => SegAct (RangeAdd (Sum a)) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength = actWithLength

-- | @since 1.1.0.0
instance (Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) where
  {-# INLINE segAct #-}
  segAct (RangeAdd (Max dx)) (Max x) = Max $! dx + x

-- | @since 1.1.0.0
instance (Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) where
  {-# INLINE segAct #-}
  segAct (RangeAdd (Min dx)) (Min x) = Min $! dx + x

-- | @since 1.0.0.0
newtype instance VU.MVector s (RangeAdd a) = MV_RangeAdd (VU.MVector s a)

-- | @since 1.0.0.0
newtype instance VU.Vector (RangeAdd a) = V_RangeAdd (VU.Vector a)

-- | @since 1.0.0.0
deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (RangeAdd a)

-- | @since 1.0.0.0
deriving instance (VU.Unbox a) => VG.Vector VU.Vector (RangeAdd a)

-- | @since 1.0.0.0
instance (VU.Unbox a) => VU.Unbox (RangeAdd a)