| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.Mo
Description
Mo's algorithm for handling \([l, r)\) offline queries in \(O((n + q) \sqrt n f)\) time complecity, where \(n\) is the length of index, \(q\) is the number of queries and \(f\) is the time for processing element addition or deletion. Due to the high time complexity, it is recommended to choose an efficient data structure such as Fenwick Tree for query processing.
Since: 1.2.5.0
Synopsis
- run :: (HasCallStack, PrimMonad m, Unbox a) => Int -> Vector (Int, Int) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m a) -> m (Vector a)
- sortIndices :: HasCallStack => Int -> Vector (Int, Int) -> Vector Int
- process :: (HasCallStack, PrimMonad m, Unbox a) => Vector Int -> Vector (Int, Int) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m ()) -> (Int -> m a) -> m (Vector a)
Documentation
Arguments
| :: (HasCallStack, PrimMonad m, Unbox a) | |
| => Int | Defines index bounds \([0, n)\). |
| -> Vector (Int, Int) | Query intervals \([l, r)\). |
| -> (Int -> m ()) | Called on adding left index \(l\). |
| -> (Int -> m ()) | Called on adding left index \(r\). |
| -> (Int -> m ()) | Called on deleting left index \(l\). |
| -> (Int -> m ()) | Called on deleting right index \(r\). |
| -> (Int -> m a) | Returns result for query index \(i\). |
| -> m (Vector a) | Result for each query. |
\(O((n + q) \sqrt n)\) Runs Mo's algorithm. Internally it's a call of sortIndices and
process.
Since: 1.2.5.0
Arguments
| :: HasCallStack | |
| => Int | Defines index bounds \([0, n)\). |
| -> Vector (Int, Int) | Query intervals \([l, r)\). |
| -> Vector Int | Sorted indices to the query intervals. |
\(O(n (\log n))\) Sorts indices of \([l, r)\) queries in an efficient order for processing.
Since: 1.2.5.0
Arguments
| :: (HasCallStack, PrimMonad m, Unbox a) | |
| => Vector Int | Sorted indices to query intervals \([l, r)\). |
| -> Vector (Int, Int) | Query intervals \([l, r)\). |
| -> (Int -> m ()) | Called on adding left index \(l\). |
| -> (Int -> m ()) | Called on adding right index \(r\). |
| -> (Int -> m ()) | Called on deleting left index \(l\). |
| -> (Int -> m ()) | Called on deleting right index \(r\). |
| -> (Int -> m a) | Returns result for query index \(i\). |
| -> m (Vector a) | Result for each query. |
\(O((n + q) \sqrt n)\) Processes \([l, r)\) interval queries. User would usually use run
instead.
Since: 1.2.5.0