A
ну реально сортировать и не требуется
Size: a a a
2020 October 07
A
мм... вместо этого надо знать порядок, во
T
Порядок чего
A
мы берем минимальную и знаем, что вершина либо слева от нее, либо справа
T
Ну грубо говоря берём 0
T
А там тоже трабл с локальными мин и макс будет
A
хм. Ну да, это примерно и есть - "построить дерево, где для каждой клетки ответ, что вершина тут"
T
Ну
А дерево строить долго
А дерево строить долго
A
в корне сунуть минимум, потом слева минимум левого и минимум правого
T
И так для каждого минимума?
A
угу, по локальным минимумам по их возрастанию
A
еще вот интересно подумать про монотонные участки
A
их можно просто брать as is, чтобы уменьшить количество вычислений
T
А чем идея отличается от локальных максимумов
A
да ничем, симметрично вроде
T
Получается так да
T
Нужно для каждого элемента быстро вычислять сумму пирамиды слева и справа
T
Быстрее чем за линию
A
а что если сначала сделать преобразование именно в горизонтальные срезы?
T
Кууда