parallel_binary_search.hpp¶
把多组答案同时在同一串更新前缀上二分；适合判定随时间单调、可批量重放更新的离线题。
Complexity: Time: O((U + Q) log U) callback work for U update positions. Space: O(Q).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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
/// che(q) after t calls to upd represents the predicate at prefix t.
template <class Reset, class Update, class Check>
std::vector<int> parallel_binary_search(int nq, int ok, int ng, Reset res,
Update upd, Check che) {
assert(nq >= 0);
int nu = std::max(ok, ng);
assert(std::min(ok, ng) >= -1);
std::vector<int> hi(nq, ok);
std::vector<int> lo(nq, ng);
while (true) {
std::vector<std::vector<int>> buc(nu + 1);
int rem = 0;
for (int que = 0; que < nq; que++) {
if (std::llabs(static_cast<long long>(hi[que]) - lo[que]) <= 1) {
continue;
}
int mid = std::midpoint(hi[que], lo[que]);
assert(0 <= mid && mid <= nu);
buc[mid].push_back(que);
rem++;
}
if (rem == 0) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= nu; pre++) {
while (app < pre) {
upd(app++);
}
for (int que : buc[pre]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
}
}
return hi;
}
} // namespace noya
#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
/// che(q) after t calls to upd represents the predicate at prefix t.
template <class Reset, class Update, class Check>
std::vector<int> parallel_binary_search(int nq, int ok, int ng, Reset res,
Update upd, Check che) {
assert(nq >= 0);
int nu = std::max(ok, ng);
assert(std::min(ok, ng) >= -1);
std::vector<int> hi(nq, ok);
std::vector<int> lo(nq, ng);
while (true) {
std::vector<std::vector<int>> buc(nu + 1);
int rem = 0;
for (int que = 0; que < nq; que++) {
if (std::llabs(static_cast<long long>(hi[que]) - lo[que]) <= 1) {
continue;
}
int mid = std::midpoint(hi[que], lo[que]);
assert(0 <= mid && mid <= nu);
buc[mid].push_back(que);
rem++;
}
if (rem == 0) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= nu; pre++) {
while (app < pre) {
upd(app++);
}
for (int que : buc[pre]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
}
}
return hi;
}
} // 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
/// che(q) after t calls to upd represents the predicate at prefix t.
template <class Reset, class Update, class Check>
std::vector<int> parallel_binary_search(int nq, int ok, int ng, Reset res,
Update upd, Check che) {
assert(nq >= 0);
int nu = std::max(ok, ng);
assert(std::min(ok, ng) >= -1);
std::vector<int> hi(nq, ok);
std::vector<int> lo(nq, ng);
while (true) {
std::vector<std::vector<int>> buc(nu + 1);
int rem = 0;
for (int que = 0; que < nq; que++) {
if (std::llabs(static_cast<long long>(hi[que]) - lo[que]) <= 1) {
continue;
}
int mid = std::midpoint(hi[que], lo[que]);
assert(0 <= mid && mid <= nu);
buc[mid].push_back(que);
rem++;
}
if (rem == 0) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= nu; pre++) {
while (app < pre) {
upd(app++);
}
for (int que : buc[pre]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
}
}
return hi;
}
} // namespace noya