{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TypeFamilies #-}

-- | Base module of a dynamic, sparse segment tree.
--
-- @since 1.2.1.0
module AtCoder.Extra.DynSparseSegTree.Raw
  ( -- * Dynamic, sparse segment tree
    DynSparseSegTree (..),

    -- * Re-exports
    P.Index (..),

    -- * Constructors
    newST,
    newRootST,
    newNodeST,
    freeSubtreeST,

    -- * Accessing elements
    modifyMST,

    -- * Products
    prodST,
    -- prodMaybe,

    -- * Binary searches
    maxRightM,
    -- -- * Conversions
    -- freezeST,
  )
where

import AtCoder.Extra.Pool qualified as P
import AtCoder.Internal.Assert qualified as ACIA
import Control.Monad (unless)
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
import Data.Coerce (coerce)
import Data.Vector.Generic.Mutable qualified as VGM
import Data.Vector.Unboxed qualified as VU
import Data.Vector.Unboxed.Mutable qualified as VUM
import GHC.Stack (HasCallStack)
import Prelude hiding (read)

-- | A dynamic, sparse segment tree that covers a half-open interval \([l_0, r_0)\). Is is dynamic
-- in that the nodes are instantinated as needed.
--
-- @since 1.2.1.0
data DynSparseSegTree s a = DynSparseSegTree
  { -- | The maximum number of nodes allocated
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> Int
capacityDsst :: {-# UNPACK #-} !Int,
    -- | Whether the data is persistent or not
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> Bool
isPersistentDsst :: {-# UNPACK #-} !Bool,
    -- | Left index boundary (inclusive)
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> Int
l0Dsst :: {-# UNPACK #-} !Int,
    -- | Right index boundary (exclusive)
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> Int
r0Dsst :: {-# UNPACK #-} !Int,
    -- | `Pool` for free slot management.
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> Pool s ()
poolDsst :: !(P.Pool s ()),
    -- | Decomposed node storage: left children
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> MVector s Index
lDsst :: !(VUM.MVector s P.Index),
    -- | Decomposed node storage: right children
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: !(VUM.MVector s P.Index),
    -- | Decomposed node storage: position
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> MVector s a
xDsst :: !(VUM.MVector s a),
    -- | Decomposed node storage: position
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> MVector s Int
iDsst :: !(VUM.MVector s Int),
    -- | Decomposed node storage: monoid product
    --
    -- @since 1.2.1.0
    forall s a. DynSparseSegTree s a -> MVector s a
prodDsst :: !(VUM.MVector s a)
  }

-- | \(O(n)\)
--
-- @since 1.2.1.0
{-# INLINEABLE newST #-}
newST :: (HasCallStack, VU.Unbox a) => Bool -> Int -> Int -> Int -> ST s (DynSparseSegTree s a)
newST :: forall a s.
(HasCallStack, Unbox a) =>
Bool -> Int -> Int -> Int -> ST s (DynSparseSegTree s a)
newST Bool
isPersistentDsst Int
capacityDsst Int
l0Dsst Int
r0Dsst = do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
l0Dsst Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
r0Dsst) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.Extra.DynSparseSegTree.Raw.newST: given invalid interval " String -> String -> String
forall a. [a] -> [a] -> [a]
++ (Int, Int) -> String
forall a. Show a => a -> String
show (Int
l0Dsst, Int
r0Dsst)
  Pool s ()
poolDsst <- Int -> ST s (Pool (PrimState (ST s)) ())
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Int -> m (Pool (PrimState m) a)
P.new Int
capacityDsst
  MVector s Index
lDsst <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityDsst
  MVector s Index
rDsst <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityDsst
  MVector s a
xDsst <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityDsst
  MVector s Int
iDsst <- Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityDsst
  MVector s a
prodDsst <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityDsst
  DynSparseSegTree s a -> ST s (DynSparseSegTree s a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
isPersistentDsst :: Bool
capacityDsst :: Int
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..}

-- | \(O(1)\)
--
-- @since 1.2.1.0
{-# INLINE newRootST #-}
newRootST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> ST s P.Index
newRootST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> ST s Index
newRootST DynSparseSegTree s a
_ = do
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex

-- | \(O(1)\)
--
-- @since 1.2.1.0
{-# INLINE newNodeST #-}
newNodeST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> Int -> a -> ST s P.Index
newNodeST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Int -> a -> ST s Index
newNodeST DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..} Int
idx !a
x = do
  Index
i <- Pool (PrimState (ST s)) () -> () -> ST s Index
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Pool (PrimState m) a -> a -> m Index
P.alloc Pool s ()
Pool (PrimState (ST s)) ()
poolDsst ()
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
P.undefIndex
  MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Index
P.undefIndex
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
x
  MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) Int
idx
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
x
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
i

-- | \(O(n)\)
--
-- @since 1.2.1.0
{-# INLINE freeSubtreeST #-}
freeSubtreeST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> P.Index -> ST s ()
freeSubtreeST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s ()
freeSubtreeST DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..} Index
i = do
  let inner :: Index -> ST s ()
inner Index
c = do
        Index
cl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
        Index
cr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cl) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ Pool (PrimState (ST s)) () -> Index -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
Pool (PrimState m) a -> Index -> m ()
P.free Pool s ()
Pool (PrimState (ST s)) ()
poolDsst Index
cl
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cr) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ Pool (PrimState (ST s)) () -> Index -> ST s ()
forall (m :: * -> *) a.
PrimMonad m =>
Pool (PrimState m) a -> Index -> m ()
P.free Pool s ()
Pool (PrimState (ST s)) ()
poolDsst Index
cr
  Index -> ST s ()
inner Index
i

-- | \(O(\log L)\)
--
-- @since 1.2.1.0
{-# INLINEABLE modifyMST #-}
modifyMST :: forall m a. (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => DynSparseSegTree (PrimState m) a -> P.Index -> (a -> m a) -> Int -> m P.Index
modifyMST :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Monoid a, Unbox a) =>
DynSparseSegTree (PrimState m) a
-> Index -> (a -> m a) -> Int -> m Index
modifyMST dst :: DynSparseSegTree (PrimState m) a
dst@DynSparseSegTree {Bool
Int
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Index
Pool (PrimState m) ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool (PrimState m) ()
lDsst :: MVector (PrimState m) Index
rDsst :: MVector (PrimState m) Index
xDsst :: MVector (PrimState m) a
iDsst :: MVector (PrimState m) Int
prodDsst :: MVector (PrimState m) a
..} Index
root a -> m a
f Int
i0
  | Index -> Bool
P.nullIndex Index
root = ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> (a -> ST (PrimState m) Index) -> a -> m Index
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DynSparseSegTree (PrimState m) a
-> Int -> a -> ST (PrimState m) Index
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Int -> a -> ST s Index
newNodeST DynSparseSegTree (PrimState m) a
dst Int
i0 (a -> m Index) -> m a -> m Index
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f a
forall a. Monoid a => a
mempty
  | Bool
otherwise = Index -> Int -> Int -> Int -> m Index
inner Index
root Int
l0Dsst Int
r0Dsst Int
i0
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> ()
ACIA.checkIndexBounded String
"AtCoder.Extra.DynSparseSegTree.Raw.modifyMST" Int
i0 Int
l0Dsst Int
r0Dsst
    inner :: P.Index -> Int -> Int -> Int -> m P.Index
    inner :: Index -> Int -> Int -> Int -> m Index
inner Index
c_ Int
l Int
r Int
i
      | Index -> Bool
P.nullIndex Index
c_ = ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> (a -> ST (PrimState m) Index) -> a -> m Index
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DynSparseSegTree (PrimState m) a
-> Int -> a -> ST (PrimState m) Index
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Int -> a -> ST s Index
newNodeST DynSparseSegTree (PrimState m) a
dst Int
i (a -> m Index) -> m a -> m Index
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f a
forall a. Monoid a => a
mempty
      | Bool
otherwise = do
          Index
c <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a -> Index -> ST (PrimState m) Index
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s Index
cloneOnWriteST DynSparseSegTree (PrimState m) a
dst Index
c_
          Int
ci <- ST (PrimState m) Int -> m Int
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Int -> m Int) -> ST (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          if Int
ci Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
i
            then do
              MVector (PrimState m) a -> (a -> m a) -> Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector (PrimState m) a
xDsst a -> m a
f (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
              ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a -> Index -> ST (PrimState m) ()
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s ()
updateNodeST DynSparseSegTree (PrimState m) a
dst Index
c
              Index -> m Index
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c
            else do
              -- update left or right child
              let m :: Int
m = (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
              if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m
                then do
                  Index
cl <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
                  if Int
ci Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
i
                    then do
                      -- TODO: is this statement correct?
                      -- now we know `i` does not exist in the segment tree.
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Int
i
                      a
cx <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a)
-> (a -> ST (PrimState m) a) -> a -> m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> m a) -> m a -> m a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f a
forall a. Monoid a => a
mempty
                      -- re-allocate `c` as a child:
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cl Int
l Int
m Int
ci a
cx
                    else do
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> m Index
inner Index
cl Int
l Int
m Int
i
                else do
                  Index
cr <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
                  if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
ci
                    then do
                      -- now we know `i` does not exist in the segment tree.
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Int
i
                      a
cx <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a)
-> (a -> ST (PrimState m) a) -> a -> m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> m a) -> m a -> m a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< a -> m a
f a
forall a. Monoid a => a
mempty
                      -- re-allocate `c` as a child:
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cr Int
m Int
r Int
ci a
cx
                    else do
                      ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> m Index
inner Index
cr Int
m Int
r Int
i

              ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a -> Index -> ST (PrimState m) ()
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s ()
updateNodeST DynSparseSegTree (PrimState m) a
dst Index
c
              Index -> m Index
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c

    -- insert new node
    inner2 :: P.Index -> Int -> Int -> Int -> a -> m P.Index
    inner2 :: Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
c_ Int
l Int
r Int
i a
x
      | Index -> Bool
P.nullIndex Index
c_ = ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a
-> Int -> a -> ST (PrimState m) Index
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Int -> a -> ST s Index
newNodeST DynSparseSegTree (PrimState m) a
dst Int
i a
x
      | Bool
otherwise = do
          Index
c <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a -> Index -> ST (PrimState m) Index
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s Index
cloneOnWriteST DynSparseSegTree (PrimState m) a
dst Index
c_
          Int
ci <- ST (PrimState m) Int -> m Int
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Int -> m Int) -> ST (PrimState m) Int -> m Int
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
ci Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
i) String
"AtCoder.Extra.DynSparseSegTree.Raw.modifyMST: wrong implementation"
          -- update left or right child
          let m :: Int
m = (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
          if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m
            then do
              Index
cl <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
              if Int
ci Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
i
                then do
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Int
i
                  a
cx <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) a
x
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cl Int
l Int
m Int
ci a
cx
                else do
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cl Int
l Int
m Int
i a
x
            else do
              Index
cr <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
              if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
ci
                then do
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Int
-> Int -> Int -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Int
i
                  a
cx <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) a
-> Int -> a -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) a
x
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cr Int
m Int
r Int
ci a
cx
                else do
                  ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ())
-> (Index -> ST (PrimState m) ()) -> Index -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MVector (PrimState (ST (PrimState m))) Index
-> Int -> Index -> ST (PrimState m) ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (Index -> m ()) -> m Index -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Index -> Int -> Int -> Int -> a -> m Index
inner2 Index
cr Int
m Int
r Int
i a
x

          ST (PrimState m) () -> m ()
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) () -> m ()) -> ST (PrimState m) () -> m ()
forall a b. (a -> b) -> a -> b
$ DynSparseSegTree (PrimState m) a -> Index -> ST (PrimState m) ()
forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s ()
updateNodeST DynSparseSegTree (PrimState m) a
dst Index
c
          Index -> m Index
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c

-- | \(O(\log L)\)
--
-- @since 1.2.1.0
{-# INLINEABLE prodST #-}
prodST :: forall a s. (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> P.Index -> Int -> Int -> ST s a
prodST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> Int -> Int -> ST s a
prodST DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..} Index
root0 Int
ql0 Int
qr0
  | Int
ql0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
qr0 Bool -> Bool -> Bool
|| Index -> Bool
P.nullIndex Index
root0 = a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
forall a. Monoid a => a
mempty
  | Bool
otherwise = Index -> Int -> Int -> Int -> Int -> a -> ST s a
inner Index
root0 Int
l0Dsst Int
r0Dsst Int
ql0 Int
qr0 a
forall a. Monoid a => a
mempty
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> Int -> ()
ACIA.checkIntervalBounded String
"AtCoder.Extra.DynSparseSegTree.Raw.prodST" Int
ql0 Int
qr0 Int
l0Dsst Int
r0Dsst
    -- left to right
    -- - l, r: node interval
    -- - ql, qr: queried interval
    inner :: P.Index -> Int -> Int -> Int -> Int -> a -> ST s a
    inner :: Index -> Int -> Int -> Int -> Int -> a -> ST s a
inner Index
c Int
l Int
r Int
ql_ Int
qr_ !a
x
      | Int
len Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x
      | Index -> Bool
P.nullIndex Index
c = a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x
      | Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
ql Bool -> Bool -> Bool
&& Int
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
qr = do
          a
cProd <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> ST s a) -> a -> ST s a
forall a b. (a -> b) -> a -> b
$! a
x a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
cProd
      | Bool
otherwise = do
          let m :: Int
m = (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
          Index
cl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          a
x' <- Index -> Int -> Int -> Int -> Int -> a -> ST s a
inner Index
cl Int
l Int
m Int
ql Int
qr a
x
          Int
ci <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          a
x'' <- if Int
ql Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
ci Bool -> Bool -> Bool
&& Int
ci Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
qr then (a
x' <>) (a -> a) -> ST s a -> ST s a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) else a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x'
          Index
cr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          Index -> Int -> Int -> Int -> Int -> a -> ST s a
inner Index
cr Int
m Int
r Int
ql Int
qr a
x''
      where
        -- shrink target interval to node interval
        ql :: Int
ql = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
ql_ Int
l
        qr :: Int
qr = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
qr_ Int
r
        len :: Int
len = Int
qr Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
ql

-- | \(O(\log L)\)
--
-- ==== Constraints
-- - The segment tree is not empty
-- - User predicate \(f\) returns `True` for `mempty`
--
-- @since 1.2.1.0
{-# INLINEABLE maxRightM #-}
maxRightM :: (HasCallStack, PrimMonad m, Monoid a, VU.Unbox a) => DynSparseSegTree (PrimState m) a -> P.Index -> (a -> m Bool) -> m Int
maxRightM :: forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Monoid a, Unbox a) =>
DynSparseSegTree (PrimState m) a -> Index -> (a -> m Bool) -> m Int
maxRightM DynSparseSegTree {Bool
Int
MVector (PrimState m) a
MVector (PrimState m) Int
MVector (PrimState m) Index
Pool (PrimState m) ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool (PrimState m) ()
lDsst :: MVector (PrimState m) Index
rDsst :: MVector (PrimState m) Index
xDsst :: MVector (PrimState m) a
iDsst :: MVector (PrimState m) Int
prodDsst :: MVector (PrimState m) a
..} Index
root a -> m Bool
f = do
  (!Int
r, !a
_) <- Index -> Int -> Int -> a -> m (Int, a)
inner Index
root Int
l0Dsst Int
r0Dsst a
forall a. Monoid a => a
mempty
  Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
r
  where
    -- returning `r0Dsst` means "go right"
    inner :: Index -> Int -> Int -> a -> m (Int, a)
inner Index
c Int
l Int
r !a
xParent
      | Index -> Bool
P.nullIndex Index
c = (Int, a) -> m (Int, a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r0Dsst, a
xParent)
      | Bool
otherwise = do
          a
xWhole <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ (a
xParent <>) (a -> a) -> ST (PrimState m) a -> ST (PrimState m) a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          Bool
b <- a -> m Bool
f a
xWhole
          if Bool
b
            then do
              (Int, a) -> m (Int, a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
r0Dsst, a
xWhole)
            else do
              let m :: Int
m = (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
r) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
              Index
cl <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
              (!Int
k, !a
xl) <- Index -> Int -> Int -> a -> m (Int, a)
inner Index
cl Int
l Int
m a
xParent
              if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
r0Dsst
                then (Int, a) -> m (Int, a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
k, a
xl)
                else do
                  a
xm <- ST (PrimState m) a -> m a
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) a -> m a) -> ST (PrimState m) a -> m a
forall a b. (a -> b) -> a -> b
$ (a
xl <>) (a -> a) -> ST (PrimState m) a -> ST (PrimState m) a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) a
-> Int -> ST (PrimState m) a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) a
MVector (PrimState (ST (PrimState m))) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
                  Bool
b' <- a -> m Bool
f a
xm
                  if Bool -> Bool
not Bool
b'
                    then ST (PrimState m) (Int, a) -> m (Int, a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Int, a) -> m (Int, a))
-> ST (PrimState m) (Int, a) -> m (Int, a)
forall a b. (a -> b) -> a -> b
$ (,a
xm) (Int -> (Int, a))
-> ST (PrimState m) Int -> ST (PrimState m) (Int, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST (PrimState m))) Int
-> Int -> ST (PrimState m) Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Int
MVector (PrimState (ST (PrimState m))) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
                    else do
                      Index
cr <- ST (PrimState m) Index -> m Index
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) Index -> m Index)
-> ST (PrimState m) Index -> m Index
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST (PrimState m))) Index
-> Int -> ST (PrimState m) Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector (PrimState m) Index
MVector (PrimState (ST (PrimState m))) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
                      Index -> Int -> Int -> a -> m (Int, a)
inner Index
cr Int
m Int
r a
xm

-- -------------------------------------------------------------------------------------------------
-- Internals
-- -------------------------------------------------------------------------------------------------

-- | \(O(1)\) Optionally clones a node depending on the persistency setting.
{-# INLINEABLE cloneOnWriteST #-}
cloneOnWriteST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> P.Index -> ST s P.Index
cloneOnWriteST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s Index
cloneOnWriteST DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..} Index
c
  | Bool -> Bool
not Bool
isPersistentDsst Bool -> Bool -> Bool
|| Index -> Bool
P.nullIndex Index
c = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c
  | Bool
otherwise = do
      Index
i <- Pool (PrimState (ST s)) () -> () -> ST s Index
forall (m :: * -> *) a.
(HasCallStack, PrimMonad m, Unbox a) =>
Pool (PrimState m) a -> a -> m Index
P.alloc Pool s ()
Pool (PrimState (ST s)) ()
poolDsst ()
      MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (Index -> ST s ()) -> ST s Index -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      MVector (PrimState (ST s)) Index -> Int -> Index -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (Index -> ST s ()) -> ST s Index -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s Int
MVector (PrimState (ST s)) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (Int -> ST s ()) -> ST s Int -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Int
MVector (PrimState (ST s)) Int
iDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
i

-- | \(O(1)\)
{-# INLINEABLE updateNodeST #-}
updateNodeST :: (HasCallStack, Monoid a, VU.Unbox a) => DynSparseSegTree s a -> P.Index -> ST s ()
updateNodeST :: forall a s.
(HasCallStack, Monoid a, Unbox a) =>
DynSparseSegTree s a -> Index -> ST s ()
updateNodeST DynSparseSegTree {Bool
Int
MVector s a
MVector s Int
MVector s Index
Pool s ()
capacityDsst :: forall s a. DynSparseSegTree s a -> Int
isPersistentDsst :: forall s a. DynSparseSegTree s a -> Bool
l0Dsst :: forall s a. DynSparseSegTree s a -> Int
r0Dsst :: forall s a. DynSparseSegTree s a -> Int
poolDsst :: forall s a. DynSparseSegTree s a -> Pool s ()
lDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
rDsst :: forall s a. DynSparseSegTree s a -> MVector s Index
xDsst :: forall s a. DynSparseSegTree s a -> MVector s a
iDsst :: forall s a. DynSparseSegTree s a -> MVector s Int
prodDsst :: forall s a. DynSparseSegTree s a -> MVector s a
capacityDsst :: Int
isPersistentDsst :: Bool
l0Dsst :: Int
r0Dsst :: Int
poolDsst :: Pool s ()
lDsst :: MVector s Index
rDsst :: MVector s Index
xDsst :: MVector s a
iDsst :: MVector s Int
prodDsst :: MVector s a
..} Index
c = do
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
xDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
  Index
cl <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
lDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cl) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    a
prodL <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)
    MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
prodDsst (a
prodL <>) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
  Index
cr <- MVector (PrimState (ST s)) Index -> Int -> ST s Index
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s Index
MVector (PrimState (ST s)) Index
rDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Index -> Bool
P.nullIndex Index
cr) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    a
prodR <- MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s a
MVector (PrimState (ST s)) a
prodDsst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
    MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.modify MVector s a
MVector (PrimState (ST s)) a
prodDsst (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
prodR) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)