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

У каждого человека $x$ есть целевое количество ресурсов $need_x$.

Каждое событие описывается как $(l_i, r_i, a_i)$ и означает, что каждый участок земли на отрезке $[l_i, r_i]$ генерирует $a_i$ ресурсов. Если отрезок «замыкается», то земли считаются расположенными по кругу.

То есть если человек владеет $t$ участками внутри затронутого отрезка, то этот человек получает $t \cdot a_i$ ресурсов от этого события.

Для каждого человека нужно определить, после какого события он впервые достигает своего целевого количества. Если он никогда его не достигает, ответ — -1.

Наивное решение

Мы можем решать задачу независимо для каждого человека.

Для одного фиксированного человека $x$ пусть $can(x, m)$ означает, может ли человек $x$ достичь требуемого количества, используя только первые $m$ событий.

Эта функция монотонна:

• если can(x, m) истинно, то can(x, m+1) тоже истинно.

Значит, для каждого человека можно сделать бинарный поиск по ответу.

Чтобы вычислить can(x, m), нужно применить первые $m$ событий. Для этого можно использовать дерево Фенвика или дерево отрезков вместе со вспомогательными функциями вроде:

• add_updates(l, r)
• remove_updates(l, r)

Тогда получаем следующее решение для одного человека:

Это работает, но слишком медленно, потому что одни и те же обновления добавляются и удаляются много раз для разных людей.

Основная идея параллельного бинарного поиска

Медленная часть — не сама проверка can(x, m), а многократное пересоздание состояния для множества разных значений m.

Ключевое наблюдение: многие люди задают вопросы про одну и ту же середину m.

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

• группируем всех людей, у которых текущая середина одинакова;
• применяем обновления только один раз до этой середины;
• отвечаем на все эти проверки вместе.

Это называется параллельный бинарный поиск.

Рекурсивная версия

Мы пишем рекурсивную функцию:

которая означает, что ответ для каждого человека из people лежит в интервале $[l, r]$.

Если l == r, то ответ для всех этих людей уже зафиксирован.

Иначе:

1. пусть $m = \left\lfloor \frac{l+r}{2} \right\rfloor$
2. применяем все события от l до m;
3. делим людей на две группы:
   • те, для кого can(x, m) истинно, идут в левую половину;
   • остальные идут в правую половину;
4. удаляем обновления;
5. рекурсивно вызываемся для обеих половин.

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

Итеративная версия

Ту же идею можно реализовать и итеративно.

Для каждого человека $x$ мы поддерживаем текущий диапазон поиска:

• tl[x] — левая граница;
• tr[x] — правая граница.

Изначально для каждого человека:

• tl[x] = 0
• tr[x] = K + 1

Затем мы повторяем следующий процесс:

1. для каждого человека вычисляем текущую середину $mid_x = \left\lfloor \frac{tl[x] + tr[x]}{2} \right\rfloor$
2. группируем людей по этим серединам;
3. делаем проход по событиям в порядке возрастания m, применяя обновления по мере продвижения;
4. когда мы достигаем середины m, отвечаем для всех людей, назначенных этой середине;
5. обновляем их диапазоны бинарного поиска.