ac-library-hs-1.2.1.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.Seq.Map

Description

Key-value pairs with monoid products and monoid actions on them through the SegAct instance.

Performance

This module is extremely slow as an ordinary map. Do not use it unless you need monoid products.

Example

Expand
>>> import AtCoder.Extra.Monoid.RangeAdd qualified as RangeAdd
>>> import AtCoder.Extra.Seq.Map qualified as M
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> m <- M.new @_ @(RangeAdd.RangeAdd (Sum Int)) @Int @(Sum Int) 10
>>> M.insert m 1 10
>>> M.insert m 3 30
>>> M.prod m 1 2
Sum {getSum = 10}

Since: 1.2.1.0

Synopsis

Map

data Map s f k v Source #

Key-value pairs with monoid products and monoid actions on them through the SegAct instance.

Since: 1.2.1.0

Constructors

Map 

Fields

Re-exports

class Monoid f => SegAct f a where Source #

Typeclass reprentation of the LazySegTree properties. User can implement either segAct or segActWithLength.

Instances should satisfy the follwing properties:

Left monoid action
segAct (f2 <> f1) x = segAct f2 (segAct f1 x)
Identity map
segAct mempty x = x
Endomorphism
segAct f (x1 <> x2) = (segAct f x1) <> (segAct f x2)

If you implement SegAct via segActWithLength, satisfy one more propety:

Linear left monoid action
segActWithLength len f a = stimes len (segAct f a) a.

Invariant

In SegAct instances, new semigroup values are always given from the left: new <> old. The order is important for non-commutative monoid implementations.

Example instance

Expand

Take Affine1 as an example of type \(F\).

{-# LANGUAGE TypeFamilies #-}

import AtCoder.LazySegTree qualified as LST
import AtCoder.LazySegTree (SegAct (..))
import Data.Monoid
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

-- | f x = a * x + b. It's implemented as a newtype of `(a, a)` for easy Unbox deriving.
newtype Affine1 a = Affine1 (Affine1 a)
  deriving newtype (Eq, Ord, Show)

-- | This type alias makes the Unbox deriving easier, described velow.
type Affine1Repr a = (a, a)

instance (Num a) => Semigroup (Affine1 a) where
  {-# INLINE (<>) #-}
  (Affine1 (!a1, !b1)) <> (Affine1 (!a2, !b2)) = Affine1 (a1 * a2, a1 * b2 + b1)

instance (Num a) => Monoid (Affine1 a) where
  {-# INLINE mempty #-}
  mempty = Affine1 (1, 0)

instance (Num a) => SegAct (Affine1 a) (Sum a) where
  {-# INLINE segActWithLength #-}
  segActWithLength len (Affine1 (!a, !b)) !x = a * x + b * fromIntegral len

Deriving Unbox is very easy for such a newtype (though the efficiency is not the maximum):

newtype instance VU.MVector s (Affine1 a) = MV_Affine1 (VU.MVector s (Affine1 a))
newtype instance VU.Vector (Affine1 a) = V_Affine1 (VU.Vector (Affine1 a))
deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1 a)
deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1 a)
instance (VU.Unbox a) => VU.Unbox (Affine1 a)

Example contest template

Expand

Define your monoid action F and your acted monoid X:

{-# LANGUAGE TypeFamilies #-}

import AtCoder.LazySegTree qualified as LST
import AtCoder.LazySegTree (SegAct (..))
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

{- ORMOLU_DISABLE -}
-- | F is a custom monoid action, defined as a newtype of FRepr.
newtype F = F FRepr deriving newtype (Eq, Ord, Show) ; unF :: F -> FRepr ; unF (F x) = x ; newtype instance VU.MVector s F = MV_F (VU.MVector s FRepr) ; newtype instance VU.Vector F = V_F (VU.Vector FRepr) ; deriving instance VGM.MVector VUM.MVector F ; deriving instance VG.Vector VU.Vector F ; instance VU.Unbox F ;
{- ORMOLU_ENABLE -}

-- | Affine: f x = a * x + b
type FRepr = (Int, Int)

instance Semigroup F where
  -- new <> old
  {-# INLINE (<>) #-}
  (F (!a1, !b1)) <> (F (!a2, !b2)) = F (a1 * a2, a1 * b2 + b1)

instance Monoid F where
  {-# INLINE mempty #-}
  mempty = F (1, 0)

{- ORMOLU_DISABLE -}
-- | X is a custom acted monoid, defined as a newtype of XRepr.
newtype X = X XRepr deriving newtype (Eq, Ord, Show) ; unX :: X -> XRepr ; unX (X x) = x; newtype instance VU.MVector s X = MV_X (VU.MVector s XRepr) ; newtype instance VU.Vector X = V_X (VU.Vector XRepr) ; deriving instance VGM.MVector VUM.MVector X ; deriving instance VG.Vector VU.Vector X ; instance VU.Unbox X ;
{- ORMOLU_ENABLE -}

-- | Acted Int (same as `Sum Int`).
type XRepr = Int

deriving instance Num X; -- in our case X is a Num.

instance Semigroup X where
  {-# INLINE (<>) #-}
  (X x1) <> (X x2) = X $! x1 + x2

instance Monoid X where
  {-# INLINE mempty #-}
  mempty = X 0

instance SegAct F X where
  -- {-# INLINE segAct #-}
  -- segAct len (F (!a, !b)) (X x) = X $! a * x + b
  {-# INLINE segActWithLength #-}
  segActWithLength len (F (!a, !b)) (X x) = X $! a * x + len * b

It's tested as below:

expect :: (Eq a, Show a) => String -> a -> a -> ()
expect msg a b
  | a == b = ()
  | otherwise = error $ msg ++ ": expected " ++ show a ++ ", found " ++ show b

main :: IO ()
main = do
  seg <- LST.build _ F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]
  LST.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]
  LST.write seg 3 $ X 10 -- [1, 5, 7, 10]
  LST.modify seg (+ (X 1)) 0   -- [2, 5, 7, 10]
  !_ <- (expect "test 1" (X 5)) <$> LST.read seg 1
  !_ <- (expect "test 2" (X 14)) <$> LST.prod seg 0 3 -- reads an interval [0, 3)
  !_ <- (expect "test 3" (X 24)) <$> LST.allProd seg
  !_ <- (expect "test 4" 2) <$> LST.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10
  !_ <- (expect "test 5" 3) <$> LST.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10
  putStrLn "=> test passed!"

Since: 1.0.0.0

Minimal complete definition

Nothing

Methods

segAct :: f -> a -> a Source #

Lazy segment tree action \(f(x)\).

Since: 1.0.0.0

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

Lazy segment tree action \(f(x)\) with the target monoid's length.

If you implement SegAct with this function, you don't have to store the monoid's length, since it's given externally.

Since: 1.0.0.0

Instances

Instances details
SegAct () a Source #

Since: 1.2.0.0

Instance details

Defined in AtCoder.LazySegTree

Methods

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

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

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 #

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 (Mat2x2 a) (V2 a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

segAct :: Mat2x2 a -> V2 a -> V2 a Source #

segActWithLength :: Int -> Mat2x2 a -> V2 a -> V2 a Source #

(Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd (Max a) -> Max a -> Max a Source #

segActWithLength :: Int -> RangeAdd (Max a) -> Max a -> Max a Source #

(Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd (Min a) -> Min a -> Min a Source #

segActWithLength :: Int -> RangeAdd (Min a) -> Min a -> Min a Source #

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

Since: 1.2.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

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

segActWithLength :: Int -> RangeAdd (Sum 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 #

Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

segAct :: Dual (Mat2x2 a) -> V2 a -> V2 a Source #

segActWithLength :: Int -> Dual (Mat2x2 a) -> V2 a -> V2 a Source #

Constructors

new :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Int -> m (Map (PrimState m) f k v) Source #

\(O(n)\) Creates a new Map of capacity \(n\). Always prefer build to new for performance.

Since: 1.2.1.0

build :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Ord k, Unbox k, Unbox v, Monoid v) => Int -> Vector (k, v) -> m (Map (PrimState m) f k v) Source #

\(O(n \log n)\) Creates a new Map of capacity \(n\) with initial values. Always prefer build to new for performance.

Since: 1.2.1.0

reset :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Map (PrimState m) f k v -> m () Source #

\(O(1)\) Clears the map. All the handles must not be used again.

Since: 1.2.1.0

Metadata

capacity :: Map s f k v -> Int Source #

\(O(1)\) Returns the maximum number of elements the map can store.

Since: 1.2.1.0

size :: PrimMonad m => Map (PrimState m) f k v -> m Int Source #

\(O(1)\) Returns the number of elements in the map.

Since: 1.2.1.0

Key-based operations

Read/write

member :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m Bool Source #

Amoritzed \(O(\log n)\). Returns whether a node with key \(k\) is in the map.

Since: 1.2.1.0

lookup :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v) Source #

Amortized \(O(\log n)\). Looks up for the monoid value of a node with key \(k\).

Since: 1.2.1.0

adjust :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> k -> m () Source #

Amoritzed \(O(\log n)\). Adjusts the monoid value of a node with key \(k\).

Since: 1.2.1.0

Insert/delete

insert :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> v -> m () Source #

Amortized \(O(\log n)\). Inserts a \((k, v)\) pair. If the key is already present in the map, the associated value is replaced with the supplied value.

Since: 1.2.1.0

insertWith Source #

Arguments

:: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) 
=> Map (PrimState m) f k v

Map

-> (v -> v -> v)

new -> old -> combined

-> k

Key

-> v

Value

-> m () 

Amortized \(O(\log n)\). Inserts a \((k, v)\) pairs, combining new value and old value.

Since: 1.2.1.0

delete :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v) Source #

Amortized \(O(\log n)\). Deletes an element with key \(k\).

Since: 1.2.1.0

delete_ :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m () Source #

Amortized \(O(\log n)\). Deletes an element with key \(k\).

Since: 1.2.1.0

Products

prod :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m v Source #

Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Throws an error for \(k_1 \gt k_2\).

Constraints

  • \(k_1 \le k_2\)

Since: 1.2.1.0

prodMaybe :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m (Maybe v) Source #

Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns Nothing if an invalid interval is given or for an empty sequence.

Since: 1.2.1.0

allProd :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> m v Source #

Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns Nothing if an invalid interval is given or for an empty sequence.

Since: 1.2.1.0

Applications

applyIn :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> f -> m () Source #

Amortized \(O(\log n)\). Given an interval \([l, r)\), applies a monoid action \(f\).

Constraints

  • \(0 \le l \le r \le n\)
  • The root must point to a non-empty sequence.

Since: 1.2.1.0

applyAll :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> f -> m () Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

Bisection methods

lookupLE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #

Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that \(k \le k_{\mathrm{ref}}\).

Since: 1.2.1.0

lookupLT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #

Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that \(k \lt k_{\mathrm{ref}}\).

Since: 1.2.1.0

lookupGE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #

Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that \(k \ge k_{\mathrm{ref}}\).

Since: 1.2.1.0

lookupGT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #

Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that \(k \gt k_{\mathrm{ref}}\).

Since: 1.2.1.0

Index-based operations

Read/write

readAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m v Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

readMaybeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m (Maybe v) Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

writeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m () Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

modifyAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> Int -> m () Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

exchangeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m v Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

Products

prodInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> m v Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

Applications

applyInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> f -> m () Source #

Amortized \(O(\log n)\).

Since: 1.2.1.0

Bisection methods

ilowerBound Source #

Arguments

:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) 
=> Map (PrimState m) f k a

Map

-> (Int -> a -> Bool)

User predicate \(f(i, v_i)\) that takes the index and the monoid value

-> m Int

Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)

Amortized \(O(\log n)\).

Since: 1.2.1.0

ilowerBoundM Source #

Arguments

:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) 
=> Map (PrimState m) f k a

Map

-> (Int -> a -> m Bool)

User predicate \(f(i, v_i)\) that takes the index and the monoid value

-> m Int

Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\)

Amortized \(O(\log n)\).

Since: 1.2.1.0

ilowerBoundProd Source #

Arguments

:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) 
=> Map (PrimState m) f k a

Map

-> (Int -> a -> Bool)

User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product

-> m Int

Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)

Amortized \(O(\log n)\).

Since: 1.2.1.0

ilowerBoundProdM Source #

Arguments

:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) 
=> Map (PrimState m) f k a

Map

-> (Int -> a -> m Bool)

User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product

-> m Int

Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\)

Amortized \(O(\log n)\).

Since: 1.2.1.0

Conversion

freeze :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> m (Vector (k, v)) Source #

\(O(n)\) Returns the \(k, v\) pairs in the map

Since: 1.2.1.0