http://www.codevs.cn/problem/1080/

Codevs1080.hs

module Codevs1080 where

import qualified Data.Vector as V; -- Use Vector for O(1) indexing

data Cmd = Add Int Int Int -- Order Index Addition
         | Inq Int Int Int -- Order Left-Index Right-Index
         deriving Show

logSolve :: [Int] -> [Cmd] -> [Int]
logSolve srcs cmds = V.toList addSum
  where
    srcVec = V.fromList srcs
    cmdVec = V.fromList cmds
    inqVec = V.filter (\a -> case a of Inq _ _ _ -> True
                                       _ -> False) cmdVec
    addVec = V.filter (\a -> case a of Add _ _ _ -> True
                                       _ -> False) cmdVec
    rawSum = V.map (\rg@(Inq _ l r) -> (rg, V.sum (V.slice l (r - l + 1) srcVec))) inqVec
    addSum = V.map (\((Inq inqOrd l r), s) -> s + (V.sum (V.map (\(Add _ i x) -> x) (V.filter (\(Add addOrd i x) -> l <= i && i <= (r - l + 1) && addOrd < inqOrd) addVec)))) rawSum -- F**k, this time mutable programs possess better performance

testSrc :: [Int]
testSrc = [4, 5, 6, 2, 1, 3]

testCmd :: [Cmd]
testCmd = [(Add 0 2 5), (Inq 1 0 3), (Add 2 0 9), (Inq 3 1 5)]

test = logSolve testSrc testCmd