並列二分探索
(Src/Utility/ParallelBinarySearch.hpp)

• View this file on GitHub
• Last update: 2025-02-24 03:31:13+09:00
• Include: #include "Src/Utility/ParallelBinarySearch.hpp"

ライブラリの使い方

template <class T, class F>
std::vector<T> ParallelBinarySearch(std::vector<T> oks, std::vector<T> ngs, F f) {

T

整数型のみ

oks, ngs

$i$ 個目のクエリの必ず条件を満たす値、必ず条件を満たさない値

f

以下の条件を満たす関数。

その一。fには引数として、まだ探索が終わっていないクエリのstd::pair<T, usize>{x, id}のvectorが突っ込まれる。 引数のvector内部の{x, id}について、id番目のクエリのxの場合の判定問題を解く必要がある。

その二。返り値として、std::pair<bool, hoge>{T/F, id}`のvectorを入れる。firstは判定問題の結果。secondはそれが何番目のクエリかの添字。

計算量

$O(\max_{i} L)$ 回、fが呼ばれ、別途に $O(Q)$ の処理が入る。

テストを見る感じ、直書きするよりもだいぶ実測が遅い…

Verified with

• Test/AtCoder/agc002_d.test.cpp

Code

#pragma once

#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

namespace zawa {

template <std::integral T, class F>
std::vector<T> ParallelBinarySearch(std::vector<T> oks, std::vector<T> ngs, F f) {
    assert(oks.size() == ngs.size());
    while (true) {
        std::vector<std::pair<T, usize>> remains; 
        std::vector<usize> inv(oks.size(), static_cast<usize>(-1));
        for (usize i = 0 ; i < oks.size() ; i++) if ((oks[i] >= ngs[i] ? oks[i] - ngs[i] : ngs[i] - oks[i]) > T{1}) {
            T mid = (oks[i]&ngs[i]) + ((oks[i]^ngs[i])>>1);
            inv[i] = remains.size();
            remains.push_back({mid, i});
        }
        if (remains.empty()) break;
        auto res = f(remains);
        assert(res.size() == remains.size());
        for (usize i = 0 ; i < res.size() ; i++) {
            T mid = remains[inv[res[i].second]].first;
            if (res[i].first) oks[res[i].second] = mid;
            else ngs[res[i].second] = mid;
            i++;
        }
    } 
    return oks;
}

} // namespace zawa

#line 2 "Src/Utility/ParallelBinarySearch.hpp"

#include <cassert>
#include <concepts>
#include <utility>
#include <vector>

namespace zawa {

template <std::integral T, class F>
std::vector<T> ParallelBinarySearch(std::vector<T> oks, std::vector<T> ngs, F f) {
    assert(oks.size() == ngs.size());
    while (true) {
        std::vector<std::pair<T, usize>> remains; 
        std::vector<usize> inv(oks.size(), static_cast<usize>(-1));
        for (usize i = 0 ; i < oks.size() ; i++) if ((oks[i] >= ngs[i] ? oks[i] - ngs[i] : ngs[i] - oks[i]) > T{1}) {
            T mid = (oks[i]&ngs[i]) + ((oks[i]^ngs[i])>>1);
            inv[i] = remains.size();
            remains.push_back({mid, i});
        }
        if (remains.empty()) break;
        auto res = f(remains);
        assert(res.size() == remains.size());
        for (usize i = 0 ; i < res.size() ; i++) {
            T mid = remains[inv[res[i].second]].first;
            if (res[i].first) oks[res[i].second] = mid;
            else ngs[res[i].second] = mid;
            i++;
        }
    } 
    return oks;
}

} // namespace zawa

Back to top page