flash_7's blog

Need help with a segment tree problem
By flash_7, history, 9 years ago, In English

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 Some hints on how the problem can be solved using segment tree would be really helpful.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by flash_7 (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

number of seg contain point X == (All segs) — (Number of segs with left endpoint > X) — (Number of segs with right endpoint < X).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Well, isn't this the definition of segment tree? A structure which supports adding V (in out case 1) to each element from L to R and get the sum for some range [L;R] (in our case L=R=Queried number). And since you have only point queries, then Fenwick tree is enough, it uses less space and is fast in practice :) I can't open the link for some reason so you may need coordinate compression if the constraints are big or implement a dynamic segment tree :)

UPD: Now I open the link and the problem you described slightly differs from the original one, however the same solution will work. In the original version you need to answer how many points are in a given segment which has another nice solution using binary search for each query after sorting the points :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks :) But i don't have much idea about dynamic segmeng tree so i'll try to solve it using binary search.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      You can use coordinate compression if you want to use BIT/Segment Tree or read about Dynamic Segment Tree where I asked, there are very good comments — http://mirror.codeforces.com/blog/entry/19080 :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thank you :) I just have solved it using coordinate compression.But that seems like brute force :P I mean after the compression i just run a normal segment tree.So i'll try to learn dynamic segment tree and then will give a try :)

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Create a map m. For each of the segments [a, b], increment m[a] and decrement m[b + 1]. Traverse the map and add each element to the one after it — in other words, convert the map into a partial sum table. Then for each number, just find the largest number less than or equal to it.

→ Reply