Блог пользователя EeOneGuy

Автор EeOneGuy, 10 лет назад, По-русски

Дан массив А и даны k запросов. Каждый запрос имеет вид : 1.Перевернуть весь отрезок от l до r. 2.Посчитать сумму на отрезке от l до r. N<=10^5,k<=10^4. Можно ли решить c помощью дерево отрезков? Если да то как?

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you give me link of this problem?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 7   Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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

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

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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