yarrr's blog

By yarrr, 13 years ago, In Russian

Пацаны, расскажите пожалуйста, я баян придумал или нет?


Задача простая: 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) Это и есть наш ответ, выводим число.
  • Vote: I like it
  • +16
  • Vote: I do not like it