| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Vector.InvNum
Description
Inversion numbers.
Synopsis
- invNum :: HasCallStack => Int -> Vector v Int => v Int -> Int
- compressInvNumG :: HasCallStack => Vector Int -> Int
- lexOrderMod :: (HasCallStack, Vector v Int) => v Int -> Int -> Int
Documentation
invNum :: HasCallStack => Int -> Vector v Int => v Int -> Int #
\(O(N \log N)\) Calculates the inversion number. Be sure to compress the input vector!
Typical problems
- ABC 261 - F
compressInvNumG :: HasCallStack => Vector Int -> Int #
\(O(N \log N)\) Calculates the inversion number, but after applying index compression. It can significantly improve the performance, like in ABC 261 F.
lexOrderMod :: (HasCallStack, Vector v Int) => v Int -> Int -> Int #
\(O(N \log N)\) Returns 1-based lexicographic order of the given array.
WARNING: Use 0-based indices for the input.
Typical problems
TODO