When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

coding_is_fun's blog

By coding_is_fun, 6 years ago, In English

UPDATE : I got a Qlog2(N) solution

Given a number N . then N lines follows some segment L[i] R[i] , where L[i] = left side of segment , R[i]= right side of segment

N

L1 R1

L2 R2

. . . . . .

LN RN

Then Given Q queries . Then Q lines as follows .

Q

X1

X2

X3 .

.

XQ

For each query you have to answer how many Segment are including the value Xi ( X >= L[i] && X <= R[i] )

Constraint :

1<=N<=10^5

0<=Li , Ri <= 10^9

1<=Q<=10^5

0<=Xi<=10^9

Sample input:

4

1 6

3 7

5 9

6 9

1

8

Sample output:

2

Explanation : 3rd segment 5-9 , 4th segment 6-9 both including 8 . Because : 8>=5 && 8<=9 , 8>=6 && 8<=9 . So ans is 2 .

How to solve it efficiently ?

My binary search solution
My O( Qlog(N) ) solution
  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Always give problem link.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I may be wrong but as far as I have seen other's solution, I haven't seen anyone writing binary search like this. you have written as while(high-low>1) but generally all people write while(low<=high) as the first one might get into infinite loop.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have an offline solution although it doesn't involve segment tree its complexity is better then whats proposed in the blog. O(N log N + Q log N). The main idea is to sort all the ranges and as well as all the queries. After that its kind of sliding window. We will maintain a priority queue. We will process queries sorted in ascending order. Suppose a range is defined by L, R and Qi is current query then we will insert all R into min priority queue PQ for which L<Qi and pop out from PQ while PQ.top()<Qi. Ans for the current query will be the size of the priority queue.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my solution, but I am not sure whether it is correct or not.

At first, for the given N segment lines, we should reduce (or compress) their ranges to [1, 2e+5]. In other words, we just "remap" the ending points of every segment line to some integer belonging to [1, 2e+5]. If you are familiar with C++, you can use "map" provided in STL.

Next, for the 1e+5 queries, we use binary search to find out the minimum value of Ri or Li that is not less than Xi. Specifically, we implement binary search in L1, R1, L2, R2, ..., LN, RN to find out the minimum value which is larger than or equal to Xi.

Then, for any segment that contain point Xi, it must contain Ri as well, which can be proved by contradiction. Now, the original problem is reduced to find out the number of segment lines that contain Ri. This can be solved by using prefix idea. We adopt an array a[2N], and set a[Li] = 1 while a[Ri + 1] =  - 1. Furthermore, we adopt another array S[2N] to calculate the prefix sum of a[2N]. Then, the value of S[Ri] is just the number of segment lines that contain point Ri.

Building a[2N] and S[2N] has complexity O(N), and implementing binary search has complexity O(logN). Thus, the total complexity turns out to be O(QlogN).

I am not quite confident of the above solution...