Параллельный бинарный поиск
Параллельный бинарный поиск
Пример задачи
Вам дано людей и земель. У каждой земли () есть владелец (), и у каждого человека есть целевой уровень ресурсов .
Параллельный бинарный поиск
Вам дано людей и земель. У каждой земли () есть владелец (), и у каждого человека есть целевой уровень ресурсов .
событий происходят последовательно. Каждое событие задаётся тройкой и означает, что земли от до генерируют ресурсов.
Заметим, что может быть больше , так как земли расположены по кругу.
Если человек владеет землями на отрезке , то он получает ресурсов.
Для каждого человека нужно определить, после какого события он достигнет своего целевого уровня ресурсов. Если это невозможно, выведите -1.
Для каждого человека можно решать задачу отдельно с помощью бинарного поиска по ответу.
Пусть can(x, m) = true, если человек может набрать нужное количество ресурсов после первых событий.
Чтобы отвечать на can(x, m), нужно уметь быстро добавить первые событий и посчитать вклад по землям этого человека. Это можно делать с помощью дерева Фенвика или дерева отрезков.
Идея для одного человека:
Проблема здесь в том, что мы много раз добавляем и удаляем одни и те же события.
Главная идея: отвечать на бинарный поиск сразу для всех людей.
Функция can(x, m) сама по себе работает достаточно быстро, а медленно именно повторное добавление/удаление событий.
Поэтому мы делим людей по ответу на середине и рекурсивно обрабатываем группы.
Так мы уменьшаем количество повторных обновлений и получаем хорошую асимптотику.
Ту же идею можно записать итеративно.
Для каждого человека храним границы бинарного поиска:
tl[x] — левая границаtr[x] — правая границаИзначально для всех:
tl[x] = 0tr[x] = K + 1На каждой итерации группируем людей по их середине (tl[x] + tr[x]) / 2, последовательно добавляем события и проверяем can(x, m).
int solve(int x) {
int l = 0, r = K + 1;
while (l < r) {
int m = (l + r) / 2;
add_updates(1, m);
if (can(x, m)) {
r = m;
} else {
l = m + 1;
}
remove_updates(1, m);
}
if (l == K + 1) return -1;
return l;
}
void solve(int l, int r, vector<int> can_x) {
if (can_x.empty()) {
return;
} else if (l == r) {
for (int x: can_x) {
if (l == K + 1) {
res[x] = -1;
} else {
res[x] = l;
}
}
return;
}
int m = (l + r) / 2;
add_updates(l, m);
vector<int> can_l, can_r;
for (int x: can_x) {
if (can(x, m)) {
can_l.push_back(x);
} else {
can_r.push_back(x);
}
}
remove_updates(l, m);
solve(l, m, can_l);
solve(m + 1, r, can_r);
}
void solve() {
for (int i = 1; i <= n; i++) {
tl[i] = 0;
tr[i] = K + 1;
}
for (int it = 0; it < LOG_K; it++) {
for (int i = 0; i <= K; i++) {
query[i].clear();
}
for (int i = 1; i <= n; i++) {
query[(tl[i] + tr[i]) / 2].push_back(i);
}
for (int m = 0; m <= K; m++) {
if (m > 0) {
add_updates(m, m);
}
for (int x : query[m]) {
if (can(x, m)) {
tr[x] = m;
} else {
tl[x] = m + 1;
}
}
}
remove_updates(1, K);
}
}