Дерево Отрезков

Ну понятно, что задача в том - чтобы посчитать высоту дамбы в каждой точке X - потому что тогда легко будет узнать и её объёмы на всех подотрезках (чтобы быстро отвечать на запрос объёма на подотрезке, запомним объёмы на всех отрезках вида [0;i]).

Как посчитать эти высоты? Ну L небольшое, поэтому это можно делать достаточно прямолинейно, итерируясь по точкам X=0..L и поддерживая два множества: в первом у нас будут лежать пирамиды, крыши которых сейчас идут вверх (возрастают), во втором - пирамиды, крыши которых идут вниз (убывают). Изначально оба множества пустые, а когда мы переходим к очередному X, у нас могли:
0) высоты всех пирамид в первом множестве увеличились на 1, во втором - уменьшились;
а) появиться новые пирамиды - мы их добавляем в первое множество с высотой 0;
б) исчезнуть старые пирамиды - мы их удаляем из второго множества;
в) сменить тип пирамиды с возрастающей на убывающую - мы переносим их из первого множества во второе.
Все эти преобразования можно делать втупую, просто обрабатывая все пирамиды, у которых что-то меняется при данном X.

А высотой дамбы в текущей точке X будет просто максимум из максимумов в первом и втором множествах.

Итого - под множествами легко угадывается дерево отрезков для максимума.