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

segments
Автор Butskhrikidze, история, 6 лет назад, По-английски

given $$$n$$$ segments $$$[l_i, r_i]$$$ where $$$-10^9 \leq l, r \leq 10^9$$$. we are given $$$q$$$ query. each query characterized by one integer $$$x$$$. for each query we must determine how many segment involves $$$x$$$ and detect segments itself by its number. How to solve this problem?

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

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

If I understand the question correctly we can use the following offline approach:

for each segment [l,r] store it as pair <l , -1> and <r , 1>. for each query store point as pair <x, 0> in the same vector / array.

Sort this structure and maintain a count of currently active segments by adding 1 on <t, -1> entities and subtracting 1 on <t, 1> entities. Answer for each <t, 0> entity is number of active segments.

Could you clarify what you mean by "detect segments itself by its number". If this means listing all segments corresponding to a query then output itself can be $$$O(NQ)$$$ big in worst case.

→ Ответить