Дан массив А и даны k запросов. Каждый запрос имеет вид :
1.Перевернуть весь отрезок от l до r.
2.Посчитать сумму на отрезке от l до r.
N<=10^5,k<=10^4.
Можно ли решить c помощью дерево отрезков? Если да то как?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Дан массив А и даны k запросов. Каждый запрос имеет вид :
1.Перевернуть весь отрезок от l до r.
2.Посчитать сумму на отрезке от l до r.
N<=10^5,k<=10^4.
Можно ли решить c помощью дерево отрезков? Если да то как?
Название |
---|
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/