2026-11-08
Query.hs
blocks :: [[Int]]
blocks = [[5, 1, 4], [2, 8, 3], [7]]
query :: Int -> Int -> Int
query l r = left + middle + right
where
xs = concat blocks
(bl, br) = (l `div` 3, r `div` 3)
left = sum (take (3 * bl + 3 - l) (drop l xs))
middle = sum [sum (blocks !! k) | k <- [bl + 1 .. br - 1]]
right = sum (take (r - 3 * br + 1) (drop (3 * br) xs))
main :: IO ()
main = print (query 2 6, query 4 5)
これは何を出力するでしょうか?
Answer
Output
(24,24)
xs は [5,1,4,2,8,3,7] で、添字 i の要素は i `div` 3 番目の塊に入っています。query l r は添字 l から r まで(両端を含む)の和を、l から l の塊の終わりまで(left)、その間にある塊まるごと(middle)、r の塊の始まりから r まで(right)の3つに分けて足します。query 2 6 では bl が0、br が2で、left は添字2の4、middle は1番の塊の2 + 8 + 3 = 13、right は添字6の7です。合計は24で、添字2から6の和 4 + 2 + 8 + 3 + 7 と一致します。
query 4 5 では添字4と5がどちらも1番の塊に入り、bl と br がともに1になります。middle の [bl + 1 .. br - 1] は [2 .. 0] で空なので0です。ところが left は r を見ずに塊の終わりまで取るので、添字4と5の8 + 3 = 11 になります。right も l を見ずに塊の始まりから取るので、添字3から5の2 + 8 + 3 = 13 です。両端が同じ塊にあると、2つの端数が同じ区間を別々に数え、合計は本来の11ではなく24になります。
query 2 6 で3つの分け方が正しく働くのを確かめ、query 4 5 にも同じ式が当てはまると考えると、(24,11) と答えます。この分け方が正しいのは、l と r が別の塊にあり、left と right が重ならないときだけです。