問題概要
$N$ 個の正整数の対 $( A_i, B_i )$ が与えられる．$\sum_{ i = 1 }^N \sum_{ j = A_i }^{ B_i } j$ を求めよ．
制約
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq B_i \leq 10^6$
解法
ぐぐったりすると分かりますが，$1$ ～ $x$ の和 $s( x )$ は $s( x ) = \frac{ x ( x + 1 ) } 2$ で求まります．これを使うと，$a$ ～ $b$ の和は $s( b ) - s( a - 1 )$ と求まります．よって，各 $i$ についてこの値を計算して足し合わせることで答えが求まります．
計算量としては $\Theta( N )$ となります．
コード
main = do n <- readInt [ as, bs ] <- transpose <$> replicateM n readIntegers print $ sum ( map s bs ) - sum ( map s ( map pred as ) ) s x = x * ( x + 1 ) `div` 2
