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

Need idea to solve LightOj -1089
Автор darkprinx, 10 лет назад, По-английски

i started to thinking about segment tree to solve this problem.

LightOj -1089

But after i noticed the range [0, 10^8], i just stucked there and couldn't managed how to solve it. please help ... thnx in advance :) :)

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

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

But after i noticed the range [0, 10^8], i just stucked there and couldn't managed how to solve it

You have to think about the amount of distinct numbers you have (at most: 2 × 50 000 for the ranges, plus 50 000 for the query points).

For example, if I give you these ranges: [1, 60 000 000], [40 000 000, 90 000 000] and these query points: 1 000 000, 50 000 000, 100 000 000, then you can reduce the problem (without changing the final answer) to a smaller problem. In this case, the ranges become: [1, 5], [3, 6], and the query points become: 2, 4, 7. For "both problems", the answers are 1, 2, 0.

P.S. note that (once you solved the "reduction" part) you can solve this problem also by using a binary indexed tree (with a trick I explained here) which can be easier than a range tree.

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

    I don't understand how to do the reduction part. How you reduce this one -> [1, 60 000 000], [40 000 000, 90 000 000] and these query points: 1 000 000, 50 000 000, 100 000 000 to this one [1, 5], [3, 6], and the query points become: 2, 4, 7 Both are quite different. isn't it?

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

      To compress numbers you can replace a certain number with its index in sorted array, for example: [1, 6, 28, 5], sorted array is [1, 5, 6, 28], so you will get new array [0, 2, 3, 1], don't forget that equal numbers must be equal in new array too.

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

The problem can easily be solved using upper_bound and lower_bound . Just sort up the left points in a vector and the right point in another vector

→ Ответить