module Data.SegTree where

import Control.Monad
import Control.Monad.Primitive
import Data.Bits
import Data.Function
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

import My.Prelude (rep1, rev1, unsafeShiftRL)

{- | * @sendo@ is a monoid homomorphism (left monoid action)
   * @sendo f@ is a semigroup endomorphism
-}
class (Monoid f, Semigroup s) => AsSemigroupEndo f s where
  sendo :: f -> (s -> s)

data SegTree s f a = SegTree
  { forall s f a. SegTree s f a -> MVector s a
getSegTree :: !(UM.MVector s a)
  , forall s f a. SegTree s f a -> MVector s f
getDualSegTree :: !(UM.MVector s f)
  , forall s f a. SegTree s f a -> Int
sizeSegTree :: !Int
  , forall s f a. SegTree s f a -> Int
heightSegTree :: !Int
  }

newSegTree ::
  (Monoid f, U.Unbox f, Monoid a, U.Unbox a, PrimMonad m) =>
  Int ->
  m (SegTree (PrimState m) f a)
newSegTree :: forall f a (m :: * -> *).
(Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) =>
Int -> m (SegTree (PrimState m) f a)
newSegTree Int
n0 = do
  MVector (PrimState m) a
seg <- Int -> a -> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UM.replicate (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n) a
forall a. Monoid a => a
mempty
  MVector (PrimState m) f
dseg <- Int -> f -> m (MVector (PrimState m) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UM.replicate Int
n f
forall a. Monoid a => a
mempty
  SegTree (PrimState m) f a -> m (SegTree (PrimState m) f a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (SegTree (PrimState m) f a -> m (SegTree (PrimState m) f a))
-> SegTree (PrimState m) f a -> m (SegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ MVector (PrimState m) a
-> MVector (PrimState m) f
-> Int
-> Int
-> SegTree (PrimState m) f a
forall s f a.
MVector s a -> MVector s f -> Int -> Int -> SegTree s f a
SegTree MVector (PrimState m) a
seg MVector (PrimState m) f
dseg Int
n (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Int
n)
  where
    !n :: Int
n = Int -> Int
extendToPowerOfTwo Int
n0

-- | /O(n)/
buildSegTree ::
  (Monoid f, U.Unbox f, Monoid a, U.Unbox a, PrimMonad m) =>
  U.Vector a ->
  m (SegTree (PrimState m) f a)
buildSegTree :: forall f a (m :: * -> *).
(Monoid f, Unbox f, Monoid a, Unbox a, PrimMonad m) =>
Vector a -> m (SegTree (PrimState m) f a)
buildSegTree Vector a
xs = do
  MVector (PrimState m) a
seg <- Int -> a -> m (MVector (PrimState m) a)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UM.replicate (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n) a
forall a. Monoid a => a
mempty
  MVector (PrimState m) f
dseg <- Int -> f -> m (MVector (PrimState m) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UM.replicate Int
n f
forall a. Monoid a => a
mempty
  MVector (PrimState m) a -> Vector a -> m ()
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> Vector a -> m ()
U.unsafeCopy (Int -> Int -> MVector (PrimState m) a -> MVector (PrimState m) a
forall a s. Unbox a => Int -> Int -> MVector s a -> MVector s a
UM.unsafeSlice Int
n (Vector a -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector a
xs) MVector (PrimState m) a
seg) Vector a
xs
  let st :: SegTree (PrimState m) f a
st = MVector (PrimState m) a
-> MVector (PrimState m) f
-> Int
-> Int
-> SegTree (PrimState m) f a
forall s f a.
MVector s a -> MVector s f -> Int -> Int -> SegTree s f a
SegTree MVector (PrimState m) a
seg MVector (PrimState m) f
dseg Int
n (Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Int
n)
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st Int
i
  SegTree (PrimState m) f a -> m (SegTree (PrimState m) f a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return SegTree (PrimState m) f a
st
  where
    !n :: Int
n = Int -> Int
extendToPowerOfTwo (Int -> Int) -> Int -> Int
forall a b. (a -> b) -> a -> b
$ Vector a -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector a
xs

-- | /O(log n)/
readSegTree ::
  (AsSemigroupEndo f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  m a
readSegTree :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m a
readSegTree SegTree (PrimState m) f a
st Int
k0 = do
  let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR Int
k Int
i)
  MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
k
{-# INLINE readSegTree #-}

-- | /O(log n)/
writeSegTree ::
  (AsSemigroupEndo f a, Semigroup a, U.Unbox a, U.Unbox f, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  a ->
  m ()
writeSegTree :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Semigroup a, Unbox a, Unbox f,
 PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> a -> m ()
writeSegTree SegTree (PrimState m) f a
st Int
k0 a
v = do
  let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int
k Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
  MVector (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
k a
v
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st (Int
k Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
{-# INLINE writeSegTree #-}

-- | /O(log n)/
modifySegTree ::
  (AsSemigroupEndo f a, Semigroup a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  (a -> a) ->
  Int ->
  m ()
modifySegTree :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a,
 PrimMonad m) =>
SegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modifySegTree SegTree (PrimState m) f a
st a -> a
f Int
k0 = do
  let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int
k Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
  MVector (PrimState m) a -> (a -> a) -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
UM.unsafeModify (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) a -> a
f Int
k
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st (Int
k Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
{-# INLINE modifySegTree #-}

{- | mappend [l..r)
 /O(log n)/
-}
mappendFromTo ::
  (AsSemigroupEndo f a, Monoid a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  Int ->
  m a
mappendFromTo :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> Int -> m a
mappendFromTo SegTree (PrimState m) f a
st Int
l0 Int
r0 = do
  let !l :: Int
l = Int
l0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
      !r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR Int
l Int
i)
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR Int
r Int
i)

  ((a -> a -> Int -> Int -> m a) -> a -> a -> Int -> Int -> m a)
-> a -> a -> Int -> Int -> m a
forall a. (a -> a) -> a
fix
    ( \a -> a -> Int -> Int -> m a
loop !a
accL !a
accR !Int
l' !Int
r' -> do
        if Int
l' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r'
          then do
            !a
accL' <-
              if Int
l' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
                then (a
accL <>) (a -> a) -> m a -> m a
forall (m :: * -> *) a b. Monad m => (a -> b) -> m a -> m b
<$!> MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
l'
                else a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
accL
            !a
accR' <-
              if Int
r' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1
                then (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
accR) (a -> a) -> m a -> m a
forall (m :: * -> *) a b. Monad m => (a -> b) -> m a -> m b
<$!> MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) (Int
r' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
                else a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
accR
            a -> a -> Int -> Int -> m a
loop
              a
accL'
              a
accR'
              ((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. Bits a => a -> Int -> a
!>>. Int
1)
          else a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a -> m a) -> a -> m a
forall a b. (a -> b) -> a -> b
$! a
accL a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
accR
    )
    a
forall a. Monoid a => a
mempty
    a
forall a. Monoid a => a
mempty
    Int
l
    Int
r
{-# INLINE mappendFromTo #-}

{- | mappend [0..k)
 /O(log n)/
-}
mappendTo ::
  (AsSemigroupEndo f a, Monoid a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  m a
mappendTo :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m a
mappendTo SegTree (PrimState m) f a
st = SegTree (PrimState m) f a -> Int -> Int -> m a
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> Int -> m a
mappendFromTo SegTree (PrimState m) f a
st Int
0
{-# INLINE mappendTo #-}

{- | mappend [0..n)
 /O(1)/
-}
mappendAll :: (U.Unbox a, PrimMonad m) => SegTree (PrimState m) f a -> m a
mappendAll :: forall a (m :: * -> *) f.
(Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> m a
mappendAll SegTree (PrimState m) f a
st = MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
1
{-# INLINE mappendAll #-}

{- | modify f k
 /O(log n)/
-}
appAt ::
  (AsSemigroupEndo f a, Semigroup a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  f ->
  m ()
appAt :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a,
 PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
appAt SegTree (PrimState m) f a
st Int
k f
f = SegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a,
 PrimMonad m) =>
SegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modifySegTree SegTree (PrimState m) f a
st (f -> a -> a
forall f s. AsSemigroupEndo f s => f -> s -> s
sendo f
f) Int
k
{-# INLINE appAt #-}

{- | mapM_ (modify f) [l..r)
 /O(log n)/
-}
appFromTo ::
  (AsSemigroupEndo f a, Semigroup a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  Int ->
  f ->
  m ()
appFromTo :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Semigroup a, Unbox f, Unbox a,
 PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> Int -> f -> m ()
appFromTo SegTree (PrimState m) f a
st Int
l0 Int
r0 f
f = Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
l0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r0) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
  let !l :: Int
l = Int
l0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
      !r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st (Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st ((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 -> m ()) -> Int -> Int -> m ()) -> Int -> Int -> m ()
forall a. (a -> a) -> a
fix
    ( \Int -> Int -> m ()
loop !Int
l' !Int
r' -> Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
l' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r') (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
        Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
l' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
          SegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
evalAt SegTree (PrimState m) f a
st Int
l' f
f
        Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
r' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
          SegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
evalAt SegTree (PrimState m) f a
st (Int
r' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) f
f
        Int -> Int -> m ()
loop
          ((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. Bits a => a -> Int -> a
!>>. Int
1)
    )
    Int
l
    Int
r

  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st (Int
l Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
    Bool -> m () -> m ()
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) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
      SegTree (PrimState m) f a -> Int -> m ()
forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st ((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)
{-# INLINE appFromTo #-}

-- | max r s.t. f (mappendFromTo seg l r) == True
upperBoundFrom ::
  (AsSemigroupEndo f a, Monoid a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  -- | left
  Int ->
  -- | predicate s.t. f memepty == True, monotone
  (a -> Bool) ->
  m Int
upperBoundFrom :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
upperBoundFrom SegTree (PrimState m) f a
st Int
l a -> Bool
p = do
  let !n :: Int
n = SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st ((Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
  Maybe (a, Int)
violationNode <-
    ((a -> Int -> m (Maybe (a, Int)))
 -> a -> Int -> m (Maybe (a, Int)))
-> a -> Int -> m (Maybe (a, Int))
forall a. (a -> a) -> a
fix
      ( \a -> Int -> m (Maybe (a, Int))
loopUp !a
acc !Int
cur -> do
          let rightParent :: Int
rightParent = Int
cur Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Int
cur
          !a
acc' <- (a
acc <>) (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 :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
rightParent
          if a -> Bool
p a
acc'
            then do
              let !cur' :: Int
cur' = Int
rightParent Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
              if Int
cur' Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int -> Int
forall a. Num a => a -> a
negate Int
cur' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
cur'
                then a -> Int -> m (Maybe (a, Int))
loopUp a
acc' Int
cur'
                else Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, Int)
forall a. Maybe a
Nothing
            else Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (a, Int) -> m (Maybe (a, Int)))
-> Maybe (a, Int) -> m (Maybe (a, Int))
forall a b. (a -> b) -> a -> b
$ (a, Int) -> Maybe (a, Int)
forall a. a -> Maybe a
Just (a
acc, Int
rightParent)
      )
      a
forall a. Monoid a => a
mempty
      (Int
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n)
  case Maybe (a, Int)
violationNode of
    Maybe (a, Int)
Nothing -> Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
n
    Just (!a
acc0, !Int
cur0) -> do
      ((a -> Int -> m Int) -> a -> Int -> m Int) -> a -> Int -> m Int
forall a. (a -> a) -> a
fix
        ( \a -> Int -> m Int
loopDown !a
acc !Int
cur -> do
            if Int
cur Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
              then do
                SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st Int
cur
                let !leftChild :: Int
leftChild = Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
cur
                !a
acc' <- (a
acc <>) (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 :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
leftChild
                if a -> Bool
p a
acc'
                  then a -> Int -> m Int
loopDown a
acc' (Int
leftChild Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
                  else a -> Int -> m Int
loopDown a
acc Int
leftChild
              else Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$! Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n
        )
        a
acc0
        Int
cur0
{-# INLINE upperBoundFrom #-}

-- | min l s.t. f (mappendFromTo seg l r) == True
lowerBoundTo ::
  (AsSemigroupEndo f a, Monoid a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  -- | right
  Int ->
  -- | predicate s.t. f memepty == True, monotone
  (a -> Bool) ->
  m Int
lowerBoundTo :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Monoid a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
lowerBoundTo SegTree (PrimState m) f a
st Int
r a -> Bool
p = do
  let !n :: Int
n = SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st
  Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 (SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
heightSegTree SegTree (PrimState m) f a
st) ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
    SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st ((Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
i)
  Maybe (a, Int)
violationNode <-
    ((a -> Int -> m (Maybe (a, Int)))
 -> a -> Int -> m (Maybe (a, Int)))
-> a -> Int -> m (Maybe (a, Int))
forall a. (a -> a) -> a
fix
      ( \a -> Int -> m (Maybe (a, Int))
loopUp !a
acc !Int
cur -> do
          let leftParent :: Int
leftParent =
                case Int
cur Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros (Int -> Int
forall a. Bits a => a -> a
complement Int
cur) of
                  Int
0 -> Int
1 -- cur: 2 ^ n
                  Int
v -> Int
v
          !a
acc' <- (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
acc) (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 :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
leftParent
          if a -> Bool
p a
acc'
            then do
              if Int
leftParent Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int -> Int
forall a. Num a => a -> a
negate Int
leftParent Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
leftParent
                then a -> Int -> m (Maybe (a, Int))
loopUp a
acc' (Int
leftParent Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
                else Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe (a, Int)
forall a. Maybe a
Nothing
            else Maybe (a, Int) -> m (Maybe (a, Int))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe (a, Int) -> m (Maybe (a, Int)))
-> Maybe (a, Int) -> m (Maybe (a, Int))
forall a b. (a -> b) -> a -> b
$ (a, Int) -> Maybe (a, Int)
forall a. a -> Maybe a
Just (a
acc, Int
leftParent)
      )
      a
forall a. Monoid a => a
mempty
      (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
n)
  case Maybe (a, Int)
violationNode of
    Maybe (a, Int)
Nothing -> Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
0
    Just (!a
acc0, !Int
cur0) ->
      ((a -> Int -> m Int) -> a -> Int -> m Int) -> a -> Int -> m Int
forall a. (a -> a) -> a
fix
        ( \a -> Int -> m Int
loopDown !a
acc !Int
cur -> do
            if Int
cur Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
              then do
                SegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st Int
cur
                let !rightChild :: Int
rightChild = Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
                !a
acc' <- (a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
acc) (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 :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
rightChild
                if a -> Bool
p a
acc'
                  then a -> Int -> m Int
loopDown a
acc' (Int
rightChild Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
                  else a -> Int -> m Int
loopDown a
acc Int
rightChild
              else Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int -> m Int) -> Int -> m Int
forall a b. (a -> b) -> a -> b
$! Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n
        )
        a
acc0
        Int
cur0
{-# INLINE lowerBoundTo #-}

-- | /O(1)/
evalAt ::
  (AsSemigroupEndo f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  f ->
  m ()
evalAt :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
evalAt SegTree (PrimState m) f a
st Int
k f
f = do
  MVector (PrimState m) a -> (a -> a) -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
UM.unsafeModify (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) (f -> a -> a
forall f s. AsSemigroupEndo f s => f -> s -> s
sendo f
f) Int
k
  Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< SegTree (PrimState m) f a -> Int
forall s f a. SegTree s f a -> Int
sizeSegTree SegTree (PrimState m) f a
st) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ do
    MVector (PrimState m) f -> (f -> f) -> Int -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
UM.unsafeModify (SegTree (PrimState m) f a -> MVector (PrimState m) f
forall s f a. SegTree s f a -> MVector s f
getDualSegTree SegTree (PrimState m) f a
st) (f
f <>) Int
k
{-# INLINE evalAt #-}

-- | /O(1)/
pushSegTree ::
  (AsSemigroupEndo f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  m ()
pushSegTree :: forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pushSegTree SegTree (PrimState m) f a
st Int
k = do
  f
fk <- MVector (PrimState m) f -> Int -> m f
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) f
forall s f a. SegTree s f a -> MVector s f
getDualSegTree SegTree (PrimState m) f a
st) Int
k
  MVector (PrimState m) f -> Int -> f -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite (SegTree (PrimState m) f a -> MVector (PrimState m) f
forall s f a. SegTree s f a -> MVector s f
getDualSegTree SegTree (PrimState m) f a
st) Int
k f
forall a. Monoid a => a
mempty
  SegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
evalAt SegTree (PrimState m) f a
st (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k) f
fk
  SegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(AsSemigroupEndo f a, Unbox f, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> f -> m ()
evalAt SegTree (PrimState m) f a
st (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
fk
{-# INLINE pushSegTree #-}

-- | /O(1)/
pullSegTree ::
  (Semigroup a, U.Unbox a, PrimMonad m) =>
  SegTree (PrimState m) f a ->
  Int ->
  m ()
pullSegTree :: forall a (m :: * -> *) f.
(Semigroup a, Unbox a, PrimMonad m) =>
SegTree (PrimState m) f a -> Int -> m ()
pullSegTree SegTree (PrimState m) f a
st Int
k = do
  a -> a -> a
forall a. Semigroup a => a -> a -> a
(<>)
    (a -> a -> a) -> m a -> m (a -> a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k)
    m (a -> a) -> m a -> m a
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> MVector (PrimState m) a -> Int -> m a
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) (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)
    m a -> (a -> m ()) -> m ()
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= MVector (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite (SegTree (PrimState m) f a -> MVector (PrimState m) a
forall s f a. SegTree s f a -> MVector s a
getSegTree SegTree (PrimState m) f a
st) Int
k
{-# INLINE pullSegTree #-}

extendToPowerOfTwo :: Int -> Int
extendToPowerOfTwo :: Int -> Int
extendToPowerOfTwo Int
x
  | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1 = Int -> Int -> Int
unsafeShiftRL (-Int
1) (Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
  | Bool
otherwise = Int
1