lower_bound и upper_bound в C++: чем отличаются и какие частые грабли?

Для отсортированного диапазона:

• lower_bound(first, last, x) → итератор на первый элемент >= x (первая позиция, куда можно вставить x, не нарушив порядок, левее равных).
• upper_bound(first, last, x) → итератор на первый элемент > x (вставка правее равных).

Отсюда полезные формулы:

• Число элементов, равных x: upper_bound(...) - lower_bound(...).
• Число элементов < x: lower_bound(...) - begin.
• Число <= x: upper_bound(...) - begin.

vector<int> a = {1, 2, 2, 2, 5};
int lt2  = lower_bound(a.begin(), a.end(), 2) - a.begin(); // 1 (индекс первого 2)
int gt2  = upper_bound(a.begin(), a.end(), 2) - a.begin(); // 4
int cnt2 = gt2 - lt2; // 3 — сколько двоек

Сложность O(log n) для random-access итераторов (vector, array).

Грабля с set. Свободные функции std::lower_bound(s.begin(), s.end(), x) на set дают O(n)! Итераторы set — bidirectional, а не random-access, поэтому std::lower_bound делает O(log n) сравнений, но O(n) шагов итератора. Используй методы-члены: s.lower_bound(x) и s.upper_bound(x) — они O(log n) по дереву. То же для map. Это классический источник скрытого TLE.