{-# LANGUAGE TypeFamilies #-}
module AtCoder.Extra.Monoid.Affine1
(
Affine1 (..),
Affine1Repr,
new,
unAffine1,
ident,
zero,
act,
)
where
import AtCoder.Extra.Math qualified as ACEM
import AtCoder.LazySegTree (SegAct (..))
import Data.Coerce (coerce)
import Data.Foldable (foldl')
import Data.List.NonEmpty (NonEmpty (..))
import Data.Semigroup (Dual (..), Semigroup (..), Sum (..))
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
newtype Affine1 a = Affine1 (Affine1Repr a)
deriving newtype
(
Affine1 a -> Affine1 a -> Bool
(Affine1 a -> Affine1 a -> Bool)
-> (Affine1 a -> Affine1 a -> Bool) -> Eq (Affine1 a)
forall a. Eq a => Affine1 a -> Affine1 a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Affine1 a -> Affine1 a -> Bool
== :: Affine1 a -> Affine1 a -> Bool
$c/= :: forall a. Eq a => Affine1 a -> Affine1 a -> Bool
/= :: Affine1 a -> Affine1 a -> Bool
Eq,
Eq (Affine1 a)
Eq (Affine1 a) =>
(Affine1 a -> Affine1 a -> Ordering)
-> (Affine1 a -> Affine1 a -> Bool)
-> (Affine1 a -> Affine1 a -> Bool)
-> (Affine1 a -> Affine1 a -> Bool)
-> (Affine1 a -> Affine1 a -> Bool)
-> (Affine1 a -> Affine1 a -> Affine1 a)
-> (Affine1 a -> Affine1 a -> Affine1 a)
-> Ord (Affine1 a)
Affine1 a -> Affine1 a -> Bool
Affine1 a -> Affine1 a -> Ordering
Affine1 a -> Affine1 a -> Affine1 a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Affine1 a)
forall a. Ord a => Affine1 a -> Affine1 a -> Bool
forall a. Ord a => Affine1 a -> Affine1 a -> Ordering
forall a. Ord a => Affine1 a -> Affine1 a -> Affine1 a
$ccompare :: forall a. Ord a => Affine1 a -> Affine1 a -> Ordering
compare :: Affine1 a -> Affine1 a -> Ordering
$c< :: forall a. Ord a => Affine1 a -> Affine1 a -> Bool
< :: Affine1 a -> Affine1 a -> Bool
$c<= :: forall a. Ord a => Affine1 a -> Affine1 a -> Bool
<= :: Affine1 a -> Affine1 a -> Bool
$c> :: forall a. Ord a => Affine1 a -> Affine1 a -> Bool
> :: Affine1 a -> Affine1 a -> Bool
$c>= :: forall a. Ord a => Affine1 a -> Affine1 a -> Bool
>= :: Affine1 a -> Affine1 a -> Bool
$cmax :: forall a. Ord a => Affine1 a -> Affine1 a -> Affine1 a
max :: Affine1 a -> Affine1 a -> Affine1 a
$cmin :: forall a. Ord a => Affine1 a -> Affine1 a -> Affine1 a
min :: Affine1 a -> Affine1 a -> Affine1 a
Ord,
Int -> Affine1 a -> ShowS
[Affine1 a] -> ShowS
Affine1 a -> String
(Int -> Affine1 a -> ShowS)
-> (Affine1 a -> String)
-> ([Affine1 a] -> ShowS)
-> Show (Affine1 a)
forall a. Show a => Int -> Affine1 a -> ShowS
forall a. Show a => [Affine1 a] -> ShowS
forall a. Show a => Affine1 a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Affine1 a -> ShowS
showsPrec :: Int -> Affine1 a -> ShowS
$cshow :: forall a. Show a => Affine1 a -> String
show :: Affine1 a -> String
$cshowList :: forall a. Show a => [Affine1 a] -> ShowS
showList :: [Affine1 a] -> ShowS
Show
)
type Affine1Repr a = (a, a)
{-# INLINE new #-}
new :: a -> a -> Affine1 a
new :: forall a. a -> a -> Affine1 a
new !a
a !a
b = Affine1Repr a -> Affine1 a
forall a. Affine1Repr a -> Affine1 a
Affine1 (a
a, a
b)
{-# INLINE unAffine1 #-}
unAffine1 :: Affine1 a -> Affine1Repr a
unAffine1 :: forall a. Affine1 a -> Affine1Repr a
unAffine1 (Affine1 Affine1Repr a
a) = Affine1Repr a
a
{-# INLINE ident #-}
ident :: (Num a) => Affine1 a
ident :: forall a. Num a => Affine1 a
ident = Affine1Repr a -> Affine1 a
forall a. Affine1Repr a -> Affine1 a
Affine1 (a
1, a
0)
{-# INLINE zero #-}
zero :: (Num a) => Affine1 a
zero :: forall a. Num a => Affine1 a
zero = Affine1Repr a -> Affine1 a
forall a. Affine1Repr a -> Affine1 a
Affine1 (a
0, a
0)
{-# INLINE act #-}
act :: (Num a) => Affine1 a -> a -> a
act :: forall a. Num a => Affine1 a -> a -> a
act (Affine1 (!a
a, !a
b)) a
x = a
a a -> a -> a
forall a. Num a => a -> a -> a
* a
x a -> a -> a
forall a. Num a => a -> a -> a
+ a
b
{-# INLINE actWithLength #-}
actWithLength :: (Num a) => Int -> Affine1 a -> a -> a
actWithLength :: forall a. Num a => Int -> Affine1 a -> a -> a
actWithLength Int
len (Affine1 (!a
a, !a
b)) !a
x = a
a a -> a -> a
forall a. Num a => a -> a -> a
* a
x a -> a -> a
forall a. Num a => a -> a -> a
+ a
b a -> a -> a
forall a. Num a => a -> a -> a
* Int -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
len
instance (Num a) => Semigroup (Affine1 a) where
{-# INLINE (<>) #-}
(Affine1 (!a
a1, !a
b1)) <> :: Affine1 a -> Affine1 a -> Affine1 a
<> (Affine1 (!a
a2, !a
b2)) = (a, a) -> Affine1 a
forall a. Affine1Repr a -> Affine1 a
Affine1 (a
a', a
b')
where
!a' :: a
a' = a
a1 a -> a -> a
forall a. Num a => a -> a -> a
* a
a2
!b' :: a
b' = a
a1 a -> a -> a
forall a. Num a => a -> a -> a
* a
b2 a -> a -> a
forall a. Num a => a -> a -> a
+ a
b1
{-# INLINE sconcat #-}
sconcat :: NonEmpty (Affine1 a) -> Affine1 a
sconcat (Affine1 a
x :| [Affine1 a]
xs) = (Affine1 a -> Affine1 a -> Affine1 a)
-> Affine1 a -> [Affine1 a] -> Affine1 a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Affine1 a -> Affine1 a -> Affine1 a
forall a. Semigroup a => a -> a -> a
(<>) Affine1 a
x [Affine1 a]
xs
{-# INLINE stimes #-}
stimes :: forall b. Integral b => b -> Affine1 a -> Affine1 a
stimes b
b = (Affine1 a -> Affine1 a -> Affine1 a)
-> Int -> Affine1 a -> Affine1 a
forall a. (a -> a -> a) -> Int -> a -> a
ACEM.power Affine1 a -> Affine1 a -> Affine1 a
forall a. Semigroup a => a -> a -> a
(<>) (b -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral b
b)
instance (Num a) => Monoid (Affine1 a) where
{-# INLINE mempty #-}
mempty :: Affine1 a
mempty = Affine1Repr a -> Affine1 a
forall a. Affine1Repr a -> Affine1 a
Affine1 (a
1, a
0)
{-# INLINE mconcat #-}
mconcat :: [Affine1 a] -> Affine1 a
mconcat [] = Affine1 a
forall a. Monoid a => a
mempty
mconcat (Affine1 a
x : [Affine1 a]
xs) = (Affine1 a -> Affine1 a -> Affine1 a)
-> Affine1 a -> [Affine1 a] -> Affine1 a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Affine1 a -> Affine1 a -> Affine1 a
forall a. Semigroup a => a -> a -> a
(<>) Affine1 a
x [Affine1 a]
xs
instance (Num a) => SegAct (Affine1 a) (Sum a) where
{-# INLINE segActWithLength #-}
segActWithLength :: Int -> Affine1 a -> Sum a -> Sum a
segActWithLength !Int
len Affine1 a
f (Sum !a
x) = a -> Sum a
forall a. a -> Sum a
Sum (a -> Sum a) -> a -> Sum a
forall a b. (a -> b) -> a -> b
$! Int -> Affine1 a -> a -> a
forall a. Num a => Int -> Affine1 a -> a -> a
actWithLength Int
len Affine1 a
f a
x
instance (Num a) => SegAct (Affine1 (Sum a)) (Sum a) where
{-# INLINE segActWithLength #-}
segActWithLength :: Int -> Affine1 (Sum a) -> Sum a -> Sum a
segActWithLength = Int -> Affine1 (Sum a) -> Sum a -> Sum a
forall a. Num a => Int -> Affine1 a -> a -> a
actWithLength
instance (Num a) => SegAct (Dual (Affine1 a)) (Sum a) where
{-# INLINE segActWithLength #-}
segActWithLength :: Int -> Dual (Affine1 a) -> Sum a -> Sum a
segActWithLength !Int
len (Dual Affine1 a
f) (Sum !a
x) = a -> Sum a
forall a. a -> Sum a
Sum (a -> Sum a) -> a -> Sum a
forall a b. (a -> b) -> a -> b
$! Int -> Affine1 a -> a -> a
forall a. Num a => Int -> Affine1 a -> a -> a
actWithLength Int
len Affine1 a
f a
x
instance (Num a) => SegAct (Dual (Affine1 (Sum a))) (Sum a) where
{-# INLINE segActWithLength #-}
segActWithLength :: Int -> Dual (Affine1 (Sum a)) -> Sum a -> Sum a
segActWithLength !Int
len (Dual Affine1 (Sum a)
f) (Sum !a
x) = a -> Sum a
forall a. a -> Sum a
Sum (a -> Sum a) -> a -> Sum a
forall a b. (a -> b) -> a -> b
$! Int -> Affine1 a -> a -> a
forall a. Num a => Int -> Affine1 a -> a -> a
actWithLength Int
len (Affine1 (Sum a) -> Affine1 a
forall a b. Coercible a b => a -> b
coerce Affine1 (Sum a)
f) a
x
newtype instance VU.MVector s (Affine1 a) = MV_Affine1 (VU.MVector s (Affine1Repr a))
newtype instance VU.Vector (Affine1 a) = V_Affine1 (VU.Vector (Affine1Repr a))
deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1 a)
deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1 a)
instance (VU.Unbox a) => VU.Unbox (Affine1 a)