絶滅

どうでもいい

lower_bound と upper_bound の関数バージョン

はい

配列や vector であれば STL の lower_bound や upper_bound を使えという話ですが,関数となるとベタ書きするしかないっぽい (他に方法あれば教えてください).
ウンチ・コーダーの自分はよく終了条件をバグらせて死ぬので,この際スニペットに lower_bound と upper_bound の関数を登録してしまうことにした.




lower_bound
// 関数 func に対して,func(x) が val 以上となる最初の x を取得する
template<typename Ty> Ty func_lower_bound(Ty first, Ty last, Ty val) {
    Ty mid;
    while (last - first > 1) {
        mid = first + (last - first) / 2;
        (func(mid) < val ? first : last) = mid;
    }
    return func(first) < val ? last : first;
}


upper_bound
// 関数 func に対して,func(x) が val より大きくなる最初の x を取得する
template<typename Ty> Ty func_upper_bound(Ty first, Ty last, Ty val) {
    Ty mid;
    while (last - first > 1) {
        mid = first + (last - first) / 2;
        (func(mid) <= val ? first : last) = mid;
    }
    return func(first) <= val ? last : first;
}



動作?ウンチ・コーダーなので保証しません.
本当は func の部分もテンプレート化したかったけど,これもウンチ・コーダーなので無理でした.



余談:ここ の FindMaximal には本当にお世話になっている.