min_leftとmax_rightの仕組みと実装を理解する

template<typename F>
BinarySearchResult max_right (F f, int l) {
    assert(0 <= l && l < length);

    // コーナーケースを回避するために、
    // 1. 右端まで全て含んでtrue
    // 2. A[l]の時点でfalse
    // となるケースをはじく。
    if (f(prod(l, length))) {
        return BinarySearchResult(length - 1);
    }
    if (!f(prod(l, l + 1))) {
        return BinarySearchResult();
    }

    l += modified_length - 1;
    T acc{};

    // r + 1を含む区間が見つかるまで登る。
    while (true) {
        // 真上に登るとA[l]より左の要素を含むセグメントに行ってしまうため、
        // 自分を確定させて右にずらす。
        if (l % 2 == 0) {
            acc += node[l];
            l++;
        }
        // 登る。
        l = (l - 1) / 2;

        // r + 1を含む区間が見つかった。
        if (!f(acc + node[l])) {
            break;
        }
    }

    // 今見ているセグメントが最下層にたどり着くまで降り続ける。
    while (l < modified_length - 1) {
        // どちらかのセグメントに進む。
        if (f(acc + node[2 * l + 1])) {
            acc += node[2 * l + 1];
            l = 2 * l + 2;
        }
        else {
            l = 2 * l + 1;
        }
    }

    l -= modified_length - 1;
    // 求めるrはたどり着いたセグメントのひとつ左にある。
    return BinarySearchResult(l - 1);
}

#include <cassert>
#include <vector>

struct BinarySearchResult {
    const bool empty_payload;
    const int value_payload;

    BinarySearchResult (): empty_payload(true), value_payload() {}
    BinarySearchResult (int border): empty_payload(false), value_payload(border) {}

    bool empty () {
        return empty_payload;
    }

    int value () {
        assert(!empty());
        return value_payload;
    }
};

template<typename T>
struct RSQSegmentTree {
    int length{};
    int modified_length{};
    std::vector<T> node{};

    RSQSegmentTree (int length_) {
        assert(1 <= length_);
        length = length_;
        modified_length = 1;
        while (modified_length < length) {
            modified_length *= 2;
        }

        node.resize(2 * modified_length - 1);
    }

    T get (int i) {
        assert(0 <= i && i < length);
        return node[modified_length - 1 + i];
    }

    void set (int i, T value) {
        assert(0 <= i && i < length);

        int cur = modified_length - 1 + i;
        node[cur] = value;

        while (0 < cur) {
            cur = (cur - 1) / 2;
            node[cur] = node[2 * cur + 1] + node[2 * cur + 2];
        }
    }

    T prod (int l, int r) {
        assert(0 <= l && l < length);
        assert(0 <= r && r <= length);
        assert(l <= r);

        if (l == r) {
            return T{};
        }

        // 閉区間へ変換
        l += modified_length - 1;
        r += modified_length - 1 - 1;

        T ret{};
        while (l < r) {
            if (l % 2 == 0) {
                ret += node[l];
                l++;
            }
            if (r % 2 == 1) {
                ret += node[r];
                r--;
            }

            l = (l - 1) / 2;
            r = (r - 1) / 2;
        }

        if (l == r) {
            ret += node[l];
        }

        return ret;
    }

    template<typename F>
    BinarySearchResult max_right (F f, int l) {
        assert(0 <= l && l < length);
        if (f(prod(l, length))) {
            return BinarySearchResult(length - 1);
        }
        if (!f(prod(l, l + 1))) {
            return BinarySearchResult();
        }

        l += modified_length - 1;
        T acc{};

        while (true) {
            if (l % 2 == 0) {
                acc += node[l];
                l++;
            }
            l = (l - 1) / 2;

            if (!f(acc + node[l])) {
                break;
            }
        }

        while (l < modified_length - 1) {
            if (f(acc + node[2 * l + 1])) {
                acc += node[2 * l + 1];
                l = 2 * l + 2;
            }
            else {
                l = 2 * l + 1;
            }
        }

        l -= modified_length - 1;
        return BinarySearchResult(l - 1);
    }

    template<typename F>
    BinarySearchResult min_left (F f, int r) {
        assert(0 <= r && r < length);
        if (f(prod(0, r + 1))) {
            return BinarySearchResult(0);
        }
        if (!f(prod(r, r + 1))) {
            return BinarySearchResult();
        }

        r += modified_length - 1;
        T acc{};

        while (true) {
            if (r % 2 == 1) {
                acc += node[r];
                r--;
            }
            r = (r - 1) / 2;

            if (!f(acc + node[r])) {
                break;
            }
        }

        while (r < modified_length - 1) {
            if (f(acc + node[2 * r + 2])) {
                acc += node[2 * r + 2];
                r = 2 * r + 1;
            }
            else {
                r = 2 * r + 2;
            }
        }

        r -= modified_length - 1;
        return BinarySearchResult(r + 1);
    }
};