"Уже несколько дней не могу нормально спать))" — Плохо)

Ок, попробую написать решение, которое скорее всего должно пройти по времени:

Решение с использованием SQRT-декомпозиции по блокам

1. Разбить массив на блоки длины K ~ sqrt(N)
2. Для каждого блока хранить частичные блоки(отсортиванный список элементов и их позиции), кроме того Sum1 — сколько чисел меньше K, 2K, 3K, ... N, и ещё внутри каждого частичного блока ещё блоки, то есть Sum1[i] — сколько чисел меньше либо равно i*K, Sum2[i][j] — обозначает сколько чисел меньше либо равно i*K + j, пересчитываем Фенвиком.
3. Апдейт не сложно сделать за какое-нибудь время O(K log N + (N/K) log N) для Sum1 и для Sum2 в каждом блоке и для элементов которые не входят в блоки целиком — [L..(L+K-1)*K), [R/K*K..R], могу расписать подробнее
4. Запрос К-го порядкого элемента тоже не сложно, просто бинпоиск по Sum1: находим блок где должен быть K-ый элемент по Sum1, потом бинпоиск по Sum2. Но вместо бинпоиска можно сделать внешний спуск по дереву Фенвика для нескольких блоков, и нужно учитывать элементы которые не входят в блоки [L..(L+K-1)*K), [R/K*K..R]. Получается O(K log N + (N/K) log N)

Естественно, можно хранить только один Фенвик Sum[i](сколько чисел меньше либо равно i) для всего блока, но тогда прыжки по памяти будут больше(зависит от тестов и компилятора!).

Можно сделать за O(log^2n) на запрос. Создадим дерево отрезков, а в каждой его вершине — декартово дерево. Будем поддерживать в ДД пару (число, кол-во). Тогда для обработки 1 запроса достаточно спуститься в нужную вершину ДО (которая соответствует отрезку [l;r]), в текущем ДД удалить число X и вставить пару (Y, кол-во удаленных X) (либо если существует, просто добавить это кол-во). Ну я думаю запрос 2 типа тривиален.

Вроде я придумал как решать за на запрос.
Давайте вспомним решение за без изменений: отсортируем все пары { a[i], i } по неубыванию, получим отсортированный массив, и по второму элементу в паре(то есть по индексам i) построим MegeSortTree(дерево отрезков, в вершине которого расположен отсортированный массив отрезка, за который отвечает данная вершина). Теперь для запроса k-того элемента нам нужно уметь спускаться по ДО и понимать, в каком сыне лежит ответ. Как это сделать? Если в левом сыне есть хотя бы k чисел из отрезка от l до r, то переходив в него, иначе — в правого новым k, равным разности старого k и количеству чисел от l до r в левом сыне.
Ок, я утверждаю, что мы можем переделать нашу структуру так, чтобы мы могли ее изменять. Для этого потребуется быстро перестраивать наш отсортированный массив пар, и, соответственно, ДО, которое мы построили по нему. Для этого Заменим ДО на ДД по неявному ключу, а в вершине ДД будем хранить еще одно ДД, но уже по ключу, чтобы быстро перестраивать сортированный массив, как в ДО. Итого мы не ухудшили асимптотику, но смогли в изменения.

Если кому-то будет полезно (вряд ли), сдал решение за O(n * m / 8 + m * sqrt(n)), то есть, запросы модицикации за квадрат, а один запрос порядковой статистики за корень. Там есть вызов функции stressTest() в начале main, его можно опустить. Может у кого-нибудь получится заставить GCC применить авто-векторизацию в месте, где срезается константа (строки 114-123).

for (int i = 0; i + 31 < blockSize; i += 32) {
    uint32_t bitmask = 0;
    for (int j = 0; j < 32; j += 8) {
        __m256 va = _mm256_load_ps(blockBegin + i + j);
        __m256 rs = _mm256_cmp_ps(vx, va, _CMP_EQ_OQ);
        bitmask = (bitmask << 8) | _mm256_movemask_ps(rs);
        _mm256_maskstore_ps(blockBegin + i + j, _mm256_cvtps_epi32(rs), vy);
    }
    changes += __builtin_popcountll(bitmask);
}

Кстати, TL на информатиксе к этой задаче был увеличен в два раза.