parallel_binary_search.hpp¶
把多组答案同时在同一串更新前缀上二分；适合判定随时间单调、可批量重放更新的离线题。
Complexity: Time: \(O((U + Q) \log (U + 2))\) bookkeeping and update/check calls, and \(O(\log (U + 2))\) resets for \(U\) update positions. Space: \(O(U + Q)\), excluding callback state.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((U + Q) log(U + 2)) bookkeeping and update/check calls,
/// and O(log(U + 2)) resets for U update positions. Space: O(U + Q),
/// excluding callback state.
#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.
/// Boundaries may be sentinels; only prefixes strictly between them are tested.
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);
if (nq == 0 || std::llabs(static_cast<long long>(ok) - ng) <= 1) return hi;
std::vector<int> hd(std::size_t(nu) + 1, -1), nxt(nq);
while (true) {
int lst = -1;
// Prepending in reverse order keeps checks ordered by query within a bucket.
for (int que = nq - 1; que >= 0; 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);
nxt[que] = hd[mid];
hd[mid] = que;
lst = std::max(lst, mid);
}
if (lst == -1) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= lst; pre++) {
while (app < pre) {
upd(app++);
}
for (int que = hd[pre]; que != -1; que = nxt[que]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
hd[pre] = -1;
}
}
return hi;
}
} // namespace noya
// NOYA_PARALLEL_BINARY_SEARCH_HPP
#ifndef NOYA_PARALLEL_BINARY_SEARCH_HPP
#define NOYA_PARALLEL_BINARY_SEARCH_HPP 1
/// @complexity Time: O((U + Q) log(U + 2)) bookkeeping and update/check calls,
/// and O(log(U + 2)) resets for U update positions. Space: O(U + Q),
/// excluding callback state.
#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.
/// Boundaries may be sentinels; only prefixes strictly between them are tested.
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);
if (nq == 0 || std::llabs(static_cast<long long>(ok) - ng) <= 1) return hi;
std::vector<int> hd(std::size_t(nu) + 1, -1), nxt(nq);
while (true) {
int lst = -1;
// Prepending in reverse order keeps checks ordered by query within a bucket.
for (int que = nq - 1; que >= 0; 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);
nxt[que] = hd[mid];
hd[mid] = que;
lst = std::max(lst, mid);
}
if (lst == -1) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= lst; pre++) {
while (app < pre) {
upd(app++);
}
for (int que = hd[pre]; que != -1; que = nxt[que]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
hd[pre] = -1;
}
}
return hi;
}
} // namespace noya
#endif // NOYA_PARALLEL_BINARY_SEARCH_HPP
/// @complexity Time: O((U + Q) log(U + 2)) bookkeeping and update/check calls,
/// and O(log(U + 2)) resets for U update positions. Space: O(U + Q),
/// excluding callback state.
#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.
/// Boundaries may be sentinels; only prefixes strictly between them are tested.
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);
if (nq == 0 || std::llabs(static_cast<long long>(ok) - ng) <= 1) return hi;
std::vector<int> hd(std::size_t(nu) + 1, -1), nxt(nq);
while (true) {
int lst = -1;
// Prepending in reverse order keeps checks ordered by query within a bucket.
for (int que = nq - 1; que >= 0; 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);
nxt[que] = hd[mid];
hd[mid] = que;
lst = std::max(lst, mid);
}
if (lst == -1) {
break;
}
res();
int app = 0;
for (int pre = 0; pre <= lst; pre++) {
while (app < pre) {
upd(app++);
}
for (int que = hd[pre]; que != -1; que = nxt[que]) {
if (che(que)) {
hi[que] = pre;
} else {
lo[que] = pre;
}
}
hd[pre] = -1;
}
}
return hi;
}
} // namespace noya
// NOYA_PARALLEL_BINARY_SEARCH_HPP