Задача ШАР
Даются числа N и K, а затем массив a целых чисел длины N
Вам нужно найти такую позицию i в массиве а, что 90% всех чисел слева от позиции i меньше чем число a[i], но число i должно быть больше K.

Решение:
N было до 1e6 и решения использованием дерево отрезков или дерево фенвика не проходили по времени, так как код писать нужно на питоне.

Для решения этой задачи нам нужно научиться хранить для каждой позиции i девяноста процентов наименьших чисел слева от позиции i.
Представьте, что вы это сделали для позиции i, то есть у вас есть массив b с 90% наименьших чисел слева от позиции i.
Что происходит с массивом b, когда вы переходите с позиции i на позицию i + 1 ?
Вам нужно добавить число a[i] в массив и удалить несколько максимальных чисел из массива b, так чтобы длина массива b стала (i+1)*0.9.

А с этим нам поможет heap, единственное он не умеет удалять максимальные числа, а умеет удалять только минимальные, так что будем хранить числа со знаком минус!

Общий алгоритм:
Для начало добавим первые K чисел в heap со знаком минус.
После удалим need_delete = K / 10 максимальных чисел из heap, запомним, что мы удалили count_deleted = K/10 чисел.
Теперь начинаем рассматривать числа из массива a начиная с позиции K.
Если a[i] > -heap[0] это означает что число a[i] больше чем 90% чисел и мы нашли ответ.
Иначе мы добавляем в heap число -a[i] и удаляем максимальные числа из heap пока count_deleted не станет равным need_delete.
Время работы алгоритма O(nlogn).
Код в комментариях: