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)