Need help with a segment tree problem

Правка en1, от flash_7, 2015-08-23 12:31:17

Given N segments (1-d) and Q numbers, for each of the numbers we have to find the number of segments which contain that number. A number "num" will lie in a segment (A,B) if A ≤ num ≤ B. For example, let the segments are (6 12), (8 8), (10 12), (8 11) and (0 12). Now for any query if the given number is 11(eleven), then the answer is 4.Because the number is contained by 4 segments. Here 1 <= (N,Q) <= 50000 Problem Link : _http://lightoj.com/volume_showproblem.php?problem=1089_ Some hints on how the problem can be solved using segment tree would be really helpful.

Теги data structure, segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский flash_7 2015-08-23 12:33:12 9
en1 Английский flash_7 2015-08-23 12:31:17 611 Initial revision (published)