最大値や最小値、累積和・累積差などで情報を保存している。
後で復元できるように一時的にメモしている。
メモの仕方の一つとして、累積がある。
累積する構造に、2次元などの拡張もある。
累積「何」かと「どこ」に当てはめるか。面白い。
N = parse(Int, readline())
A = parse.(Int, split(readline()))
D = parse(Int, readline())
LA = zeros(Int, N + 1)
RA = zeros(Int, N + 1)
for i in 1:N
LA[i+1] = max(LA[i], A[i]) #1番目が2index
end
for i in 0:N-1
RA[N-i] = max(RA[N-i+1], A[N-i]) #1番目が1index
end
for _ in 1:D
l, r = parse.(Int, split(readline()))
ans = max(RA[r+1], LA[l])
println(ans)
end
役に立つ記事
配列操作
elseif
型変換
標準出力
いもす法
minmax