parallel_binary_search.hpp¶
Run parallel binary search over prefixes of a common update list. ok must be a known true boundary and ng a known false boundary. Calling check(q) after t calls to update represents the predicate at prefix t.
把多组答案同时在同一串更新前缀上二分；适合判定随时间单调、可批量重放更新的离线题。
Implementation¶
#ifndef NOYA_PARALLEL_BINARY_SEARCH_HPP
#define NOYA_PARALLEL_BINARY_SEARCH_HPP 1
/// @complexity Time: O((U + Q) log U) callback work for U update positions.
/// Space: O(Q).
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Run parallel binary search over prefixes of a common update list.
/// `ok` must be a known true boundary and `ng` a known false boundary. Calling
/// check(q) after t calls to update represents the predicate at prefix t.
template <class Reset, class Update, class Check>
std::vector<int> parallel_binary_search(int query_count, int ok, int ng,
Reset reset, Update update,
Check check) {
assert(query_count >= 0);
int update_count = std::max(ok, ng);
assert(std::min(ok, ng) >= -1);
std::vector<int> true_bound(query_count, ok);
std::vector<int> false_bound(query_count, ng);
while (true) {
std::vector<std::vector<int>> buckets(update_count + 1);
int remaining = 0;
for (int query = 0; query < query_count; query++) {
if (std::llabs(static_cast<long long>(true_bound[query]) -
false_bound[query]) <= 1) {
continue;
}
int middle = std::midpoint(true_bound[query], false_bound[query]);
assert(0 <= middle && middle <= update_count);
buckets[middle].push_back(query);
remaining++;
}
if (remaining == 0) {
break;
}
reset();
int applied = 0;
for (int prefix = 0; prefix <= update_count; prefix++) {
while (applied < prefix) {
update(applied++);
}
for (int query : buckets[prefix]) {
if (check(query)) {
true_bound[query] = prefix;
} else {
false_bound[query] = prefix;
}
}
}
}
return true_bound;
}
} // namespace noya
#endif // NOYA_PARALLEL_BINARY_SEARCH_HPP
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <numeric>
#include <vector>
/// @complexity Time: O((U + Q) log U) callback work for U update positions.
/// Space: O(Q).
namespace noya {
/// @brief Run parallel binary search over prefixes of a common update list.
/// `ok` must be a known true boundary and `ng` a known false boundary. Calling
/// check(q) after t calls to update represents the predicate at prefix t.
template <class Reset, class Update, class Check>
std::vector<int> parallel_binary_search(int query_count, int ok, int ng,
Reset reset, Update update,
Check check) {
assert(query_count >= 0);
int update_count = std::max(ok, ng);
assert(std::min(ok, ng) >= -1);
std::vector<int> true_bound(query_count, ok);
std::vector<int> false_bound(query_count, ng);
while (true) {
std::vector<std::vector<int>> buckets(update_count + 1);
int remaining = 0;
for (int query = 0; query < query_count; query++) {
if (std::llabs(static_cast<long long>(true_bound[query]) -
false_bound[query]) <= 1) {
continue;
}
int middle = std::midpoint(true_bound[query], false_bound[query]);
assert(0 <= middle && middle <= update_count);
buckets[middle].push_back(query);
remaining++;
}
if (remaining == 0) {
break;
}
reset();
int applied = 0;
for (int prefix = 0; prefix <= update_count; prefix++) {
while (applied < prefix) {
update(applied++);
}
for (int query : buckets[prefix]) {
if (check(query)) {
true_bound[query] = prefix;
} else {
false_bound[query] = prefix;
}
}
}
}
return true_bound;
}
} // namespace noya