aarcee's blog

Need help for the following problem
By aarcee, history, 6 years ago, In English

Problem Link here

Brief Explanation:

  • Given n segments with their left and right end points on OX-axis.
  • You are given q queries where each query starts with an integer m followed by m integers(points).
  • The answer to the query is the number of segments, such that each of them contains at least one point from the query.

My Approach:

  • Sort the given points in the query.
  • Start from the leftmost point
  • For the first point find the number of segments which contain this point and add to the sum.(Finding the number of segments which contain this point or not can be done with binary search)
  • For the second point we do the same as done for the first point but subtract the number of segments which contain the segment [first, second] as they are already counted for the first point.
  • Similarly for the third point we find the number of segments which contain this point and subtract the number of segments which contain the segment [second, third] as they are already counted for the first and second points.
  • Similarly for the ith point we find the number of segments which contain this point and subtract the number of segments which contain the segment [i — 1, i].

But I am not able to figure out a way to find the number of segments out of given n segments which contain a specific range(segment) from [L, R] in logn time.Is there a way to find it out??

Please say me if some part of my approach seems wrong or if you have some different solution.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

You can sort the n intervals by their left end points and create an array of size n storing the right end points for each left end point. Finding out the number of intervals containing [l,r] is equivalent to counting the number of integers >=r in some prefix of this array (precisely till the last left end point <=l). This is a very standard problem that can be done offline with BIT or online with persistent segment tree.

Also have a look at the Editorial for an alternate solution.

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

    Thanks a lot. I got an idea of doing it with persistent segment tree but the constraint of 10^6 on l and r seems too big for it.Can you explain me the BIT approach.

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

      You don't actually need an array of size 1e6 for persistent seg tree. You can use coordinate compression and map the values in range 0 to n. In this way you can solve for 1e9 constraints too.

      Here's the BIT approach:

      Suppose you have an array A of n numbers and queries for finding number of integers greater than p in subarray i to j. This is an offline approach. Sort all the queries by p. Create an array B of size n consisting of all zeros. Process queries in decreasing values of p. Mark 1 on all the indices of B for numbers in A which are >=p. Now you only need the subarray sum [i,j] in array B for each query.

      → Reply