{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_HADDOCK hide #-}

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

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

    -- * Constructors
    newST,
    newRootST,
    newNodeST,
    newSeqST,

    -- * Accessing elements
    modifyMST,

    -- * Products
    prodST,
    -- prodMaybe,

    -- * Applications
    applyInST,

    -- * Tree operations
    copyIntervalWithST,
    resetIntervalST,

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

import AtCoder.Extra.Pool qualified as P
import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.LazySegTree (SegAct (..))
import Control.Monad (when)
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
import Data.Coerce (coerce)
import Data.Maybe (fromMaybe)
import Data.Vector.Generic qualified as VG
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, lazily propagated segment tree that covers a half-open interval \([l_0, r_0)\).
-- The nodes are instantinated as needed.
--
-- @since 1.2.1.0
data DynLazySegTree s f a = DynLazySegTree
  { -- | The maximum number of nodes allocated
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Int
capacityLdst :: {-# UNPACK #-} !Int,
    -- | Whether the data is persistent or not
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Bool
isPersistentLdst :: {-# UNPACK #-} !Bool,
    -- | Left index boundary (inclusive)
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Int
l0Ldst :: {-# UNPACK #-} !Int,
    -- | Right index boundary (exclusive)
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: {-# UNPACK #-} !Int,
    -- | Initial monoid value assignment \(g: (l, r) \rightarrow a\)
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Int -> Int -> a
initialProdLdst :: !(Int -> Int -> a),
    -- | `Pool` for free slot management.
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> Pool s ()
poolLdst :: !(P.Pool s ()),
    -- | Decomposed node storage: left children
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> MVector s Index
lLdst :: !(VUM.MVector s P.Index),
    -- | Decomposed node storage: right children
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: !(VUM.MVector s P.Index),
    -- | Decomposed node storage: monoid value
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> MVector s a
xLdst :: !(VUM.MVector s a),
    -- | Decomposed node storage: lazily propagated monoid action
    --
    -- @since 1.2.1.0
    forall s f a. DynLazySegTree s f a -> MVector s f
lazyLdst :: !(VUM.MVector s f)
  }

-- | \(O(n)\)
--
-- @since 1.2.1.0
{-# INLINEABLE newST #-}
newST :: (HasCallStack, VU.Unbox f, VU.Unbox a) => Bool -> Int -> Int -> Int -> (Int -> Int -> a) -> ST s (DynLazySegTree s f a)
newST :: forall f a s.
(HasCallStack, Unbox f, Unbox a) =>
Bool
-> Int
-> Int
-> Int
-> (Int -> Int -> a)
-> ST s (DynLazySegTree s f a)
newST Bool
isPersistentLdst Int
capacityLdst Int
l0Ldst Int
r0Ldst Int -> Int -> a
initialProdLdst = do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
l0Ldst Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
r0Ldst) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.Extra.DynLazySegTree.Raw.newST: given invalid interval " String -> String -> String
forall a. [a] -> [a] -> [a]
++ (Int, Int) -> String
forall a. Show a => a -> String
show (Int
l0Ldst, Int
r0Ldst)
  Pool s ()
poolLdst <- Int -> ST s (Pool (PrimState (ST s)) ())
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Int -> m (Pool (PrimState m) a)
P.new Int
capacityLdst
  MVector s Index
lLdst <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityLdst
  MVector s Index
rLdst <- Int -> ST s (MVector (PrimState (ST s)) Index)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityLdst
  MVector s a
xLdst <- Int -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityLdst
  MVector s f
lazyLdst <- Int -> ST s (MVector (PrimState (ST s)) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
VUM.unsafeNew Int
capacityLdst
  DynLazySegTree s f a -> ST s (DynLazySegTree s f a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
isPersistentLdst :: Bool
capacityLdst :: Int
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..}

-- | \(O(1)\)
--
-- @since 1.2.1.0
{-# INLINE newRootST #-}
newRootST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> ST s P.Index
newRootST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> ST s Index
newRootST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} = do
  DynLazySegTree s f a -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree s f a
dst Int
l0Ldst Int
r0Ldst

-- | \(O(1)\)
--
-- @since 1.2.1.0
{-# INLINE newNodeST #-}
newNodeST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> a -> ST s P.Index
newNodeST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} !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)) ()
poolLdst ()
  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
lLdst (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
rLdst (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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) a
x
  MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) f
forall a. Monoid a => a
mempty
  Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
i

-- | \(O(L)\)
--
-- @since 1.2.1.0
{-# INLINEABLE newSeqST #-}
newSeqST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> VU.Vector a -> ST s P.Index
newSeqST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Vector a -> ST s Index
newSeqST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} !Vector a
xs = do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
l0Ldst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& Int
r0Ldst Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs) String
"AtCoder.Extra.DynLazySegTree.Raw: mismatch between the bounds and the input vector: the bounds must be [0, n)"
  -- run DFS and allocate nodes from left to right
  let dfs :: Int -> Int -> ST s Index
dfs Int
l Int
r
        | Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
        | Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = DynLazySegTree s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree s f a
dst (a -> ST s Index) -> a -> ST s Index
forall a b. (a -> b) -> a -> b
$ Vector a
xs Vector a -> Int -> a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
v a -> Int -> a
VG.! Int
l
        | 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
lRoot <- Int -> Int -> ST s Index
dfs Int
l Int
m
            Index
rRoot <- Int -> Int -> ST s Index
dfs Int
m Int
r
            a
xlRoot <- 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
lRoot)
            a
xrRoot <- 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
rRoot)
            let !x :: a
x = a
xlRoot a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
xrRoot
            Index
root <- DynLazySegTree s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree s f a
dst a
x
            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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
lRoot
            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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root) Index
rRoot
            Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
  Int -> Int -> ST s Index
dfs Int
0 (Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
xs)

-- | \(O(1)\)
--
-- ==== Constraints
-- - The interval must be non-empty
--
-- @since 1.2.1.0
{-# INLINE newNodeInST #-}
newNodeInST :: (HasCallStack, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> Int -> Int -> ST s P.Index
newNodeInST :: forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Int -> Int -> a
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
initialProdLdst :: Int -> Int -> a
initialProdLdst} Int
l Int
r = do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
l) (String -> ()) -> String -> ()
forall a b. (a -> b) -> a -> b
$ String
"AtCoder.Extra.DynLazySegTree.Raw.nodeNodeInST: not empty or negative interval: " String -> String -> String
forall a. [a] -> [a] -> [a]
++ (Int, Int) -> String
forall a. Show a => a -> String
show (Int
l, Int
r)
  DynLazySegTree s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree s f a
dst (a -> ST s Index) -> a -> ST s Index
forall a b. (a -> b) -> a -> b
$! Int -> Int -> a
initialProdLdst Int
l Int
r

-- | \(O(\log L)\)
--
-- @since 1.2.1.0
{-# INLINEABLE modifyMST #-}
modifyMST :: forall m f a. (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree (PrimState m) f a -> P.Index -> (a -> m a) -> Int -> m P.Index
modifyMST :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
DynLazySegTree (PrimState m) f a
-> Index -> (a -> m a) -> Int -> m Index
modifyMST dst :: DynLazySegTree (PrimState m) f a
dst@DynLazySegTree {Bool
Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Index
Pool (PrimState m) ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool (PrimState m) ()
lLdst :: MVector (PrimState m) Index
rLdst :: MVector (PrimState m) Index
xLdst :: MVector (PrimState m) a
lazyLdst :: MVector (PrimState m) f
..} Index
root a -> m a
f Int
i = Index -> Int -> Int -> m Index
inner Index
root Int
l0Ldst Int
r0Ldst
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> ()
ACIA.checkIndexBounded String
"AtCoder.Extra.DynLazySegTree.Raw.modifyMST" Int
i Int
l0Ldst Int
r0Ldst
    inner :: P.Index -> Int -> Int -> m P.Index
    inner :: Index -> Int -> Int -> m Index
inner Index
c Int
l Int
r
      | Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = do
          -- let !_ = ACIA.runtimeAssert (i == l) ""
          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
$ DynLazySegTree (PrimState m) f a -> Index -> ST (PrimState m) Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree (PrimState m) f a
dst Index
c
          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
xLdst 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
$ MVector (PrimState (ST (PrimState m))) f
-> Int -> f -> 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) f
MVector (PrimState (ST (PrimState m))) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c') f
forall a. Monoid a => a
mempty
          Index -> m Index
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c'
      | Bool
otherwise = 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
$ DynLazySegTree (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
propST DynLazySegTree (PrimState m) f a
dst Index
c Int
l Int
r
          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

          -- lazily allocate left and right children:
          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
$ do
            Index
j <- 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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
            if Index -> Bool
P.nullIndex Index
j
              then do
                Index
j' <- DynLazySegTree (PrimState m) f a
-> Int -> Int -> ST (PrimState m) Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree (PrimState m) f a
dst Int
l Int
m
                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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
j'
                Index -> ST (PrimState m) Index
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
j'
              else Index -> ST (PrimState m) Index
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
j

          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
$ do
            Index
j <- 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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
            if Index -> Bool
P.nullIndex Index
j
              then do
                Index
j' <- DynLazySegTree (PrimState m) f a
-> Int -> Int -> ST (PrimState m) Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree (PrimState m) f a
dst Int
m Int
r
                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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
j'
                Index -> ST (PrimState m) Index
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
j'
              else Index -> ST (PrimState m) Index
forall a. a -> ST (PrimState m) a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
j

          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
$ DynLazySegTree (PrimState m) f a -> Index -> ST (PrimState m) Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree (PrimState m) f a
dst Index
c
          if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m
            then 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
lLdst (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 -> m Index
inner Index
cl Int
l Int
m
            else 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
rLdst (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 -> m Index
inner Index
cr Int
m Int
r

          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
$ do
            -- Note that either left or right child of `c'` is updated in the above `if`
            a
clx <- 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
xLdst (Int -> ST (PrimState m) a)
-> (Index -> Int) -> Index -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index -> Int
forall a b. Coercible a b => a -> b
coerce (Index -> ST (PrimState m) a)
-> ST (PrimState m) Index -> ST (PrimState m) a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m 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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
            a
crx <- 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
xLdst (Int -> ST (PrimState m) a)
-> (Index -> Int) -> Index -> ST (PrimState m) a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index -> Int
forall a b. Coercible a b => a -> b
coerce (Index -> ST (PrimState m) a)
-> ST (PrimState m) Index -> ST (PrimState m) a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m 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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
            MVector (PrimState (ST (PrimState m))) a
-> Int -> a -> 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) a
MVector (PrimState (ST (PrimState m))) a
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c') (a -> ST (PrimState m) ()) -> a -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$! a
clx a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
crx
          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 applyInST #-}
applyInST :: forall f a s. (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> P.Index -> Int -> Int -> f -> ST s P.Index
applyInST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> f -> ST s Index
applyInST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} Index
root0 Int
ql0 Int
qr0 !f
f
  | Int
ql0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
qr0 = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root0
  | Bool
otherwise = Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
root0 Int
l0Ldst Int
r0Ldst Int
ql0 Int
qr0
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> Int -> ()
ACIA.checkIntervalBounded String
"AtCoder.Extra.DynLazySegTree.Raw.applyInST" Int
ql0 Int
qr0 Int
l0Ldst Int
r0Ldst
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Bool -> Bool
not (Index -> Bool
P.nullIndex Index
root0)) String
"AtCoder.Extra.DynLazySegTree.Raw.applyInST"
    -- left to right
    -- - l, r: node interval
    -- - ql, qr: queried interval
    inner :: P.Index -> Int -> Int -> Int -> Int -> ST s P.Index
    inner :: Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
c_ Int
l Int
r Int
ql_ Int
qr_ = do
      Index
c <- if Index -> Bool
P.nullIndex Index
c_ then DynLazySegTree s f a -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree s f a
dst Int
l Int
r else Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c_
      if Int
len Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
        then do
          -- A node of length zero would be created if the interval length is odd. It's OK:
          Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c
        else
          if 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
            then do
              Index
c' <- DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
c
              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
xLdst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
              MVector (PrimState (ST s)) f -> (f -> f) -> 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 f
MVector (PrimState (ST s)) f
lazyLdst (f
f <>) (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
c'
            else do
              DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
propST DynLazySegTree s f a
dst Index
c Int
l Int
r
              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
c' <- DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
c
              MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
lLdst (\Index
i -> Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
i Int
l Int
m Int
ql Int
qr) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
              MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
rLdst (\Index
i -> Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
i Int
m Int
r Int
ql Int
qr) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
              a
clx <- 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
xLdst (Int -> ST s a) -> (Index -> Int) -> Index -> ST s a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index -> Int
forall a b. Coercible a b => a -> b
coerce (Index -> ST s a) -> ST s Index -> ST s a
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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
              a
crx <- 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
xLdst (Int -> ST s a) -> (Index -> Int) -> Index -> ST s a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Index -> Int
forall a b. Coercible a b => a -> b
coerce (Index -> ST s a) -> ST s Index -> ST s a
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
rLdst (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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c') (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a
clx a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
crx
              Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c'
      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)\)
--
-- @since 1.2.1.0
{-# INLINEABLE prodST #-}
prodST :: forall f a s. (HasCallStack, SegAct f a, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> P.Index -> Int -> Int -> ST s a
prodST :: forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s a
prodST DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} 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 -> f -> ST s a
inner Index
root0 Int
l0Ldst Int
r0Ldst Int
ql0 Int
qr0 a
forall a. Monoid a => a
mempty f
forall a. Monoid a => a
mempty
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> Int -> ()
ACIA.checkIntervalBounded String
"AtCoder.Extra.DynLazySegTree.Raw.prodST" Int
ql0 Int
qr0 Int
l0Ldst Int
r0Ldst
    -- left to right
    -- - l, r: node interval
    -- - ql, qr: queried interval
    inner :: P.Index -> Int -> Int -> Int -> Int -> a -> f -> ST s a
    inner :: Index -> Int -> Int -> Int -> Int -> a -> f -> ST s a
inner Index
c Int
l Int
r Int
ql_ Int
qr_ !a
x !f
f
      | 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 = do
          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
<> Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f (Int -> Int -> a
initialProdLdst Int
ql Int
qr)
      | 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
cx <- 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
xLdst (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
<> Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f a
cx
      | 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
          !f
f' <- (f
f <>) (f -> f) -> ST s f -> ST s f
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) f -> Int -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s f
MVector (PrimState (ST s)) f
lazyLdst (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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          a
x' <- Index -> Int -> Int -> Int -> Int -> a -> f -> ST s a
inner Index
cl Int
l Int
m Int
ql Int
qr a
x f
f'
          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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          a
x'' <- Index -> Int -> Int -> Int -> Int -> a -> f -> ST s a
inner Index
cr Int
m Int
r Int
ql Int
qr a
x' f
f'
          a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure 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)\)
--
-- @since 1.2.1.0
{-# INLINEABLE copyIntervalWithST #-}
copyIntervalWithST ::
  forall f a s.
  (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  -- | Dynamic segment tree
  DynLazySegTree s f a ->
  -- | Root to be modified
  P.Index ->
  -- | Another segment tree
  P.Index ->
  -- | \(l\)
  Int ->
  -- | \(r\)
  Int ->
  -- | Action \(f\)
  f ->
  -- | New root
  ST s P.Index
copyIntervalWithST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a
-> Index -> Index -> Int -> Int -> f -> ST s Index
copyIntervalWithST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} Index
rootA Index
rootB Int
ql0 Int
qr0 !f
f0
  | Index
rootA Index -> Index -> Bool
forall a. Eq a => a -> a -> Bool
== Index
rootB = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
rootA
  | Bool
otherwise = do
      if Int
ql0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
qr0
        then Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
rootA
        else do
          Index
rootA' <- DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
rootA
          Index -> Index -> Int -> Int -> Int -> Int -> f -> ST s ()
inner Index
rootA' Index
rootB Int
l0Ldst Int
r0Ldst Int
ql0 Int
qr0 f
f0
          Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
rootA'
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> Int -> ()
ACIA.checkIntervalBounded String
"AtCoder.Extra.DynLazySegTree.Raw.copyIntervalWithST" Int
ql0 Int
qr0 Int
l0Ldst Int
r0Ldst
    !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Bool -> Bool
not (Index -> Bool
P.nullIndex Index
rootA)) String
"AtCoder.Extra.DynLazySegTree.Raw.copyIntervalWithST: given null"

    -- left to right
    -- - l, r: node interval
    -- - ql, qr: queried interval
    inner :: P.Index -> P.Index -> Int -> Int -> Int -> Int -> f -> ST s ()
    inner :: Index -> Index -> Int -> Int -> Int -> Int -> f -> ST s ()
inner Index
c Index
d Int
l Int
r Int
ql_ Int
qr_ !f
f
      | Int
len Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure () -- `c` is already cloned
      | 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
          if Bool -> Bool
not (Index -> Bool
P.nullIndex Index
d)
            then 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> ST s ()) -> (a -> a) -> a -> ST s ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f (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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
              MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (f -> ST s ()) -> (f -> f) -> f -> ST s ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (f
f <>) (f -> ST s ()) -> ST s f -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) f -> Int -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
              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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
              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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
            else 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> ST s ()) -> (a -> a) -> a -> ST s ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! Int -> Int -> a
initialProdLdst Int
l Int
r
              MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) f
f
              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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) 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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) Index
P.undefIndex
      | 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
          MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
lLdst (\Index
i -> if Index -> Bool
P.nullIndex Index
i then DynLazySegTree s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree s f a
dst (Int -> Int -> a
initialProdLdst Int
l Int
m) else DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
i) (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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
rLdst (\Index
i -> if Index -> Bool
P.nullIndex Index
i then DynLazySegTree s f a -> a -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> a -> ST s Index
newNodeST DynLazySegTree s f a
dst (Int -> Int -> a
initialProdLdst Int
m Int
r) else DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
i) (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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
          f
cLazy <- MVector (PrimState (ST s)) f -> Int -> f -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.exchange MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) f
forall a. Monoid a => a
mempty
          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
xLdst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) f
cLazy) (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
xLdst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
m) f
cLazy) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
          MVector (PrimState (ST s)) f -> (f -> f) -> 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 f
MVector (PrimState (ST s)) f
lazyLdst (f
cLazy <>) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)
          MVector (PrimState (ST s)) f -> (f -> f) -> 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 f
MVector (PrimState (ST s)) f
lazyLdst (f
cLazy <>) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
          !f
f' <- if Index -> Bool
P.nullIndex Index
d then f -> ST s f
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure f
f else (f
f <>) (f -> f) -> ST s f -> ST s f
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) f -> Int -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
          Index
dl' <- Index -> Maybe Index -> Index
forall a. a -> Maybe a -> a
fromMaybe Index
P.undefIndex (Maybe Index -> Index) -> ST s (Maybe Index) -> ST s Index
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) Index -> Int -> ST s (Maybe Index)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (Maybe a)
VGM.readMaybe MVector s Index
MVector (PrimState (ST s)) Index
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
          Index
dr' <- Index -> Maybe Index -> Index
forall a. a -> Maybe a -> a
fromMaybe Index
P.undefIndex (Maybe Index -> Index) -> ST s (Maybe Index) -> ST s Index
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState (ST s)) Index -> Int -> ST s (Maybe Index)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (Maybe a)
VGM.readMaybe MVector s Index
MVector (PrimState (ST s)) Index
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
d)
          Index -> Index -> Int -> Int -> Int -> Int -> f -> ST s ()
inner Index
cl Index
dl' Int
l Int
m Int
ql Int
qr f
f'
          Index -> Index -> Int -> Int -> Int -> Int -> f -> ST s ()
inner Index
cr Index
dr' Int
m Int
r Int
ql Int
qr f
f'
          a
clx <- 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)
          a
crx <- 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
          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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a
clx a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
crx
      where
        !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Bool -> Bool
not (Index -> Bool
P.nullIndex Index
c)) String
"AtCoder.Extra.DynLazySegTree.Raw.copyIntervalWithST: implementation error"
        -- 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)\) Resets an interval \([l, r)\) to initial monoid values.
--
-- @since 1.2.1.0
{-# INLINEABLE resetIntervalST #-}
resetIntervalST ::
  forall f a s.
  (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) =>
  DynLazySegTree s f a ->
  P.Index ->
  Int ->
  Int ->
  ST s P.Index
resetIntervalST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s Index
resetIntervalST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} Index
root Int
ql0 Int
qr0
  | Int
ql0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
qr0 = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root
  | Index -> Bool
P.nullIndex Index
root = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
  | Int
ql0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l0Ldst Bool -> Bool -> Bool
&& Int
qr0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r0Ldst = do
      -- for the case of non-persistent segment tere, we should update the root in-place:
      Index
root' <- DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
root
      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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! Int -> Int -> a
initialProdLdst Int
l0Ldst Int
r0Ldst
      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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') 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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') Index
P.undefIndex
      MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
root') f
forall a. Monoid a => a
mempty
      Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
root'
  | Bool
otherwise = Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
root Int
l0Ldst Int
r0Ldst Int
ql0 Int
qr0
  where
    !()
_ = HasCallStack => String -> Int -> Int -> Int -> Int -> ()
String -> Int -> Int -> Int -> Int -> ()
ACIA.checkIntervalBounded String
"AtCoder.Extra.DynLazySegTree.Raw.resetIntervalST" Int
ql0 Int
qr0 Int
l0Ldst Int
r0Ldst

    -- replace interval with null
    inner :: P.Index -> Int -> Int -> Int -> Int -> ST s P.Index
    inner :: Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
c Int
l Int
r Int
ql_ Int
qr_
      -- TODO: shall we allocate new node?
      | Int
len Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c
      | 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
P.undefIndex
      -- NOTE: we're returning `undefIndex`, but we can instead free the subtree if it's not persistent
      | Int
ql Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l Bool -> Bool -> Bool
&& Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
qr = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
P.undefIndex
      | Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 = Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c
      | Bool
otherwise = do
          DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
propST DynLazySegTree s f a
dst Index
c Int
l Int
r
          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
c' <- DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
c
          MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
lLdst (\Index
i -> Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
i Int
l Int
m Int
ql Int
qr) (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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
          MVector (PrimState (ST s)) Index
-> (Index -> ST s Index) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> m a) -> Int -> m ()
VGM.modifyM MVector s Index
MVector (PrimState (ST s)) Index
rLdst (\Index
i -> Index -> Int -> Int -> Int -> Int -> ST s Index
inner Index
i Int
m Int
r Int
ql Int
qr) (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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c')
          a
clx <- if Index -> Bool
P.nullIndex Index
cl then 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
$! Int -> Int -> a
initialProdLdst Int
l Int
m else 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)
          a
crx <- if Index -> Bool
P.nullIndex Index
cr then 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
$! Int -> Int -> a
initialProdLdst Int
m Int
r else 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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
          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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c') (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a
clx a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
crx
          Index -> ST s Index
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c'
      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

-- It returns only allocated leaf values
-- {-# INLINEABLE freezeST #-}
-- freezeST :: forall f a s. (HasCallStack, SegAct f a, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> P.Index -> ST s (VU.Vector a)
-- freezeST DynLazySegTree {..} root = do
--   buf <- B.new (r0Ldst - l0Ldst)
--
--   let inner c l r !f
--         | P.nullIndex c = pure ()
--         | r - l == 1 = do
--             x <- VGM.read xLdst (coerce c)
--             B.pushBack buf $! segAct f x
--         | otherwise = do
--             let m = (l + r) `div` 2
--             !f' <- (f <>) <$> VGM.read lazyLdst (coerce c)
--             cl <- VGM.read lLdst (coerce c)
--             cr <- VGM.read rLdst (coerce c)
--             inner cl l m f'
--             inner cr m r f'
--
--   inner root l0Ldst r0Ldst mempty
--   B.unsafeFreeze buf

-- | \(O(\log L)\)
--
-- @since 1.2.1.0
{-# INLINEABLE maxRightM #-}
maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree (PrimState m) f a -> P.Index -> (a -> m Bool) -> m Int
maxRightM :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f,
 Monoid a, Unbox a) =>
DynLazySegTree (PrimState m) f a -> Index -> (a -> m Bool) -> m Int
maxRightM dst :: DynLazySegTree (PrimState m) f a
dst@DynLazySegTree {Bool
Int
MVector (PrimState m) f
MVector (PrimState m) a
MVector (PrimState m) Index
Pool (PrimState m) ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool (PrimState m) ()
lLdst :: MVector (PrimState m) Index
rLdst :: MVector (PrimState m) Index
xLdst :: MVector (PrimState m) a
lazyLdst :: MVector (PrimState m) f
..} Index
root !a -> m Bool
f = do
  (!Int
r, !a
_) <- Index -> Int -> Int -> a -> m (Int, a)
inner Index
root Int
l0Ldst Int
r0Ldst 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
    -- FIXME: it should not allocate new nodes
    inner :: Index -> Int -> Int -> a -> m (Int, a)
inner Index
c_ Int
l Int
r !a
x = do
      Index
c <- if Index -> Bool
P.nullIndex Index
c_ then 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
$ DynLazySegTree (PrimState m) f a
-> Int -> Int -> ST (PrimState m) Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree (PrimState m) f a
dst Int
l Int
r else Index -> m Index
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Index
c_
      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
x <>) (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
xLdst (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
r, a
xWhole)
        else do
          if Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
            then (Int, a) -> m (Int, a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int
l, a
x)
            else 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
$ DynLazySegTree (PrimState m) f a
-> Index -> Int -> Int -> ST (PrimState m) ()
forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
propST DynLazySegTree (PrimState m) f a
dst Index
c Int
l Int
r
              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
lLdst (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
x
              if Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
m
                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
                  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
rLdst (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
xl

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

-- | \(O(1)\) Optionally clones a node depending on the persistency setting.
{-# INLINEABLE cloneOnWriteST #-}
cloneOnWriteST :: (HasCallStack, SegAct f a, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> P.Index -> ST s P.Index
cloneOnWriteST :: forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} Index
c
  | Bool -> Bool
not Bool
isPersistentLdst 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)) ()
poolLdst ()
      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
lLdst (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
lLdst (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
rLdst (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
rLdst (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
xLdst (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
xLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
i) (f -> ST s ()) -> ST s f -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MVector (PrimState (ST s)) f -> Int -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s f
MVector (PrimState (ST s)) f
lazyLdst (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 propST #-}
propST :: (HasCallStack, SegAct f a, Eq f, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => DynLazySegTree s f a -> P.Index -> Int -> Int -> ST s ()
propST :: forall f a s.
(HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
DynLazySegTree s f a -> Index -> Int -> Int -> ST s ()
propST dst :: DynLazySegTree s f a
dst@DynLazySegTree {Bool
Int
MVector s f
MVector s a
MVector s Index
Pool s ()
Int -> Int -> a
capacityLdst :: forall s f a. DynLazySegTree s f a -> Int
isPersistentLdst :: forall s f a. DynLazySegTree s f a -> Bool
l0Ldst :: forall s f a. DynLazySegTree s f a -> Int
r0Ldst :: forall s f a. DynLazySegTree s f a -> Int
initialProdLdst :: forall s f a. DynLazySegTree s f a -> Int -> Int -> a
poolLdst :: forall s f a. DynLazySegTree s f a -> Pool s ()
lLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
rLdst :: forall s f a. DynLazySegTree s f a -> MVector s Index
xLdst :: forall s f a. DynLazySegTree s f a -> MVector s a
lazyLdst :: forall s f a. DynLazySegTree s f a -> MVector s f
capacityLdst :: Int
isPersistentLdst :: Bool
l0Ldst :: Int
r0Ldst :: Int
initialProdLdst :: Int -> Int -> a
poolLdst :: Pool s ()
lLdst :: MVector s Index
rLdst :: MVector s Index
xLdst :: MVector s a
lazyLdst :: MVector s f
..} Index
c Int
l Int
r = do
  let !()
_ = HasCallStack => Bool -> String -> ()
Bool -> String -> ()
ACIA.runtimeAssert (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
2) String
"AtCoder.Extra.DynLazySegTree.Raw.propST: the interval must have length more than or equal to `2`"
  f
cLazy <- MVector (PrimState (ST s)) f -> Int -> ST s f
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.read MVector s f
MVector (PrimState (ST s)) f
lazyLdst (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 ()
when (f
cLazy f -> f -> Bool
forall a. Eq a => a -> a -> Bool
/= f
forall a. Monoid a => a
mempty) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ 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

    -- create or clone left child
    Index
cl <- do
      Index
i <- 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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      if Index -> Bool
P.nullIndex Index
i
        then DynLazySegTree s f a -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree s f a
dst Int
l Int
m
        else DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
i
    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
lLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) 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
xLdst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l) f
cLazy) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)
    MVector (PrimState (ST s)) f -> (f -> f) -> 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 f
MVector (PrimState (ST s)) f
lazyLdst (f
cLazy <>) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cl)

    -- create or clone right child
    Index
cr <- do
      Index
i <- 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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c)
      if Index -> Bool
P.nullIndex Index
i
        then DynLazySegTree s f a -> Int -> Int -> ST s Index
forall f a s.
(HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Int -> Int -> ST s Index
newNodeInST DynLazySegTree s f a
dst Int
m Int
r
        else DynLazySegTree s f a -> Index -> ST s Index
forall f a s.
(HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) =>
DynLazySegTree s f a -> Index -> ST s Index
cloneOnWriteST DynLazySegTree s f a
dst Index
i
    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
rLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) 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
xLdst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
m) f
cLazy) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)
    MVector (PrimState (ST s)) f -> (f -> f) -> 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 f
MVector (PrimState (ST s)) f
lazyLdst (f
cLazy <>) (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
cr)

    -- clear the lazy action
    MVector (PrimState (ST s)) f -> Int -> f -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.write MVector s f
MVector (PrimState (ST s)) f
lazyLdst (Index -> Int
forall a b. Coercible a b => a -> b
coerce Index
c) f
forall a. Monoid a => a
mempty