AtCoder.Extra.Seq.Raw

Base module for implementing dynamic sequences. It internaly uses a splay tree and user has to track the root node change.

Since: 1.2.0.0

Seq

data Seq s f a

Storages of dynamic sequences of monoid values with monoid actions on them through the SegAct instance.

Since: 1.2.0.0

Constructors

Seq

Fields

• nSeq :: !Int

  The maximum number of elements.

  Since: 1.2.0.0

• poolSeq :: !(Pool s ())

  Pool for free slot management.

  Since: 1.2.0.0

• lSeq :: !(MVector s Index)

  Decomposed node data storage: left children.

  Since: 1.2.0.0

• rSeq :: !(MVector s Index)

  Decomposed node data storage: right children.

  Since: 1.2.0.0

• pSeq :: !(MVector s Index)

  Decomposed node data storage: parents.

  Since: 1.2.0.0

• sSeq :: !(MVector s Int)

  Decomposed node data storage: subtree sizes.

  Since: 1.2.0.0

• vSeq :: !(MVector s a)

  Decomposed node data storage: monoid values.

  Since: 1.2.0.0

• prodSeq :: !(MVector s a)

  Decomposed node data storage: monoid products.

  Since: 1.2.0.0

• revSeq :: !(MVector s Bit)

  Decomposed node data storage: reversed flag of children.

  Since: 1.2.0.0

• lazySeq :: !(MVector s f)

  Decomposed node data storage: lazily propagated monoid action. Use () if you don't need monoid actions.

  Since: 1.2.0.0

Constructors

newST :: (Monoid f, Unbox f, Monoid a, Unbox a) => Int -> ST s (Seq s f a)

$O(n)$ Creates a new Seq of length $n$.

Since: 1.2.0.0

resetST :: Seq s f a -> ST s ()

$O(1)$ Clears the sequence storage.

Since: 1.2.0.0

newNodeST :: (HasCallStack, Monoid f, Unbox f, Unbox a) => Seq s f a -> a -> ST s Index

$O(1)$ Allocates a new sequence of length $1$.

Since: 1.2.0.0

newSeqST :: (HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Vector a -> ST s Index

$O(n)$ Allocates a new sequence.

Since: 1.2.0.0

freeNodeST :: Seq s v a -> Index -> ST s ()

$O(1)$ Frees a node.

Since: 1.2.0.0

freeSubtreeST :: Unbox a => Seq s f a -> Index -> ST s ()

$O(n)$ Frees a subtree.

Since: 1.2.0.0

Metadata

capacity :: Seq s f a -> Int

$O(1)$ Returns the capacity of the sequence storage.

Since: 1.2.1.0

lengthST :: Seq s f a -> Index -> ST s Int

$O(1)$ Returns the length of a sequence or a subtree.

Since: 1.2.1.0

Merge/split

mergeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Index -> ST s Index

Amortized $O(\log n)$. Merges two sequences $l, r$ into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

merge3ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Index -> Index -> ST s Index

Amortized $O(\log n)$. Merges three sequences $l, m, r$ into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

merge4ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Index -> Index -> Index -> ST s Index

Amortized $O(\log n)$. Merges four sequences $l, b, c, d, m, r$ into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

splitST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s (Index, Index)

Amortized $O(\log n)$. Splits a sequences into two: $[0, k), [k, n)$.

Constraints

• The node must be null or a root.
• $0 \le k \le n$.

Since: 1.2.0.0

split3ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> ST s (Index, Index, Index)

Amortized $O(\log n)$. Splits a sequences into three: $[0, l), [l, r), [r, n)$.

Constraints

• The node must be null or a root.
• $0 \le l \le r \le n$.

Since: 1.2.0.0

split4ST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> Int -> ST s (Index, Index, Index, Index)

Amortized $O(\log n)$. Splits a sequences into four: $[0, i), [i, j), [j, k), [k, n)$.

Constraints

• The node must be null or a root.
• $0 \le i \le j \le k \le n$.

Since: 1.2.0.0

splitLrST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> ST s (Index, Index, Index)

Amortized $O(\log n)$. Splits a sequence into three: $[0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)$.

Constraints

• The node must be a root.

Since: 1.2.0.0

sliceST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> ST s Index

Amortized $O(\log n)$. Captures the root of a subtree of $[l, r)$. Splay the new root after call.

Constraints

• $0 \le \lt r \le n$. Note that the interval must have positive length.

Since: 1.2.0.0

Read/write

readST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s (a, Index)

Amortized $O(\log n)$. Reads the $k$-th node's monoid value.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

readMaybeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s (Maybe (a, Index))

Amortized $O(\log n)$. Reads the $k$-th node's monoid value.

Constraints

• The root must be empty or a root.

Since: 1.2.0.0

writeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> a -> ST s Index

Amortized $O(\log n)$. Writes to the $k$-th node's monoid value.

Constraints

• The node must be a root.
• $0 \le k \lt n$

Since: 1.2.0.0

modifyST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> (a -> a) -> Int -> ST s Index

Amortized $O(\log n)$. Modifies the $k$-th node's monoid value.

Constraints

• The node must be a root.
• $0 \le k \lt n$

Since: 1.2.0.0

exchangeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> a -> ST s (a, Index)

Amortized $O(\log n)$. Exchanges the $k$-th node's monoid value.

Constraints

• The node must be a root.
• $0 \le k \lt n$

Since: 1.2.0.0

Products

prodST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> ST s (a, Index)

Amortized $O(\log n)$. Returns the monoid product in an interval $[l, r)$.

Constraints

• The node must be a root
• $0 \le l \le r \le n$

Since: 1.2.0.0

prodMaybeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> ST s (Maybe (a, Index))

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

Since: 1.2.0.0

prodAllST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> ST s a

Amortized $O(\log n)$. Returns the monoid product of the whole sequence. Returns mempty for an empty sequence.

Constraint

• The node must be null or a root.

Since: 1.2.0.0

Applications

applyInST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> f -> ST s Index

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

Constraints

• $0 \le l \le r \le n$

Since: 1.2.0.0

applyToRootST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> f -> ST s ()

$O(1)$ Applies a monoid action $f$ to the root of a sequence.

Since: 1.2.0.0

reverseST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> Int -> ST s Index

Amortized $O(\log n)$. Reverses the sequence in $[l, r)$.

Constraints

• The monoid action $f$ must be commutative.
• The monoid value $v$ must be commutative.

Since: 1.2.0.0

Insert/delete

insertST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> a -> ST s Index

Amortized $O(\log n)$. Inserts a new node at $k$ with initial monoid value $v$. This functions for an empty index.

Constraints

• The node must be null or a root.
• $0 \le k \le n$

Since: 1.2.0.0

deleteST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s (a, Index)

Amortized $O(\log n)$. Frees the $k$-th node and returns the monoid value of it.

Constraints

• The node must be null or a root.
• $0 \le k \lt n$

Since: 1.2.0.0

deleteST_ :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s Index

Amortized $O(\log n)$. Frees the $k$-th node.

Constraints

• The node must be null or a root.
• $0 \le k \lt n$

Since: 1.2.0.0

detachST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s Index

Amortized $O(\log n)$. Detaches the $k$-th node and returns the new root of the original sequence.

Constraints

• The node must be null or a root.
• $0 \le k \lt n$

Since: 1.2.0.0

Balancing

rotateST :: HasCallStack => Seq s v a -> Index -> ST s ()

Amortized $O(\log n)$. Rotates a child node.

Constraints

• $0 \le i \lt n$

Since: 1.2.0.0

splayST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Bool -> ST s ()

Amortized $O(\log n)$. Moves up a node to be a root.

Since: 1.2.0.0

splayKthST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> Int -> ST s Index

Amortized $O(\log n)$. Finds $k$-th node and splays it. Returns the new root.

Constraints

• $0 \le k \lt n$

Since: 1.2.0.0

Bisection methods

C++-like

ilowerBoundST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Int, Index)

(r, root)

Amortized $O(\log n)$.

Since: 1.2.0.0

ilowerBoundM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

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

-> m (Int, Index)

(r, root)

Amortized $O(\log n)$.

Since: 1.2.0.0

ilowerBoundProdST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Int, Index)

(r, root)

Amortized $O(\log n)$.

Constraints

• The node must be a root.

Since: 1.2.0.0

ilowerBoundProdM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

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

-> m (Int, Index)

(r, root)

Amortized $O(\log n)$.

Constraints

• The node must be a root.

Since: 1.2.0.0

Splits

isplitMaxRightST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Index, Index)

(left, right) sequences where $f$ holds for the left

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Since: 1.2.0.0

isplitMaxRightM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

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

-> m (Index, Index)

(left, right) sequences where $f$ holds for the left

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Since: 1.2.0.0

isplitMaxRightProdST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Index, Index)

(left, right) sequences where $f$ holds for the left

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Since: 1.2.0.0

isplitMaxRightProdM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

User predicate $f(i, v_i)$ that takes the index and the monoid value | $r$

-> m (Index, Index)

(left, right) sequences where $f$ holds for the left

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Since: 1.2.0.0

Max right

imaxRightST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Int, Index, Index)

(r, left, right)

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v$ where $f(v)$ holds for every $v_i (0 \le i \lt k)$. Note that $f$ works for a single node, not a monoid product.

Constraints

• The node must be a root.

Since: 1.2.0.0

imaxRightM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

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

-> m (Int, Index, Index)

(r, left, right)

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $v_i (0 \le i \le k)$. Note that $f$ works for a single node, not a monoid product.

Constraints

• The node must be a root.

Since: 1.2.0.0

imaxRightProdST

Arguments

:: (SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Int -> a -> Bool)

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

-> ST s (Int, Index, Index)

(ilowerBound, rightmost node, new root)

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Constraints

• The node must be a root.

Since: 1.2.0.0

imaxRightProdM

Arguments

:: (PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq (PrimState m) f a

Sequence storage

-> Index

Root node

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

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

-> m (Int, Index, Index)

(ilowerBound, rightmost node, new root)

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Constraints

• The node must be a root.

Since: 1.2.0.0

Conversions

freezeST :: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> ST s (Vector a)

Amortized $O(n)$. Returns the sequence of monoid values.

Since: 1.2.0.0

Internals

These functions are exported primarily for Map implementations.

splitMaxRightWithST

Arguments

:: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Index -> ST s Bool)

User predicate $f(i)$

-> ST s (Index, Index)

(left, right) sequences where $f$ holds for the left

Amortized $O(\log n)$.

Since: 1.2.1.0

maxRightWithST

Arguments

:: (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a)

=> Seq s f a

Sequence storage

-> Index

Root node

-> (Index -> ST s Bool)

User predicate

-> ST s (Index, Index)

(rightmost node, new root)

Amortized $O(\log n)$. Given a monotonious sequence, returns the rightmost node $v_k$ where $f(v)$ holds for every $[0, i) (0 \le i \lt k)$.

Constraints

• The node must be a root.

Since: 1.2.1.0

updateNodeST :: (Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()

$O(1)$ Recomputes the node size and the monoid product.

Since: 1.2.1.0

writeNodeST :: (Monoid a, Unbox a) => Seq s f a -> Index -> a -> ST s ()

$O(1)$ Writes to the monoid value of a node.

Since: 1.2.1.0

modifyNodeST :: (HasCallStack, Monoid a, Unbox a) => Seq s f a -> (a -> a) -> Index -> ST s ()

$O(1)$ Modifies the monoid value of a node.

Since: 1.2.1.0

exchangeNodeST :: (HasCallStack, Monoid a, Unbox a) => Seq s f a -> Index -> a -> ST s a

$O(1)$ Exchanges the monoid value of a node.

Since: 1.2.1.0

propNodeST :: (HasCallStack, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> ST s ()

Amortized $O(\log n)$. Propgates the lazily propagated values on a node.

Since: 1.2.1.0

applyNodeST :: (HasCallStack, SegAct f a, Unbox f, Monoid a, Unbox a) => Seq s f a -> Index -> f -> ST s ()

Amortized $O(\log n)$. Propgates at a node.

Since: 1.2.1.0