{-# LANGUAGE RecordWildCards #-}

-- | A lazily propagted segment tree. It is the data structure for the pair of a [monoid](https://en.wikipedia.org/wiki/Monoid)
-- \((S, \cdot: S \times S \to S, e \in S)\) and a set \(F\) of \(S \to S\) mappings that satisfies
-- the following properties.
--
-- - \(F\) contains the identity map \(\mathrm{id}\) such that \(\mathrm{id}(x) = x\) holds for all
-- \(x \in S\).
-- - \(F\) is closed under composition, i.e., \(f \circ g \in F\) holds for all \(f, g \in F\).
-- - \(f(x \cdot y) = f(x) \cdot f(y)\) holds for all \(f \in F\) and \(x, y \in S\).
--
-- Given an array \(S\) of length \(N\), it processes the following queries in \(O(\log N)\) time.
--
-- - Acting the map \(f\in F\) (cf. \(x = f(x)\)) on all the elements of an interval
-- - Calculating the product of the elements of an interval
--
-- In Haskell types, \(F\) is a `SegAct` (@'segAct' f@) and \(S\) is a `Monoid`. For simplicity, in
-- this document, we assume that the relevant methods work in constant time. If these they work in
-- \(O(T)\) time, each time complexity appear in this document is multipled by \(O(T)\).
--
-- ==== __Example__
-- Here we'll use `AtCoder.Extra.Monoid.Affine1` as a monoid action \(F\) and `Data.Semigroup.Sum`
-- as the acted monoid \(S\):
--
-- >>> import AtCoder.LazySegTree qualified as LST
-- >>> import AtCoder.Extra.Monoid (SegAct(..), Affine1(..)) -- `SegAct` is also re-exported in Extra.Monoid.
-- >>> import Data.Semigroup (Sum(..))
--
-- Use `build` to construct a `LazySegTree` with initial values. @'build' \@_ \@f \@a@ constructs a
-- `LazySegTree` of 'SegAct' @f a@:
--
-- >>> seg <- LST.build @_ @(Affine1 Int) @(Sum Int) $ VU.fromList [1, 2, 3, 4]
--
-- `applyIn` @seg l r f@ applies an action \(f\) to an interval \([l, r)\):
--
-- >>> LST.applyIn seg 1 3 $ Affine1 (2, 1) -- [1, 5, 7, 4]
--
-- Modify one element with `write`, `modify`, `modifyM` or `applyAt`:
--
-- >>> LST.write seg 3 $ Sum 10 -- [1, 5, 7, 10]
-- >>> LST.modify seg (+ 1) 0   -- [2, 5, 7, 10]
--
-- Read the values with `read`, `prod` or `allProd`:
--
-- >>> LST.read seg 1
-- Sum {getSum = 5}
--
-- >>> LST.prod seg 0 3 -- product (fold) of `Sum Int` in interval [0, 3)
-- Sum {getSum = 14}
--
-- >>> LST.allProd seg
-- Sum {getSum = 24}
--
-- Run binary search:
--
-- >>> LST.maxRight seg 0 (<= (Sum 10)) -- sum [0, 2) = 7 <= 10
-- 2
--
-- >>> LST.minLeft seg 4 (<= (Sum 10)) -- sum [3, 4) = 10 <= 10
-- 3
--
-- Inspect all the values in \(O(n \log n)\) with `freeze` or `unsafeFreeze`:
--
-- >>> VU.map getSum <$> LST.freeze seg
-- [2,5,7,10]
--
-- ==== Tips
--
-- - `prod` returns \(a_l \cdot a_{l + 1} \cdot .. \cdot a_{r - 1}\). If you need \(a_{r - 1} \cdot a_{r - 2} \cdot .. \cdot a_{l}\),
-- wrap your monoid in `Data.Monoid.Dual`.
-- - If you ever need to store boxed types to `LazySegTree`, wrap it in @Data.Vector.Unboxed.DoNotUnboxStrict@
-- or the like.
--
-- ==== Major changes from the original @ac-library@
-- - The API is based on `Monoid` and `SegAct`, not the functions @op@, @e@, @mapping@,
-- @composition@ and @id@.
-- - @get@ and @set@ are renamed to `read` and `write`.
-- - `modify`, `modifyM`, `exchange`, `freeze` and `unsafeFreeze` are added.
--
-- @since 1.0.0.0
module AtCoder.LazySegTree
  ( -- * Lazy segment tree
    SegAct (..),
    LazySegTree (nLst, sizeLst, logLst),

    -- * Constructors
    new,
    build,

    -- * Accessing elements
    write,
    modify,
    modifyM,
    exchange,
    read,

    -- * Products
    prod,
    prodMaybe,
    allProd, -- FIXME: rename to prodAll

    -- * Applications
    applyAt,
    applyIn,

    -- * Binary searches

    -- ** Left binary searches
    minLeft,
    minLeftM,

    -- ** Right binary searches
    maxRight,
    maxRightM,

    -- * Conversions
    freeze,
    unsafeFreeze,
  )
where

import AtCoder.Internal.Assert qualified as ACIA
import AtCoder.Internal.Bit qualified as ACIBIT
import Control.Monad (unless, when)
import Control.Monad.Primitive (PrimMonad, PrimState, stToPrim)
import Control.Monad.ST (ST)
import Data.Bits (bit, countLeadingZeros, countTrailingZeros, testBit, (.&.), (.<<.), (.>>.))
import Data.Foldable (for_)
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)

-- | Typeclass reprentation of the `LazySegTree` properties. User can implement either `segAct` or
-- `segActWithLength`.
--
-- Instances should satisfy the follwing properties:
--
-- [Left monoid action] @'segAct' (f2 '<>' f1) x = 'segAct' f2 ('segAct' f1 x)@
-- [Identity map] @`segAct` `mempty` x = x@
-- [Endomorphism] @'segAct' f (x1 '<>' x2) = ('segAct' f x1) '<>' ('segAct' f x2)@
--
-- If you implement `SegAct` via `segActWithLength`, satisfy one more propety:
--
-- [Linear left monoid action] @'segActWithLength' len f (stimes len a) = 'Data.Semigroup.stimes' len ('segAct' f a)@.
--
-- ==== Invariant
-- In `SegAct` instances, new semigroup values are always given from the left: @new '<>' old@. The
-- order is important for non-commutative monoid implementations.
--
-- ==== __Example instance__
-- Take `AtCoder.Extra.Monoid.Affine1` as an example of type \(F\).
--
-- @
-- {-# LANGUAGE TypeFamilies #-}
--
-- import AtCoder.LazySegTree qualified as LST
-- import AtCoder.LazySegTree (SegAct (..))
-- import Data.Monoid
-- 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
--
-- -- | f x = a * x + b. It's implemented as a newtype of `(a, a)` for easy `Unbox` deriving.
-- newtype 'AtCoder.Extra.Monoid.Affine1.Affine1' a = 'AtCoder.Extra.Monoid.Affine1.Affine1' ('AtCoder.Extra.Monoid.Affine1.Affine1' a)
--   deriving newtype ('Eq', 'Ord', 'Show')
--
-- -- | This type alias makes the 'Data.Vector.Unboxed.Unbox' deriving easier, described velow.
-- type 'AtCoder.Extra.Monoid.Affine1.Affine1Repr' a = (a, a)
--
-- instance ('Num' a) => 'Semigroup' ('AtCoder.Extra.Monoid.Affine1.Affine1' a) where
--   {-# INLINE ('<>') #-}
--   ('AtCoder.Extra.Monoid.Affine1.Affine1' (!a1, !b1)) '<>' ('AtCoder.Extra.Monoid.Affine1.Affine1' (!a2, !b2)) = 'AtCoder.Extra.Monoid.Affine1.Affine1' (a1 * a2, a1 * b2 + b1)
--
-- instance ('Num' a) => 'Monoid' ('AtCoder.Extra.Monoid.Affine1.Affine1' a) where
--   {-# INLINE 'mempty' #-}
--   'mempty' = 'AtCoder.Extra.Monoid.Affine1.Affine1' (1, 0)
--
-- instance ('Num' a) => 'SegAct' ('AtCoder.Extra.Monoid.Affine1.Affine1' a) ('Sum' a) where
--   {-# INLINE segActWithLength #-}
--   'segActWithLength' len ('AtCoder.Extra.Monoid.Affine1.Affine1' (!a, !b)) !x = a * x + b * fromIntegral len
-- @
--
-- Deriving 'Data.Vector.Unboxed.Unbox' is very easy for such a newtype (though the efficiency is
-- not the maximum):
--
-- @
-- newtype instance VU.MVector s ('AtCoder.Extra.Monoid.Affine1.Affine1' a) = MV_Affine1 (VU.MVector s ('AtCoder.Extra.Monoid.Affine1.Affine1' a))
-- newtype instance VU.Vector ('AtCoder.Extra.Monoid.Affine1.Affine1' a) = V_Affine1 (VU.Vector ('AtCoder.Extra.Monoid.Affine1.Affine1' a))
-- deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector ('AtCoder.Extra.Monoid.Affine1.Affine1' a)
-- deriving instance (VU.Unbox a) => VG.Vector VU.Vector ('AtCoder.Extra.Monoid.Affine1.Affine1' a)
-- instance (VU.Unbox a) => VU.Unbox ('AtCoder.Extra.Monoid.Affine1.Affine1' a)
-- @
--
-- ==== __Example contest template__
-- Define your monoid action @F@ and your acted monoid @X@:
--
-- @
-- {-# LANGUAGE DerivingStrategies #-}
-- {-# LANGUAGE TypeFamilies #-}
--
-- import AtCoder.LazySegTree qualified as LST
-- import AtCoder.LazySegTree (SegAct (..))
-- 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
--
-- {- ORMOLU_DISABLE -}
-- -- | `F` is a custom monoid action, defined as a newtype of `FRepr`.
-- newtype F = F FRepr deriving newtype (Eq, Ord, Show) ; unF :: F -> FRepr ; unF (F x) = x ; newtype instance VU.MVector s F = MV_F (VU.MVector s FRepr) ; newtype instance VU.Vector F = V_F (VU.Vector FRepr) ; deriving instance VGM.MVector VUM.MVector F ; deriving instance VG.Vector VU.Vector F ; instance VU.Unbox F ;
-- {- ORMOLU_ENABLE -}
--
-- -- | Affine: f x = a * x + b
-- type FRepr = (Int, Int)
--
-- instance Semigroup F where
--   -- @new <> old@
--   {-# INLINE (<>) #-}
--   (F (!a1, !b1)) <> (F (!a2, !b2)) = F (a1 * a2, a1 * b2 + b1)
--
-- instance Monoid F where
--   {-# INLINE mempty #-}
--   mempty = F (1, 0)
--
-- {- ORMOLU_DISABLE -}
-- -- | `X` is a custom acted monoid, defined as a newtype of `XRepr`.
-- newtype X = X XRepr deriving newtype (Eq, Ord, Show) ; unX :: X -> XRepr ; unX (X x) = x; newtype instance VU.MVector s X = MV_X (VU.MVector s XRepr) ; newtype instance VU.Vector X = V_X (VU.Vector XRepr) ; deriving instance VGM.MVector VUM.MVector X ; deriving instance VG.Vector VU.Vector X ; instance VU.Unbox X ;
-- {- ORMOLU_ENABLE -}
--
-- -- | Acted `Int` (same as `Sum Int`).
-- type XRepr = Int
--
-- deriving instance Num X; -- in our case `X` is a `Num`.
--
-- instance Semigroup X where
--   {-# INLINE (<>) #-}
--   (X x1) <> (X x2) = X $! x1 + x2
--
-- instance Monoid X where
--   {-# INLINE mempty #-}
--   mempty = X 0
--
-- instance SegAct F X where
--   -- {-# INLINE segAct #-}
--   -- segAct len (F (!a, !b)) (X x) = X $! a * x + b
--   {-# INLINE segActWithLength #-}
--   segActWithLength len (F (!a, !b)) (X x) = X $! a * x + len * b
-- @
--
-- It's tested as below:
--
-- @
-- expect :: (Eq a, Show a) => String -> a -> a -> ()
-- expect msg a b
--   | a == b = ()
--   | otherwise = error $ msg ++ ": expected " ++ show a ++ ", found " ++ show b
--
-- main :: IO ()
-- main = do
--   seg <- LST.build @_ @F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]
--   LST.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]
--   LST.write seg 3 $ X 10 -- [1, 5, 7, 10]
--   LST.modify seg (+ (X 1)) 0   -- [2, 5, 7, 10]
--   !_ \<- (expect "test 1" (X 5)) \<$> LST.read seg 1
--   !_ \<- (expect "test 2" (X 14)) \<$> LST.prod seg 0 3 -- reads an interval [0, 3)
--   !_ \<- (expect "test 3" (X 24)) \<$> LST.allProd seg
--   !_ \<- (expect "test 4" 2) \<$> LST.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10
--   !_ \<- (expect "test 5" 3) \<$> LST.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10
--   putStrLn "=> test passed!"
-- @
--
-- @since 1.0.0.0
class (Monoid f) => SegAct f a where
  -- | Lazy segment tree action \(f(x)\).
  --
  -- @since 1.0.0.0
  {-# INLINE segAct #-}
  segAct :: f -> a -> a
  segAct = Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
1

  -- | Lazy segment tree action \(f(x)\) with the target monoid's length.
  --
  -- If you implement `SegAct` with this function, you don't have to store the monoid's length,
  -- since it's given externally.
  --
  -- @since 1.0.0.0
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> f -> a -> a
  segActWithLength Int
_ = f -> a -> a
forall f a. SegAct f a => f -> a -> a
segAct

-- | @since 1.2.0.0
instance SegAct () a where
  {-# INLINE segAct #-}
  segAct :: () -> a -> a
segAct ()
_ = a -> a
forall a. a -> a
id
  {-# INLINE segActWithLength #-}
  segActWithLength :: Int -> f -> a -> a
  segActWithLength :: forall f. Int -> f -> a -> a
segActWithLength Int
_ f
_ = a -> a
forall a. a -> a
id

-- | A lazily propagated segment tree defined around `SegAct`.
--
-- @since 1.0.0.0
data LazySegTree s f a = LazySegTree
  { -- | Valid length.
    --
    -- @since 1.0.0.0
    forall s f a. LazySegTree s f a -> Int
nLst :: {-# UNPACK #-} !Int,
    -- | \(\lceil \log_2 \mathrm{nLst} \rceil\)
    --
    -- @since 1.0.0.0
    forall s f a. LazySegTree s f a -> Int
sizeLst :: {-# UNPACK #-} !Int,
    -- | \(\log_2 \mathrm{sizeLst}\).
    --
    -- @since 1.0.0.0
    forall s f a. LazySegTree s f a -> Int
logLst :: {-# UNPACK #-} !Int,
    -- | Data storage of length @2 * sizeLst@.
    forall s f a. LazySegTree s f a -> MVector s a
dLst :: !(VUM.MVector s a),
    -- | Data storage of length @sizeLst@.
    forall s f a. LazySegTree s f a -> MVector s f
lzLst :: !(VUM.MVector s f)
  }

-- | Creates an array of length \(n\). All the elements are initialized to `mempty`.
--
-- ==== Constraints
-- - \(0 \leq n\)
--
-- ==== Complexity
-- - \(O(n)\)
--
-- @since 1.0.0.0
{-# INLINE new #-}
new :: (HasCallStack, PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => Int -> m (LazySegTree (PrimState m) f a)
new :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a,
 Unbox a) =>
Int -> m (LazySegTree (PrimState m) f a)
new Int
nLst
  | Int
nLst Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = ST (PrimState m) (LazySegTree (PrimState m) f a)
-> m (LazySegTree (PrimState m) f a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (LazySegTree (PrimState m) f a)
 -> m (LazySegTree (PrimState m) f a))
-> ST (PrimState m) (LazySegTree (PrimState m) f a)
-> m (LazySegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ Vector a -> ST (PrimState m) (LazySegTree (PrimState m) f a)
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
Vector a -> ST s (LazySegTree s f a)
buildST (Vector a -> ST (PrimState m) (LazySegTree (PrimState m) f a))
-> Vector a -> ST (PrimState m) (LazySegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ Int -> a -> Vector a
forall a. Unbox a => Int -> a -> Vector a
VU.replicate Int
nLst a
forall a. Monoid a => a
mempty
  | Bool
otherwise = [Char] -> m (LazySegTree (PrimState m) f a)
forall a. HasCallStack => [Char] -> a
error ([Char] -> m (LazySegTree (PrimState m) f a))
-> [Char] -> m (LazySegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ [Char]
"new: given negative size `" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
nLst [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"`"

-- | Creates an array with initial values \(vs\).
--
-- ==== Constraints
-- - \(0 \leq n\)
--
-- ==== Complexity
-- - \(O(n)\)
--
-- @since 1.0.0.0
{-# INLINE build #-}
build :: (PrimMonad m, Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => VU.Vector a -> m (LazySegTree (PrimState m) f a)
build :: forall (m :: * -> *) f a.
(PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) =>
Vector a -> m (LazySegTree (PrimState m) f a)
build Vector a
vs = ST (PrimState m) (LazySegTree (PrimState m) f a)
-> m (LazySegTree (PrimState m) f a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (LazySegTree (PrimState m) f a)
 -> m (LazySegTree (PrimState m) f a))
-> ST (PrimState m) (LazySegTree (PrimState m) f a)
-> m (LazySegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ Vector a -> ST (PrimState m) (LazySegTree (PrimState m) f a)
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
Vector a -> ST s (LazySegTree s f a)
buildST Vector a
vs

-- | Sets \(p\)-th value of the array to \(x\).
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE write #-}
write :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m ()
write :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> a -> m ()
write LazySegTree (PrimState m) f a
self Int
p 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
$ LazySegTree (PrimState m) f a -> Int -> a -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> a -> ST s ()
writeST LazySegTree (PrimState m) f a
self Int
p a
x
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.write" Int
p (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | (Extra API) Modifies \(p\)-th value with a function \(f\).
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE modify #-}
modify :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modify :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modify LazySegTree (PrimState m) f a
self a -> a
f Int
p = 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
$ LazySegTree (PrimState m) f a
-> (a -> a) -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> (a -> a) -> Int -> ST s ()
modifyST LazySegTree (PrimState m) f a
self a -> a
f Int
p
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.modify" Int
p (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | (Extra API) Modifies \(p\)-th value with a monadic function \(f\).
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINEABLE modifyM #-}
modifyM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> (a -> m a) -> Int -> m ()
modifyM :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> (a -> m a) -> Int -> m ()
modifyM self :: LazySegTree (PrimState m) f a
self@LazySegTree {Int
MVector (PrimState m) f
MVector (PrimState m) a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector (PrimState m) a
lzLst :: MVector (PrimState m) f
..} a -> m a
f Int
p = do
  let !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.modifyM" Int
p Int
nLst
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  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
$ [Int] -> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST (PrimState m) ()) -> ST (PrimState m) ())
-> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree (PrimState m) f a
self (Int -> ST (PrimState m) ()) -> Int -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  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
dLst a -> m a
f Int
p'
  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
$ [Int] -> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST (PrimState m) ()) -> ST (PrimState m) ())
-> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree (PrimState m) f a
self (Int -> ST (PrimState m) ()) -> Int -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i

-- | (Extra API) Sets \(p\)-th value of the array to \(x\) and returns the old value.
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.1.0.0
{-# INLINE exchange #-}
exchange :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m a
exchange :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> a -> m a
exchange LazySegTree (PrimState m) f a
self Int
p a
x = 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
$ LazySegTree (PrimState m) f a -> Int -> a -> ST (PrimState m) a
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> a -> ST s a
exchangeST LazySegTree (PrimState m) f a
self Int
p a
x
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.exchange" Int
p (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | Returns \(p\)-th value of the array.
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE read #-}
read :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> m a
read :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> m a
read LazySegTree (PrimState m) f a
self Int
p = 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
$ LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) a
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s a
readST LazySegTree (PrimState m) f a
self Int
p
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.read" Int
p (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | Returns the product of \([a[l], ..., a[r - 1]]\), assuming the properties of the monoid. It
-- returns `mempty` if \(l = r\).
--
-- ==== Constraints
-- - \(0 \leq l \leq r \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE prod #-}
prod :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m a
prod :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> Int -> m a
prod self :: LazySegTree (PrimState m) f a
self@LazySegTree {Int
nLst :: forall s f a. LazySegTree s f a -> Int
nLst :: Int
nLst} Int
l0 Int
r0
  | Bool -> Bool
not (Int -> Int -> Int -> Bool
ACIA.testInterval Int
l0 Int
r0 Int
nLst) = [Char] -> Int -> Int -> Int -> m a
forall a. HasCallStack => [Char] -> Int -> Int -> Int -> a
ACIA.errorInterval [Char]
"AtCoder.LazySegTree.prod" Int
l0 Int
r0 Int
nLst
  | Int
l0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r0 = a -> m a
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
forall a. Monoid a => a
mempty
  | Bool
otherwise = 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
$ LazySegTree (PrimState m) f a -> Int -> Int -> ST (PrimState m) a
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> Int -> ST s a
unsafeProdST LazySegTree (PrimState m) f a
self Int
l0 Int
r0

-- | Total variant of `prod`. Returns the product of \([a[l], ..., a[r - 1]]\), assuming the
-- properties of the monoid. Returns `Just` `mempty` if \(l = r\). It returns `Nothing` if the
-- interval is invalid.
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE prodMaybe #-}
prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m (Maybe a)
prodMaybe :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> Int -> m (Maybe a)
prodMaybe self :: LazySegTree (PrimState m) f a
self@LazySegTree {Int
nLst :: forall s f a. LazySegTree s f a -> Int
nLst :: Int
nLst} Int
l0 Int
r0
  | Bool -> Bool
not (Int -> Int -> Int -> Bool
ACIA.testInterval Int
l0 Int
r0 Int
nLst) = Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing
  | Int
l0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r0 = Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Maybe a
forall a. a -> Maybe a
Just a
forall a. Monoid a => a
mempty)
  | Bool
otherwise = ST (PrimState m) (Maybe a) -> m (Maybe a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Maybe a) -> m (Maybe a))
-> ST (PrimState m) (Maybe a) -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> ST (PrimState m) a -> ST (PrimState m) (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> LazySegTree (PrimState m) f a -> Int -> Int -> ST (PrimState m) a
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> Int -> ST s a
unsafeProdST LazySegTree (PrimState m) f a
self Int
l0 Int
r0

-- | Returns the product of \([op(a[0], ..., a[n - 1])]\), assuming the properties of the monoid. It
-- returns `mempty` if \(n = 0\).
--
-- ==== Complexity
-- - \(O(1)\)
--
-- @since 1.0.0.0
{-# INLINE allProd #-}
allProd :: (PrimMonad m, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m a
allProd :: forall (m :: * -> *) a f.
(PrimMonad m, Monoid a, Unbox a) =>
LazySegTree (PrimState m) f a -> m a
allProd LazySegTree {Int
MVector (PrimState m) a
MVector (PrimState m) f
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector (PrimState m) a
lzLst :: MVector (PrimState m) f
..} = MVector (PrimState m) a -> Int -> 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
dLst Int
1

-- | Applies @segAct f@ to an index \(p\).
--
-- ==== Constraints
-- - \(0 \leq p \lt n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE applyAt #-}
applyAt :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> f -> m ()
applyAt :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> f -> m ()
applyAt LazySegTree (PrimState m) f a
self Int
p f
f = 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
$ LazySegTree (PrimState m) f a -> Int -> f -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
applyAtST LazySegTree (PrimState m) f a
self Int
p f
f
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> ()
[Char] -> Int -> Int -> ()
ACIA.checkIndex [Char]
"AtCoder.LazySegTree.applyAt" Int
p (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | Applies @segAct f@ to an interval \([l, r)\).
--
-- ==== Constraints
-- - \(0 \leq l \leq r \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE applyIn #-}
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> f -> m ()
applyIn :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> Int -> f -> m ()
applyIn LazySegTree (PrimState m) f a
self Int
l0 Int
r0 f
f = 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
$ LazySegTree (PrimState m) f a
-> Int -> Int -> f -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> Int -> f -> ST s ()
applyInST LazySegTree (PrimState m) f a
self Int
l0 Int
r0 f
f
  where
    !()
_ = HasCallStack => [Char] -> Int -> Int -> Int -> ()
[Char] -> Int -> Int -> Int -> ()
ACIA.checkInterval [Char]
"AtCoder.LazySegTree.applyIn" Int
l0 Int
r0 (LazySegTree (PrimState m) f a -> Int
forall s f a. LazySegTree s f a -> Int
nLst LazySegTree (PrimState m) f a
self)

-- | Applies a binary search on the segment tree. It returns an index \(l\) that satisfies both of the
-- following.
--
-- - \(l = r\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\) returns `True`.
-- - \(l = 0\) or \(g(a[l - 1] \cdot a[l] \cdot ... \cdot a[r - 1])\) returns `False`.
--
-- If \(g\) is monotone, this is the minimum \(l\) that satisfies
-- \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).
--
-- ==== Constraints
--
-- - if \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
-- - @g mempty == True@.
-- - \(0 \leq r \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE minLeft #-}
minLeft :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
minLeft :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
minLeft LazySegTree (PrimState m) f a
seg Int
r0 a -> Bool
g = LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
minLeftM LazySegTree (PrimState m) f a
seg Int
r0 (Bool -> m Bool
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> m Bool) -> (a -> Bool) -> a -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
g)

-- | Monadic variant of `minLeft`.
--
-- ==== Constraints
--
-- - if \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
-- - @g mempty == True@.
-- - \(0 \leq r \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINEABLE minLeftM #-}
minLeftM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
minLeftM :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
minLeftM self :: LazySegTree (PrimState m) f a
self@LazySegTree {Int
MVector (PrimState m) f
MVector (PrimState m) a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector (PrimState m) a
lzLst :: MVector (PrimState m) f
..} Int
r0 a -> m Bool
g = do
  Bool
b <- a -> m Bool
g a
forall a. Monoid a => a
mempty
  let !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert Bool
b [Char]
"AtCoder.LazySegTree.minLeftM: `g empty` returned `False`"
  if Int
r0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
    then Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0
    else do
      let r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
      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
$ [Int] -> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST (PrimState m) ()) -> ST (PrimState m) ())
-> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
        LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree (PrimState m) f a
self (Int -> ST (PrimState m) ()) -> Int -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
      Int -> a -> m Int
inner Int
r a
forall a. Monoid a => a
mempty
  where
    -- NOTE: Not ordinary bounds check!
    !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
r0 Bool -> Bool -> Bool
&& Int
r0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
nLst) ([Char] -> ()) -> [Char] -> ()
forall a b. (a -> b) -> a -> b
$ [Char]
"AtCoder.LazySegTree.minLeftM: given invalid `right` index `" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
r0 [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"` over length `" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
nLst [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"`"
    inner :: Int -> a -> m Int
inner Int
r !a
sm = do
      let r' :: Int
r' = Int -> Int
forall {b}. (Integral b, Bits b) => b -> b
chooseBit (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
      !a
sm' <- (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
sm) (a -> a) -> m a -> m a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) a -> Int -> 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
dLst Int
r'
      Bool
b <- a -> m Bool
g a
sm'
      if Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Bool
b
        then do
          Int -> a -> m Int
inner2 Int
r' a
sm
        else do
          if (Int
r' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (-Int
r')) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
r'
            then Int -> a -> m Int
inner Int
r' a
sm'
            else Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
0
    chooseBit :: b -> b
chooseBit b
r
      | b
r b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
1 Bool -> Bool -> Bool
&& b -> Bool
forall a. Integral a => a -> Bool
odd b
r = b -> b
chooseBit (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ b
r b -> Int -> b
forall a. Bits a => a -> Int -> a
.>>. Int
1
      | Bool
otherwise = b
r
    inner2 :: Int -> a -> m Int
inner2 Int
r a
sm
      | Int
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
sizeLst = do
          let r' :: Int
r' = Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
          a
sm' <- 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
$ do
            LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree (PrimState m) f a
self Int
r
            (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
sm) (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
dLst Int
r'
          Bool
b <- a -> m Bool
g a
sm'
          if Bool
b
            then Int -> a -> m Int
inner2 (Int
r' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a
sm'
            else Int -> a -> m Int
inner2 Int
r' a
sm
      | Bool
otherwise = Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
sizeLst

-- | Applies a binary search on the segment tree. It returns an index \(r\) that satisfies both of the
-- followings.
--
-- - \(r = l\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1]))\) returns `True`.
-- - \(r = n\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r]))\) returns `False`.
--
-- If \(g\) is monotone, this is the maximum \(r\) that satisfies
-- \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).
--
-- ==== Constraints
--
-- - If \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
-- - @g mempty == True@.
-- - \(0 \leq l \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINE maxRight #-}
maxRight :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
maxRight :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
maxRight LazySegTree (PrimState m) f a
seg Int
l0 a -> Bool
g = LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
maxRightM LazySegTree (PrimState m) f a
seg Int
l0 (Bool -> m Bool
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Bool -> m Bool) -> (a -> Bool) -> a -> m Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
g)

-- | Monadic variant of `maxRight`.
--
-- ==== Constraints
--
-- - If \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
-- - @g mempty == True@.
-- - \(0 \leq l \leq n\)
--
-- ==== Complexity
-- - \(O(\log n)\)
--
-- @since 1.0.0.0
{-# INLINEABLE maxRightM #-}
maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
maxRightM :: forall (m :: * -> *) f a.
(HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a,
 Unbox a) =>
LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
maxRightM self :: LazySegTree (PrimState m) f a
self@LazySegTree {Int
MVector (PrimState m) f
MVector (PrimState m) a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector (PrimState m) a
lzLst :: MVector (PrimState m) f
..} Int
l0 a -> m Bool
g = do
  Bool
b <- a -> m Bool
g a
forall a. Monoid a => a
mempty
  let !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert Bool
b [Char]
"AtCoder.LazySegTree.maxRightM: `g mempty` must return `False`"
  if Int
l0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
nLst
    then Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
nLst
    else do
      let l :: Int
l = Int
l0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
      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
$ [Int] -> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST (PrimState m) ()) -> ST (PrimState m) ())
-> (Int -> ST (PrimState m) ()) -> ST (PrimState m) ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
        LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree (PrimState m) f a
self (Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i)
      Int -> a -> m Int
inner Int
l a
forall a. Monoid a => a
mempty
  where
    -- NOTE: Not ordinary bounds check!
    !()
_ = HasCallStack => Bool -> [Char] -> ()
Bool -> [Char] -> ()
ACIA.runtimeAssert (Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l0 Bool -> Bool -> Bool
&& Int
l0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
nLst) ([Char] -> ()) -> [Char] -> ()
forall a b. (a -> b) -> a -> b
$ [Char]
"AtCoder.LazySegTree.maxRightM: given invalid `left` index `" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
l0 [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"` over length `" [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ Int -> [Char]
forall a. Show a => a -> [Char]
show Int
nLst [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ [Char]
"`"
    inner :: Int -> a -> m Int
inner Int
l !a
sm = do
      let l' :: Int
l' = Int -> Int
chooseBit Int
l
      !a
sm' <- 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
sm <>) (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
dLst Int
l'
      Bool
b <- a -> m Bool
g a
sm'
      if Bool -> Bool
not Bool
b
        then do
          Int -> a -> m Int
inner2 Int
l' a
sm
        else do
          let l'' :: Int
l'' = Int
l' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
          if (Int
l'' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (-Int
l'')) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
l''
            then Int -> a -> m Int
inner Int
l'' a
sm'
            else Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Int
nLst
    chooseBit :: Int -> Int
    chooseBit :: Int -> Int
chooseBit Int
l
      | Int -> Bool
forall a. Integral a => a -> Bool
even Int
l = Int -> Int
chooseBit (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
1
      | Bool
otherwise = Int
l
    inner2 :: Int -> a -> m Int
inner2 Int
l !a
sm
      | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
sizeLst = do
          let l' :: Int
l' = Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
l
          a
sm' <- 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
$ do
            LazySegTree (PrimState m) f a -> Int -> ST (PrimState m) ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree (PrimState m) f a
self Int
l
            (a
sm <>) (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
dLst Int
l'
          Bool
b <- a -> m Bool
g a
sm'
          if Bool
b
            then Int -> a -> m Int
inner2 (Int
l' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) a
sm'
            else Int -> a -> m Int
inner2 Int
l' a
sm
      | Bool
otherwise = Int -> m Int
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$ Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
sizeLst

-- | \(O(n)\) Yields an immutable copy of the mutable vector.
--
-- @since 1.0.0.0
{-# INLINE freeze #-}
freeze :: (PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m (VU.Vector a)
freeze :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree (PrimState m) f a -> m (Vector a)
freeze = ST (PrimState m) (Vector a) -> m (Vector a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector a) -> m (Vector a))
-> (LazySegTree (PrimState m) f a -> ST (PrimState m) (Vector a))
-> LazySegTree (PrimState m) f a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LazySegTree (PrimState m) f a -> ST (PrimState m) (Vector a)
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> ST s (Vector a)
freezeST

-- | \(O(n)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable
-- vector may not be used after this operation.
--
-- @since 1.0.0.0
{-# INLINE unsafeFreeze #-}
unsafeFreeze :: (PrimMonad m, SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree (PrimState m) f a -> m (VU.Vector a)
unsafeFreeze :: forall (m :: * -> *) f a.
(PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree (PrimState m) f a -> m (Vector a)
unsafeFreeze = ST (PrimState m) (Vector a) -> m (Vector a)
forall (m :: * -> *) a. PrimMonad m => ST (PrimState m) a -> m a
stToPrim (ST (PrimState m) (Vector a) -> m (Vector a))
-> (LazySegTree (PrimState m) f a -> ST (PrimState m) (Vector a))
-> LazySegTree (PrimState m) f a
-> m (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LazySegTree (PrimState m) f a -> ST (PrimState m) (Vector a)
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> ST s (Vector a)
unsafeFreezeST

-- NOTE (perf): these functions have to be inlined after all:

-- -------------------------------------------------------------------------------------------------
-- Internal
-- -------------------------------------------------------------------------------------------------

{-# INLINEABLE buildST #-}
buildST :: (Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => VU.Vector a -> ST s (LazySegTree s f a)
buildST :: forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
Vector a -> ST s (LazySegTree s f a)
buildST Vector a
vs = do
  let nLst :: Int
nLst = Vector a -> Int
forall a. Unbox a => Vector a -> Int
VU.length Vector a
vs
  let sizeLst :: Int
sizeLst = Int -> Int
ACIBIT.bitCeil Int
nLst
  let logLst :: Int
logLst = Int -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Int
sizeLst
  MVector s a
dLst <- Int -> a -> ST s (MVector (PrimState (ST s)) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
sizeLst) a
forall a. Monoid a => a
mempty
  MVector s f
lzLst <- Int -> f -> ST s (MVector (PrimState (ST s)) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
VUM.replicate Int
sizeLst f
forall a. Monoid a => a
mempty
  Vector a -> (Int -> a -> ST s ()) -> ST s ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (Int -> a -> m b) -> m ()
VU.iforM_ Vector a
vs ((Int -> a -> ST s ()) -> ST s ())
-> (Int -> a -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i a
v -> 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
dLst (Int
sizeLst Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i) a
v
  let segtree :: LazySegTree s f a
segtree = LazySegTree {Int
MVector s f
MVector s a
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..}
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
sizeLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1, Int
sizeLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
segtree Int
i
  LazySegTree s f a -> ST s (LazySegTree s f a)
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure LazySegTree s f a
segtree

{-# INLINEABLE writeST #-}
writeST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> a -> ST s ()
writeST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> a -> ST s ()
writeST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
p a
x = do
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  MVector (PrimState (ST s)) a -> Int -> a -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m ()
VGM.unsafeWrite MVector s a
MVector (PrimState (ST s)) a
dLst Int
p' a
x
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i

{-# INLINEABLE modifyST #-}
modifyST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> (a -> a) -> Int -> ST s ()
modifyST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> (a -> a) -> Int -> ST s ()
modifyST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} a -> a
f Int
p = do
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  MVector (PrimState (ST s)) a -> (a -> a) -> Int -> ST s ()
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> (a -> a) -> Int -> m ()
VGM.unsafeModify MVector s a
MVector (PrimState (ST s)) a
dLst a -> a
f Int
p'
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i

{-# INLINEABLE exchangeST #-}
exchangeST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> a -> ST s a
exchangeST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> a -> ST s a
exchangeST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
p a
x = do
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  a
res <- MVector (PrimState (ST s)) a -> Int -> a -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> a -> m a
VGM.unsafeExchange MVector s a
MVector (PrimState (ST s)) a
dLst Int
p' a
x
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  a -> ST s a
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
res

{-# INLINEABLE readST #-}
readST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> ST s a
readST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s a
readST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
p = do
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  MVector (PrimState (ST s)) a -> Int -> ST s a
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m a
VGM.unsafeRead MVector s a
MVector (PrimState (ST s)) a
dLst Int
p'

{-# INLINEABLE applyAtST #-}
applyAtST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> f -> ST s ()
applyAtST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
applyAtST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
p f
f = do
  let p' :: Int
p' = Int
p Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  -- propagate
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  -- FIXME: length should be always `1`
  let !len :: Int
len = Int -> Int
forall a. Bits a => Int -> a
bit (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$! Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Int
p')
  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
dLst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f) Int
p'
  -- evaluate
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
p' Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i

{-# INLINEABLE applyInST #-}
applyInST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> Int -> f -> ST s ()
applyInST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> Int -> f -> ST s ()
applyInST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
l0 Int
r0 f
f
  | Int
l0 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
r0 = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
  | Bool
otherwise = do
      let l :: Int
l = Int
l0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
      let r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
      -- propagate
      [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
l) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i)
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
r Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
r) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self ((Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i)
      Int -> Int -> ST s ()
inner Int
l (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      -- evaluate
      [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
logLst] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
l) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self (Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i)
        Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
r Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
r) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree s f a
self ((Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i)
  where
    -- NOTE: we're using inclusive range [l, r] for simplicity
    inner :: Int -> Int -> ST s ()
inner Int
l Int
r
      | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
r = () -> ST s ()
forall a. a -> ST s a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      | Bool
otherwise = do
          Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
l Int
0) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
            LazySegTree s f a -> Int -> f -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
allApplyST LazySegTree s f a
self Int
l f
f
          Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
r Int
0) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
            LazySegTree s f a -> Int -> f -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
allApplyST LazySegTree s f a
self Int
r f
f
          Int -> Int -> ST s ()
inner ((Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
1) ((Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
1)

-- | Internal implementation of `prod`.
{-# INLINEABLE unsafeProdST #-}
unsafeProdST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> Int -> ST s a
unsafeProdST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> Int -> ST s a
unsafeProdST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
l0 Int
r0 = do
  let l :: Int
l = Int
l0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  let r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizeLst
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
logLst, Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 .. Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
l) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
    Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (((Int
r Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.<<. Int
i) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
r) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
i
  Int -> Int -> a -> a -> ST s a
forall {f :: * -> *}.
(PrimState f ~ s, PrimMonad f) =>
Int -> Int -> a -> a -> f a
inner Int
l (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a
forall a. Monoid a => a
mempty a
forall a. Monoid a => a
mempty
  where
    -- NOTE: we're using inclusive range [l, r] for simplicity
    inner :: Int -> Int -> a -> a -> f a
inner Int
l Int
r !a
smL !a
smR
      | Int
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
r = a -> f a
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> f a) -> a -> f a
forall a b. (a -> b) -> a -> b
$! a
smL a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
smR
      | Bool
otherwise = do
          !a
smL' <-
            if Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
l Int
0
              then (a
smL <>) (a -> a) -> f a -> f a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState f) a -> Int -> f 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 f) a
dLst Int
l
              else a -> f a
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
smL
          !a
smR' <-
            if Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
r Int
0
              then (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
smR) (a -> a) -> f a -> f a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState f) a -> Int -> f 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 f) a
dLst Int
r
              else a -> f a
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
smR
          Int -> Int -> a -> a -> f a
inner ((Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
1) ((Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
.>>. Int
1) a
smL' a
smR'

{-# INLINEABLE freezeST #-}
freezeST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> ST s (VU.Vector a)
freezeST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> ST s (Vector a)
freezeST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} = do
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
sizeLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self Int
i
  MVector s a -> ST s (Vector a)
MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.freeze (MVector s a -> ST s (Vector a))
-> (MVector s a -> MVector s a) -> MVector s a -> ST s (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
nLst (MVector s a -> ST s (Vector a)) -> MVector s a -> ST s (Vector a)
forall a b. (a -> b) -> a -> b
$ Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.drop Int
sizeLst MVector s a
dLst

{-# INLINEABLE unsafeFreezeST #-}
unsafeFreezeST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> ST s (VU.Vector a)
unsafeFreezeST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> ST s (Vector a)
unsafeFreezeST self :: LazySegTree s f a
self@LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} = do
  -- push all (we _could_ skip some elements)
  [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (f :: * -> *) a b.
(Foldable t, Applicative f) =>
t a -> (a -> f b) -> f ()
for_ [Int
1 .. Int
sizeLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    LazySegTree s f a -> Int -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST LazySegTree s f a
self Int
i
  MVector s a -> ST s (Vector a)
MVector (PrimState (ST s)) a -> ST s (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
VU.unsafeFreeze (MVector s a -> ST s (Vector a))
-> (MVector s a -> MVector s a) -> MVector s a -> ST s (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.take Int
nLst (MVector s a -> ST s (Vector a)) -> MVector s a -> ST s (Vector a)
forall a b. (a -> b) -> a -> b
$ Int -> MVector s a -> MVector s a
forall a s. Unbox a => Int -> MVector s a -> MVector s a
VUM.drop Int
sizeLst MVector s a
dLst

-- | \(O(1)\)
{-# INLINE updateST #-}
updateST :: (Monoid f, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> ST s ()
updateST :: forall f a s.
(Monoid f, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
updateST LazySegTree {MVector s a
dLst :: forall s f a. LazySegTree s f a -> MVector s a
dLst :: MVector s a
dLst} Int
k = do
  a
opL <- 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
dLst (Int -> ST s a) -> Int -> ST s a
forall a b. (a -> b) -> a -> b
$ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k
  a
opR <- 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
dLst (Int -> ST s a) -> Int -> ST s a
forall a b. (a -> b) -> a -> b
$ Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
  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
dLst Int
k (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a
opL a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
opR

-- | \(O(1)\)
{-# INLINE allApplyST #-}
allApplyST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> f -> ST s ()
allApplyST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
allApplyST LazySegTree {Int
MVector s f
MVector s a
nLst :: forall s f a. LazySegTree s f a -> Int
sizeLst :: forall s f a. LazySegTree s f a -> Int
logLst :: forall s f a. LazySegTree s f a -> Int
dLst :: forall s f a. LazySegTree s f a -> MVector s a
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
nLst :: Int
sizeLst :: Int
logLst :: Int
dLst :: MVector s a
lzLst :: MVector s f
..} Int
k f
f = do
  let !len :: Int
len = Int -> Int
forall a. Bits a => Int -> a
bit (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$! Int
logLst Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Int
k)
  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
dLst (Int -> f -> a -> a
forall f a. SegAct f a => Int -> f -> a -> a
segActWithLength Int
len f
f) Int
k
  Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
sizeLst) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
    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
lzLst (f
f <>) Int
k

-- | \(O(1)\)
{-# INLINE pushST #-}
pushST :: (SegAct f a, VU.Unbox f, Monoid a, VU.Unbox a) => LazySegTree s f a -> Int -> ST s ()
pushST :: forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> ST s ()
pushST self :: LazySegTree s f a
self@LazySegTree {MVector s f
lzLst :: forall s f a. LazySegTree s f a -> MVector s f
lzLst :: MVector s f
lzLst} Int
k = do
  f
lzK <- 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
lzLst Int
k
  LazySegTree s f a -> Int -> f -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
allApplyST LazySegTree s f a
self (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k) f
lzK
  LazySegTree s f a -> Int -> f -> ST s ()
forall f a s.
(SegAct f a, Unbox f, Monoid a, Unbox a) =>
LazySegTree s f a -> Int -> f -> ST s ()
allApplyST LazySegTree s f a
self (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) f
lzK
  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
lzLst Int
k f
forall a. Monoid a => a
mempty