Пацаны, расскажите пожалуйста, я баян придумал или нет?
Задача простая: m запросов, вывести k-ю порядковую статистику массива a[n] на отрезке [l,r].
n ≤ 105, m ≤ 105
Сложность: n· log(n) препроцессинг, log2(n) на запрос.
Что делаем:
1) Сортируем массив в виде пар (ai, i), сначала по значению, потом по индексу.
2) Строим n-штук persistent segment tree, где на i-м шаге добавляем в дерево отрезков индекс элемента, который находится по i-му индексу в отсортированном массиве пар.
3) Бинпоиском находит нижнюю границу i, где в дереве отрезков i sum(l, r) ≥ k.
4) Это и есть наш ответ, выводим число.
Comments (0)
