Канал посвящен олимпиадам по информатике/спортивному программированию/ЕГЭ по информатике и изучению языков.
По всем вопросам: @postupashkaProg
Чат: @botalka_prog
Post #159
612
Здравствуйте, камрады 😎
Сегодня прокачанная версия бинпоиска по ответу — параллельный бинпоиск: тот же бинпоиск, только сразу для кучи запросов.
Идея
Есть m операций (добавляем рёбра, прибавляем на отрезках) и q запросов «после какой минимальной операции для меня выполнится условие?». Условие монотонно: выполнилось после t операций — выполнится и после t + 1.
Для одного запроса это обычный бинпоиск по ответу. Но check дорогой: чтобы проверить момент t, нужно применить t операций к структуре, а это O(m). На все запросы выходит O(q · m · log m), не влезаем.
Заметим: все эти бинпоиски гоняют префиксы одной и той же последовательности операций. Значит, можно сделать один прогон и по дороге проверить всех сразу.
Раунд выглядит так:
1. Раскладываем запросы по корзинам по их mid = (lo + hi) / 2.
2. Сбрасываем структуру и применяем операции t = 1, 2, ..., m. Сразу после операции t проверяем всех, у кого mid = t, и сдвигаем им lo или hi.
3. Повторяем раунды, пока у всех не станет lo = hi.
За раунд отрезок каждого запроса уменьшается вдвое, поэтому раундов log m, и каждый запрос проверяется всего log m раз. Если бы мы проверяли все запросы после каждой операции, каждый проверился бы m раз.
Задача (Stamp Rally, AGC 002 D)
Связный граф, m пронумерованных рёбер. Запрос (x, y, z): два брата стартуют из x и y и хотят вместе посетить z вершин. Нужно минимизировать максимальный номер пройденного ребра.
Ответ — минимальное t, при котором по рёбрам 1..t из x и y вместе достижимо хотя бы z вершин. Проверяем через DSU из нашего поста: если x и y в одной компоненте, достижимо sz[root(x)], иначе сумма размеров двух компонент. Но DSU не умеет удалять рёбра, так что обычный бинпоиск пересобирал бы его на каждой проверке каждого запроса.
По раундам при m = 8: сначала у всех mid = 4. Потом запросы расходятся на [1, 4] и [5, 8] с mid = 2 и 6, и обе группы проверяются за один прогон. Потом mid = 1, 3, 5, 7. Каждый запрос проверили 3 раза вместо 8.
Важные моменты
Каждый раунд строим структуру с нуля.
Сначала применяем операцию t, потом проверяем запросы с mid = t.
Корзины вместо сортировки: раунд стоит O(n + m + q).
Если ответа может не быть, берите hi = m + 1 как фиктивное «точно выполнено». lo = m + 1 в конце значит, что ответа нет.
Приём только оффлайн, и условие обязано быть монотонным.
Асимптотика
log m раундов, каждый за O(n + m + q). Итого O((n + m + q) · log m).
Где применять
«Есть m изменений, для каждого из q объектов найдите первый момент, когда что-то выполнится»: рёбра + DSU, прибавления на отрезках + Фенвик, k-я статистика на отрезке (бинпоиск по значению + Фенвик).
Практика
Stamp Rally — AtCoder AGC 002 D
Meteors — SPOJ
Qpwoeirut and Vertices — CF 1706E
@postupashki_prog
Сегодня прокачанная версия бинпоиска по ответу — параллельный бинпоиск: тот же бинпоиск, только сразу для кучи запросов.
Идея
Есть m операций (добавляем рёбра, прибавляем на отрезках) и q запросов «после какой минимальной операции для меня выполнится условие?». Условие монотонно: выполнилось после t операций — выполнится и после t + 1.
Для одного запроса это обычный бинпоиск по ответу. Но check дорогой: чтобы проверить момент t, нужно применить t операций к структуре, а это O(m). На все запросы выходит O(q · m · log m), не влезаем.
Заметим: все эти бинпоиски гоняют префиксы одной и той же последовательности операций. Значит, можно сделать один прогон и по дороге проверить всех сразу.
Раунд выглядит так:
1. Раскладываем запросы по корзинам по их mid = (lo + hi) / 2.
2. Сбрасываем структуру и применяем операции t = 1, 2, ..., m. Сразу после операции t проверяем всех, у кого mid = t, и сдвигаем им lo или hi.
3. Повторяем раунды, пока у всех не станет lo = hi.
За раунд отрезок каждого запроса уменьшается вдвое, поэтому раундов log m, и каждый запрос проверяется всего log m раз. Если бы мы проверяли все запросы после каждой операции, каждый проверился бы m раз.
Задача (Stamp Rally, AGC 002 D)
Связный граф, m пронумерованных рёбер. Запрос (x, y, z): два брата стартуют из x и y и хотят вместе посетить z вершин. Нужно минимизировать максимальный номер пройденного ребра.
Ответ — минимальное t, при котором по рёбрам 1..t из x и y вместе достижимо хотя бы z вершин. Проверяем через DSU из нашего поста: если x и y в одной компоненте, достижимо sz[root(x)], иначе сумма размеров двух компонент. Но DSU не умеет удалять рёбра, так что обычный бинпоиск пересобирал бы его на каждой проверке каждого запроса.
// root и unite с объединением по размеру — как в посте про DSU
int reach(int x, int y) {
x = root(x); y = root(y);
return x == y ? sz[x] : sz[x] + sz[y];
}
// ea[t], eb[t] — концы t-го ребра; qx, qy, qz — запросы
vector<int> lo(q, 1), hi(q, m);
while (true) {
vector<vector<int>> byMid(m + 1); // byMid[t] — у кого mid = t
bool active = false;
for (int i = 0; i < q; i++)
if (lo[i] < hi[i]) {
byMid[(lo[i] + hi[i]) / 2].push_back(i);
active = true;
}
if (!active) break; // все бинпоиски сошлись
for (int v = 1; v <= n; v++) par[v] = v, sz[v] = 1;
for (int t = 1; t <= m; t++) {
unite(ea[t], eb[t]); // добавили t-е ребро
for (int i : byMid[t]) // проверяем всех с mid = t
if (reach(qx[i], qy[i]) >= qz[i]) hi[i] = t;
else lo[i] = t + 1;
}
}
// ответ на i-й запрос — lo[i]
По раундам при m = 8: сначала у всех mid = 4. Потом запросы расходятся на [1, 4] и [5, 8] с mid = 2 и 6, и обе группы проверяются за один прогон. Потом mid = 1, 3, 5, 7. Каждый запрос проверили 3 раза вместо 8.
Важные моменты
Каждый раунд строим структуру с нуля.
Сначала применяем операцию t, потом проверяем запросы с mid = t.
Корзины вместо сортировки: раунд стоит O(n + m + q).
Если ответа может не быть, берите hi = m + 1 как фиктивное «точно выполнено». lo = m + 1 в конце значит, что ответа нет.
Приём только оффлайн, и условие обязано быть монотонным.
Асимптотика
log m раундов, каждый за O(n + m + q). Итого O((n + m + q) · log m).
Где применять
«Есть m изменений, для каждого из q объектов найдите первый момент, когда что-то выполнится»: рёбра + DSU, прибавления на отрезках + Фенвик, k-я статистика на отрезке (бинпоиск по значению + Фенвик).
Практика
Stamp Rally — AtCoder AGC 002 D
Meteors — SPOJ
Qpwoeirut and Vertices — CF 1706E
@postupashki_prog
