Блог пользователя PerryThePlaytypus

Автор PerryThePlaytypus, история, 20 месяцев назад, По-английски

How would I use these functions for pairs? I mean if I have a pair {a,b} and I would like a pair p = {c,d} such that a < c and b < d. The traditional lower_bound and upper_bound functions only give us a pair whose first value 'c' is greater or equal to 'a' and it doesn't care about b and d. Can I get the former in O(logN)?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

This is not solvable for lower_bound / upper_bound, because you cannot sort an array that satisfy a < c and b < d for all pairs. You should use Segment Tree instead