Can you give me link of this problem?

не декартово дерево

Не (не декартово дерево) -> декартово дерево

Можно ли решить c помощью дерево отрезков?

Решение с помощью декартова дерева (по неявному ключу) довольно понятное и быстрое, нежели решение с помощью дерева отрезков(если оно существует).

Думаю это невозможно ( ну по крайней мере, я такого решения не знаю ) . Можна решить корневой, но декартово дерево решает эту задачу проще .

Вот мой код, на запросы: реверс на отрезке, замена элемента на позиции P, ну и сумма на отрезке.
Декартка на массивах. Вот идея переворота на отрезке.

Я не до конца уверен, но, по-моему, у нас в командном обсуждении возникала идея, как симулировать переворот на отрезке с помощью ДО. Не уверен точно, что то, что я сейчас вспомнил, не имеет дырок, но, по-моему, как-то так:

ДО строится на массиве частичных разностей, T_i = A_i - A_i - 1. Функция, которая хранится в вершине ДО — сумма частичных сумм на отрезке: . А также — просто сумма на отрезке . Как после изменения в точке соединить два потомка текущей вершины вроде должно быть понятно — S2(L, R) = S2(L, M) + S2(M, R) + (R - M) * S(L, M).

Что происходит при перевороте? Для всех точек, кроме крайних точек переворота, просто меняется знак (было A_i - A_i - 1, после переворота  ×  - 1. Для крайних точек значение просто поменялось.

То есть нам нужно уметь менять значение в точке, и "лениво" проталкивать вниз умножение на минус единицу.

Крайних случаев в таком решении должно быть как добра, на контестах никогда не встречалось.

Can be solved with a treap with implicit key... read this post http://habrahabr.ru/post/101818/