[−][src]Module contest_algorithms::order
Ordering algorithms.
Structs
| PiecewiseLinearConvexFn | Represents a maximum (upper envelope) of a collection of linear functions of one variable, evaluated using an online version of the convex hull trick. It combines the offline algorithm with square root decomposition, resulting in an asymptotically suboptimal but simple algorithm with good amortized performance: N inserts interleaved with Q queries yields O(N sqrt Q + Q log N) time complexity in general, or O(N + Q log N) if all queries come after all inserts. |
| SparseIndex | A simple data structure for coordinate compression |
Functions
| asserting_cmp | A comparator on partially ordered elements, that panics if they are incomparable |
| merge_sort | A stable sort |
| merge_sorted | Stably merges two sorted and totally ordered collections into one |
| slice_lower_bound | Assuming slice is sorted and totally ordered, returns the minimum i for which slice[i] >= key, or slice.len() if no such i exists |
| slice_upper_bound | Assuming slice is sorted and totally ordered, returns the minimum i for which slice[i] > key, or slice.len() if no such i exists |