抽象化二分探索
(Algorithm/bisect.hpp)

• View this file on GitHub
• Last update: 2025-01-11 20:14:38+09:00
• Include: #include "Algorithm/bisect.hpp"

概要

抽象化二分探索。
[l, r)の 半開区間 に対して行う

max_right

[l, max_r_plus_one) について、[oooxxx)を想定して二分探索 okになる右端 + 1を返す(全部okならmax_r_plus_oneが帰る)

• なので、「条件を満たす最大値」が欲しい場合、戻り値から-1する必要がある

使用例

min_left

[min_l, r)について、[xxxoooo)を想定して二分探索 okになる左端を返す (全部ngならrを返す) 使用例

イメージ: l,rがoとxの境目になっている。ただし、半開区間を加味しても、探索範囲内が全てo/xになっていた場合、ifで分岐している 両者とも、半開区間に含まれないところにはクエリが来ない

Verified with

• verify/Algorithm_bisect_max_right.test.cpp
• verify/Algorithm_bisect_min_left.test.cpp

Code

template <typename T, typename F> T max_right(T l, T max_r_plus_one, F pred) {
    assert(l < max_r_plus_one);

    if (!pred(l)) return l;

    while (max_r_plus_one > l + 1) {
        T mid = ((l ^ max_r_plus_one) >> 1) + (l & max_r_plus_one);
        (pred(mid) ? l : max_r_plus_one) = mid;
    }
    return max_r_plus_one;
};

template <typename T, typename F> T min_left(T min_l, T r, F pred) {
    assert(min_l < r);

    if (pred(min_l)) return min_l;

    while (r > min_l + 1) {
        T mid = ((min_l ^ r) >> 1) + (min_l & r);
        (pred(mid) ? r : min_l) = mid;
    }
    return r;
}
/*
@brief 抽象化二分探索
@docs doc/bisect.md
*/

#line 1 "Algorithm/bisect.hpp"

template <typename T, typename F> T max_right(T l, T max_r_plus_one, F pred) {
    assert(l < max_r_plus_one);

    if (!pred(l)) return l;

    while (max_r_plus_one > l + 1) {
        T mid = ((l ^ max_r_plus_one) >> 1) + (l & max_r_plus_one);
        (pred(mid) ? l : max_r_plus_one) = mid;
    }
    return max_r_plus_one;
};

template <typename T, typename F> T min_left(T min_l, T r, F pred) {
    assert(min_l < r);

    if (pred(min_l)) return min_l;

    while (r > min_l + 1) {
        T mid = ((min_l ^ r) >> 1) + (min_l & r);
        (pred(mid) ? r : min_l) = mid;
    }
    return r;
}
/*
@brief 抽象化二分探索
@docs doc/bisect.md
*/

Back to top page