Доброго времени суток пользователи Codeforces. Не могли бы вы подсказать задачи на вариации дерева отрезков? Желательно:
- Количество различных чисел на отрезке
- Поиск подотрезка с максимальной сумой
- Есть ли число на отрезке
- K-я порядковая статистика на отрезке
- Поиск К-того нуля и прочие нетривиальные задачи на дерево отрезков.
Также хотелось бы решение на
- Количество различных чисел на отрезке
- K-я порядковая статистика на отрезке
Допускаются решения как деревом отрезков, так и корневой или прочими структурами данных.
Пока только это вспомнил:
http://www.spoj.com/problems/DQUERY/
http://www.spoj.com/problems/PT07J/
http://www.spoj.com/problems/COT/
100068J - Сколько звезд на небе?
369E - Валера и запросы
100043I - Откат
http://www.spoj.com/problems/MKTHNUM/
http://www.spoj.com/problems/GOT/
http://acm.timus.ru/problem.aspx?space=1&num=1717
Если говорить о spoj.pl, то там еще есть серия задач "Can you answer these queries":
http://www.spoj.com/problems/GSS1
http://www.spoj.com/problems/GSS2
...
http://www.spoj.com/problems/GSS9
Спасибо:)
K-ая статистика много обсуждалась здесь.
Количество различных чисел на отрезке: Задача С
еще бы решение знать )
Здесь обсуждалось решение :)
SPOJ CEOI09TR, я ее решал весьма нетривиальным деревом отрезков.
Советую вначале постараться решить задачу самостоятельно, ну а если станет совсем невмоготу — есть разбор за моим авторством.
Вот также задачи на тему Дерево отрезков с e-olimp'a : http://www.e-olimp.com/ua/problems/4481 http://www.e-olimp.com/ua/problems/4482 http://www.e-olimp.com/ua/problems/4483 ... http://www.e-olimp.com/ua/problems/4499 http://www.e-olimp.com/ua/problems/4500
4 учебные задачи для тренировки
http://informatics.mccme.ru/mod/statements/view3.php?id=6150&chapterid=3326#1
http://codeforces.com/contest/528/problem/B
Мне часто стала попадаться задачка на подсчет суммы различных элементов на отрезке. Интересно как она решается 1) с персистентным ДО 2) без персистентности