| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Algorithm.Mo
Description
\(O(N \sqrt Q)\) Mo's algorithm
Be sure to..
{-# INLINE #-}user-defined functions- Never use unboxed vector for output
Typical problems
Synopsis
- sortMo :: Int -> Vector (Int, Int) -> Vector Int
- runMoG :: (PrimMonad m, Unbox x, Vector v b) => Vector x -> Vector (Int, Int) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> b) -> a -> m (v b)
- runMoPureG :: (Unbox x, Vector v b) => Vector x -> Vector (Int, Int) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> b) -> a -> v b
- runMo :: (PrimMonad m, Unbox x, Unbox b) => Vector x -> Vector (Int, Int) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> b) -> a -> m (Vector b)
- runMoPure :: (Unbox x, Unbox b) => Vector x -> Vector (Int, Int) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> b) -> a -> Vector b
- simpleRunMo :: (PrimMonad m, Unbox x, Unbox a) => Vector x -> Vector (Int, Int) -> (a -> x -> m a) -> (a -> x -> m a) -> a -> m (Vector a)
- simpleRunMoPure :: (Unbox x, Unbox a) => Vector x -> Vector (Int, Int) -> (a -> x -> a) -> (a -> x -> a) -> a -> Vector a
Documentation
sortMo :: Int -> Vector (Int, Int) -> Vector Int #
\(O(N \log N)\) Returns a sorted indices to the vector of (l, r), first by l and
then div br.
runMoG :: (PrimMonad m, Unbox x, Vector v b) => Vector x -> Vector (Int, Int) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> b) -> a -> m (v b) #
\(O(N (\log N + \sqrt Q))\). Mo's algorithm: runMo xs lrs onInsL onInsR onRemL onRemR extract state0.
runMoPureG :: (Unbox x, Vector v b) => Vector x -> Vector (Int, Int) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> b) -> a -> v b #
\(O(N (\log N + \sqrt Q))\). Pure variant of runMoG.
runMo :: (PrimMonad m, Unbox x, Unbox b) => Vector x -> Vector (Int, Int) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> x -> m a) -> (a -> b) -> a -> m (Vector b) #
\(O(N (\log N + \sqrt Q))\). Type-restricted runMo
runMoPure :: (Unbox x, Unbox b) => Vector x -> Vector (Int, Int) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> x -> a) -> (a -> b) -> a -> Vector b #
\(O(N (\log N + \sqrt Q))\). Type-restricted runMoPure