blob: 40ec517556fe38ea6a3f847e835b8d00b53134f9 (
plain) (
tree)
|
|
module Algo.Leaffix where
import Data.Vector.Unboxed as V
leaffix :: (Vector Int, Vector Int) -> Vector Int
{-# NOINLINE leaffix #-}
leaffix (ls,rs)
= leaffix (V.replicate (V.length ls) 1) ls rs
where
leaffix xs ls rs
= let zs = V.replicate (V.length ls * 2) 0
vs = V.update_ zs ls xs
sums = V.prescanl' (+) 0 vs
in
V.zipWith (-) (V.backpermute sums ls) (V.backpermute sums rs)
|