Need help with a segment tree problem

Revision en1, by 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.

Tags data structure, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English flash_7 2015-08-23 12:33:12 9
en1 English flash_7 2015-08-23 12:31:17 611 Initial revision (published)