{-# LANGUAGE RecordWildCards #-}

module Data.SegTree.Dual 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

import Data.Monoid.Action (MonoidAction (..))

-- | @a@ need not to be Semigroup
data DualSegTree s f a = DualSegTree
  { forall s f a. DualSegTree s f a -> MVector s f
dualSegTreeDST :: !(UM.MVector s f)
  , forall s f a. DualSegTree s f a -> MVector s a
primalsDST :: !(UM.MVector s a)
  , forall s f a. DualSegTree s f a -> Int
dualSizeDST :: !Int
  -- ^ @2^n@
  , forall s f a. DualSegTree s f a -> Int
primalSizeDST :: !Int
  , forall s f a. DualSegTree s f a -> Int
heightDST :: !Int
  -- ^ @2 ^ height == sizeDual@
  }

-- | /O(n)/
buildDualSegTree ::
  (Monoid f, U.Unbox f, U.Unbox a, PrimMonad m) =>
  U.Vector a ->
  m (DualSegTree (PrimState m) f a)
buildDualSegTree :: forall f a (m :: * -> *).
(Monoid f, Unbox f, Unbox a, PrimMonad m) =>
Vector a -> m (DualSegTree (PrimState m) f a)
buildDualSegTree Vector a
xs = do
  MVector (PrimState m) f
dualSegTreeDST <- Int -> f -> m (MVector (PrimState m) f)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UM.replicate Int
dualSizeDST f
forall a. Monoid a => a
mempty
  MVector (PrimState m) a
primalsDST <- Vector a -> m (MVector (PrimState m) a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
Vector a -> m (MVector (PrimState m) a)
U.thaw Vector a
xs
  DualSegTree (PrimState m) f a -> m (DualSegTree (PrimState m) f a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (DualSegTree (PrimState m) f a
 -> m (DualSegTree (PrimState m) f a))
-> DualSegTree (PrimState m) f a
-> m (DualSegTree (PrimState m) f a)
forall a b. (a -> b) -> a -> b
$ DualSegTree{Int
MVector (PrimState m) f
MVector (PrimState m) a
dualSegTreeDST :: MVector (PrimState m) f
primalsDST :: MVector (PrimState m) a
dualSizeDST :: Int
primalSizeDST :: Int
heightDST :: Int
dualSegTreeDST :: MVector (PrimState m) f
dualSizeDST :: Int
primalsDST :: MVector (PrimState m) a
primalSizeDST :: Int
heightDST :: Int
..}
  where
    !dualSizeDST :: Int
dualSizeDST = 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
    primalSizeDST :: Int
primalSizeDST = Vector a -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector a
xs
    heightDST :: Int
heightDST = Int -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Int
dualSizeDST
{-# INLINE buildDualSegTree #-}

-- | /O(n)/
freezeDualSegTree ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  m (U.Vector a)
freezeDualSegTree :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> m (Vector a)
freezeDualSegTree
  DualSegTree
    { dualSegTreeDST :: forall s f a. DualSegTree s f a -> MVector s f
dualSegTreeDST = MVector (PrimState m) f
dseg
    , primalsDST :: forall s f a. DualSegTree s f a -> MVector s a
primalsDST = MVector (PrimState m) a
pseg
    , dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    } = do
    Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep1 ((Int
dsize 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 -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
      f
fi <- MVector (PrimState m) f -> Int -> m f
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead MVector (PrimState m) f
dseg Int
i
      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 MVector (PrimState m) f
dseg (f
fi <>) (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
i)
      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 MVector (PrimState m) f
dseg (f
fi <>) (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

    ((Int -> a -> m ()) -> MVector (PrimState m) a -> m ())
-> MVector (PrimState m) a -> (Int -> a -> m ()) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> a -> m ()) -> MVector (PrimState m) a -> m ()
forall (m :: * -> *) a b.
(PrimMonad m, Unbox a) =>
(Int -> a -> m b) -> MVector (PrimState m) a -> m ()
UM.imapM_ MVector (PrimState m) a
pseg ((Int -> a -> m ()) -> m ()) -> (Int -> a -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i a
x -> do
      f
f <- MVector (PrimState m) f -> Int -> m f
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead MVector (PrimState m) f
dseg (Int -> m f) -> Int -> m f
forall a b. (a -> b) -> a -> b
$ (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
dsize) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. Int
1
      MVector (PrimState m) a -> Int -> a -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite MVector (PrimState m) a
pseg Int
i (f -> a -> a
forall f a. MonoidAction f a => f -> a -> a
mact f
f a
x)

    MVector (PrimState m) f -> f -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> a -> m ()
UM.set MVector (PrimState m) f
dseg f
forall a. Monoid a => a
mempty
    MVector (PrimState m) a -> m (Vector a)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.freeze MVector (PrimState m) a
pseg
{-# INLINE freezeDualSegTree #-}

-- | /O(log n)/
readDualSegTree ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  m a
readDualSegTree :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m a
readDualSegTree
  seg :: DualSegTree (PrimState m) f a
seg@DualSegTree
    { primalsDST :: forall s f a. DualSegTree s f a -> MVector s a
primalsDST = MVector (PrimState m) a
pseg
    , dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    , heightDST :: forall s f a. DualSegTree s f a -> Int
heightDST = Int
height
    }
  Int
k0 = do
    let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
dsize
    Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 Int
height ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
      DualSegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree DualSegTree (PrimState m) f a
seg (Int
k Int -> Int -> Int
forall a. Bits a => a -> Int -> a
!>>. 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 MVector (PrimState m) a
pseg Int
k0
{-# INLINE readDualSegTree #-}

-- | /O(log n)/
writeDualSegTree ::
  (MonoidAction f a, U.Unbox a, U.Unbox f, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  a ->
  m ()
writeDualSegTree :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox a, Unbox f, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> a -> m ()
writeDualSegTree
  seg :: DualSegTree (PrimState m) f a
seg@DualSegTree
    { primalsDST :: forall s f a. DualSegTree s f a -> MVector s a
primalsDST = MVector (PrimState m) a
pseg
    , dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    , heightDST :: forall s f a. DualSegTree s f a -> Int
heightDST = Int
height
    }
  Int
k0
  a
v = do
    let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
dsize
    Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 Int
height ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
      DualSegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree DualSegTree (PrimState m) f a
seg (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 MVector (PrimState m) a
pseg Int
k0 a
v
{-# INLINE writeDualSegTree #-}

-- | /O(log n)/
modifyDualSegTree ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  (a -> a) ->
  Int ->
  m ()
modifyDualSegTree :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modifyDualSegTree
  seg :: DualSegTree (PrimState m) f a
seg@DualSegTree
    { primalsDST :: forall s f a. DualSegTree s f a -> MVector s a
primalsDST = MVector (PrimState m) a
pseg
    , dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    , heightDST :: forall s f a. DualSegTree s f a -> Int
heightDST = Int
height
    }
  a -> a
f
  Int
k0 = do
    let !k :: Int
k = Int
k0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
dsize
    Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 Int
height ((Int -> m ()) -> m ()) -> (Int -> m ()) -> m ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
      DualSegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree DualSegTree (PrimState m) f a
seg (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 MVector (PrimState m) a
pseg a -> a
f Int
k0
{-# INLINE modifyDualSegTree #-}

{- | modify f k
 /O(log n)/
-}
appAt ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  f ->
  m ()
appAt :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
appAt DualSegTree (PrimState m) f a
st Int
k f
f = DualSegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
modifyDualSegTree DualSegTree (PrimState m) f a
st (f -> a -> a
forall f a. MonoidAction f a => f -> a -> a
mact f
f) Int
k
{-# INLINE appAt #-}

{- | mapM_ (modify f) [l..r)
 /O(log n)/
-}
appFromTo ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  Int ->
  f ->
  m ()
appFromTo :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> Int -> f -> m ()
appFromTo
  seg :: DualSegTree (PrimState m) f a
seg@DualSegTree
    { dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    , heightDST :: forall s f a. DualSegTree s f a -> Int
heightDST = Int
height
    }
  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
+ Int
dsize
        !r :: Int
r = Int
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
dsize
    Int -> (Int -> m ()) -> m ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 Int
height ((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
        DualSegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree DualSegTree (PrimState m) f a
seg (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
        DualSegTree (PrimState m) f a -> Int -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree DualSegTree (PrimState m) f a
seg ((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
            DualSegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
evalAt DualSegTree (PrimState m) f a
seg 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
            DualSegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
evalAt DualSegTree (PrimState m) f a
seg (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
{-# INLINE appFromTo #-}

-- | /O(1)/
evalAt ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  f ->
  m ()
evalAt :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
evalAt
  DualSegTree
    { dualSegTreeDST :: forall s f a. DualSegTree s f a -> MVector s f
dualSegTreeDST = MVector (PrimState m) f
dseg
    , primalsDST :: forall s f a. DualSegTree s f a -> MVector s a
primalsDST = MVector (PrimState m) a
pseg
    , dualSizeDST :: forall s f a. DualSegTree s f a -> Int
dualSizeDST = Int
dsize
    , primalSizeDST :: forall s f a. DualSegTree s f a -> Int
primalSizeDST = Int
psize
    }
  Int
k
  f
f = do
    if Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
dsize
      then 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 MVector (PrimState m) f
dseg (f
f <>) Int
k
      else do
        let !k' :: Int
k' = Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
dsize
        Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
psize) (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ 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 MVector (PrimState m) a
pseg (f -> a -> a
forall f a. MonoidAction f a => f -> a -> a
mact f
f) Int
k'
{-# INLINE evalAt #-}

-- | /O(1)/
pushSegTree ::
  (MonoidAction f a, U.Unbox f, U.Unbox a, PrimMonad m) =>
  DualSegTree (PrimState m) f a ->
  Int ->
  m ()
pushSegTree :: forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> m ()
pushSegTree seg :: DualSegTree (PrimState m) f a
seg@DualSegTree{dualSegTreeDST :: forall s f a. DualSegTree s f a -> MVector s f
dualSegTreeDST = MVector (PrimState m) f
dseg} 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 MVector (PrimState m) f
dseg 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 MVector (PrimState m) f
dseg Int
k f
forall a. Monoid a => a
mempty
  DualSegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
evalAt DualSegTree (PrimState m) f a
seg (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
k) f
fk
  DualSegTree (PrimState m) f a -> Int -> f -> m ()
forall f a (m :: * -> *).
(MonoidAction f a, Unbox f, Unbox a, PrimMonad m) =>
DualSegTree (PrimState m) f a -> Int -> f -> m ()
evalAt DualSegTree (PrimState m) f a
seg (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 #-}

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