配列の中でA以上B以下の要素の数などを簡単に求める

range_count.cpp

// startは含む
// endは含まない
RangeCount range_count(vector<int>::iterator start, vector<int>::iterator end, int l, int r) {
    if (l > r) return RangeCount{0, 0, 0, 0, 0};
    if (start >= end) return RangeCount{0, 0, 0, 0, 0};

    if (l == r) {
        RangeCount rc;
        auto it_u = upper_bound(start, end, r);
        auto it_l = lower_bound(start, end, r);

        rc.upper = distance(it_u, end);
        rc.r_equal = distance(it_l, it_u);
        rc.between = 0;
        rc.l_equal = rc.r_equal;
        rc.lower = distance(start, it_l);

        return rc;
    }

    RangeCount rc;
    auto it_ru = upper_bound(start, end, r);
    auto it_rl = lower_bound(start, end, r);
    rc.upper = distance(it_ru, end);
    rc.r_equal = distance(it_rl, it_ru);
    auto it_lu = upper_bound(start, end, l);
    auto it_ll = lower_bound(start, end, l);
    rc.between = distance(it_lu, it_rl);
    rc.l_equal = distance(it_ll, it_lu);
    rc.lower = distance(start, it_ll);

    return rc;

}