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

Cant Solve Timus Data Structure Problem N1987
Автор onlydmc123, 10 лет назад, По-английски

Can someone help me? In Discussion people said they solved in O(m*logn), is there O(n+m) solution too? If you can, give me ideas of both solutions. http://acm.timus.ru/problem.aspx?space=1&num=1987

Thanks

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

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

I solved it in O(m*logn), the idea is to keep a set of active segments, sorted by lenght using a priority queue. Since queries are sorted we can also sort segments by their starting point. Now we can process queries one by one, each time we add segments that start before the point of the query and delete segments that end before the point of the query. Since we add and delete at most once each segment to the priority queue the running time is O(m*logn)

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

    Actually, you even don't need priority queue, You can do it in O(n + m) with stack. You should notice that all right ends of active segments are sorted in ascending order. So all you need is just push right end of segment to stack when you face it, and pop once, so answer for query is O(1), totally O(n + m) (1 add, 1 delete for every segment).

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

Another way you can sovle it is segment tree. You can store in node index of segment covering current interval (last index, since they sorted). So if you want to get index for query X, at current node you first check appropriate son, whether there is some smaller segment, if not, you take answer from current node. For preventing ML you can create nodes only where you need it(because queries in [1, 109]), in that case you'll be needed O(n * log(n)) memory.

→ Ответить