onlydmc123's blog

Cant Solve Timus Data Structure Problem N1987
By onlydmc123, 9 years ago, In English

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

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

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

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

      I didn't think to this optimization...

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

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.

→ Reply