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

Need help with a segment tree problem
Автор flash_7, история, 9 лет назад, По-английски

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.

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

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

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 :)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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://codeforces.me/blog/entry/19080 :)

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 :)

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить