Дан массив А и даны k запросов. Каждый запрос имеет вид : 1.Перевернуть весь отрезок от l до r. 2.Посчитать сумму на отрезке от l до r. N<=10^5,k<=10^4. Можно ли решить c помощью дерево отрезков? Если да то как?
Дан массив А и даны k запросов. Каждый запрос имеет вид : 1.Перевернуть весь отрезок от l до r. 2.Посчитать сумму на отрезке от l до r. N<=10^5,k<=10^4. Можно ли решить c помощью дерево отрезков? Если да то как?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Can you give me link of this problem?
http://olympiads.kz/files/kz-2012-republic-statements.zip. Problem G
Не (не декартово дерево) -> декартово дерево
Решение с помощью декартова дерева (по неявному ключу) довольно понятное и быстрое, нежели решение с помощью дерева отрезков(если оно существует).
Думаю это невозможно ( ну по крайней мере, я такого решения не знаю ) . Можна решить корневой, но декартово дерево решает эту задачу проще .
Вот мой код, на запросы: реверс на отрезке, замена элемента на позиции P, ну и сумма на отрезке.
Декартка на массивах. Вот идея переворота на отрезке.
Я не до конца уверен, но, по-моему, у нас в командном обсуждении возникала идея, как симулировать переворот на отрезке с помощью ДО. Не уверен точно, что то, что я сейчас вспомнил, не имеет дырок, но, по-моему, как-то так:
ДО строится на массиве частичных разностей, Ti = Ai - Ai - 1. Функция, которая хранится в вершине ДО — сумма частичных сумм на отрезке:
. А также — просто сумма на отрезке 
. Как после изменения в точке соединить два потомка текущей вершины вроде должно быть понятно — S2(L, R) = S2(L, M) + S2(M, R) + (R - M) * S(L, M).
Что происходит при перевороте? Для всех точек, кроме крайних точек переворота, просто меняется знак (было Ai - Ai - 1, после переворота × - 1. Для крайних точек значение просто поменялось.
То есть нам нужно уметь менять значение в точке, и "лениво" проталкивать вниз умножение на минус единицу.
Крайних случаев в таком решении должно быть как добра, на контестах никогда не встречалось.
Can be solved with a treap with implicit key... read this post http://habrahabr.ru/post/101818/