3622
правки
Изменения
м
→Чуть менее наивное решение
=== Чуть менее наивное решение ===
Будем использовать два указателя, с помощью которых сможем обойти массивы , не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k - 1)</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
=== Еще одно решение ===
В первом массиве выберем серединный элемент <tex>(i = n / 2)</tex> и бинпоиском найдем во втором массиве позицию <tex>j</tex>, на котором стоит наибольший элемент, меньший <tex>a[i]</tex>. Если <tex>i + j = k - 2</tex>, то мы нашли <tex>k</tex>-ую порядковую статистику {{---}} это элемент <tex>a[i]</tex>. Иначе, если <tex>i + j > k - 2</tex>, то далее тем же способом ищем в массиве <tex>A</tex> в диапазоне индексов <tex>[0, i - 1]</tex>, а если <tex>i + j < k - 2</tex>, то в диапазоне индексов <tex>[i + 1, n - 1]</tex>. Решая задачу таким способом, мы получим асимптотику <tex>O(\log(n) \cdot \log(m))</tex>.
