Параллельный двоичный поиск

Бывает так: надо сделать $k$ двоичных поисков, и каждая проверка стоит дорого — прогнать все события, обойти всю структуру, задать вопрос жюри. По отдельности это $k \log n$ дорогих проверок, и задача не проходит.

Приём называется параллельный двоичный поиск: вести все поиски одновременно и делить дорогую проверку между ними.

Схема

шаг	что происходит
1	у каждого поиска свои границы $lo_i$, $hi_i$; считаем середины
2	раскладываем поиски по корзинам: поиск $i$ — в корзину $mid_i$
3	один раз прогоняем процесс от начала до конца
4	дойдя до момента $j$, отвечаем всем поискам из корзины $j$
5	сдвигаем границы и повторяем, пока есть активные

for (;;) {
    bool active = false;
    for (int j = 0; j <= q + 1; j++) bucket[j].clear();
    for (int i = 0; i < k; i++) {
        if (lo[i] >= hi[i]) continue;
        active = true;
        bucket[(lo[i] + hi[i]) / 2].push_back(i);
    }
    if (!active) break;
    clearStructure();
    for (int j = 1; j <= q; j++) {
        applyEvent(j);
        for (int i : bucket[j]) check(i) ? hi[i] = j : lo[i] = j + 1;
    }
}

Раундов $O(\log q)$; в каждом процесс прогоняется один раз, и каждый поиск отвечает ровно один вопрос. Если событие применяется за $O(\log n)$ и проверка стоит столько же, всё вместе — $O((q + k)\log q \log n)$.

Когда это нужно

задача	что за процесс	что ищем
«Метеоры»	дожди прибавляют на отрезке	после какого дождя заявка выполнится
«когда впервые»	события меняют массив	первый момент, когда свойство стало верным
$k$-я статистика на отрезке	добавление значений по возрастанию	какое значение оказалось $k$-м
интерактив с пакетом	вопрос жюри на $10^5$ пар	граница для каждого элемента

Обязательное условие — монотонность: свойство, по которому ищем, должно один раз переключаться с «нет» на «да» по ходу процесса. Без этого двоичный поиск неприменим, и никакая параллельность не спасёт.

Что ломается чаще всего

Структура не почищена между раундами. Каждый раунд прогоняет процесс заново, значит дерево Фенвика надо обнулять — или откатывать те же прибавления. Забытая чистка даёт ответы, которые «почти правильные»: ошибка видна не на первом раунде.

Поиски, у которых границы сошлись, попадают в пакет. В интерактивных задачах лимит на размер пакета обычно ровно такой, чтобы поместились активные; лишняя пара — и вердикт «неверный формат».

Не тот ответ при «никогда». Если свойство не наступило, граница остаётся за концом процесса. Это законное состояние, и его надо отличать от последнего момента: договоритесь заранее, что $lo = q + 1$ означает $-1$ в ответе.

Полезный частный случай: если процесс — это «добавляем значения по возрастанию», параллельный двоичный поиск заменяет персистентное дерево отрезков. Он длиннее в написании, зато не требует ни версий, ни памяти на них.

Смежное: двоичный поиск по ответу, интерактивные задачи, персистентное дерево отрезков.