### coding_is_fun's blog

By coding_is_fun, 11 months ago, ,

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

•
• -8
•

 » 11 months ago, # |   +5 Always give problem link.
•  » » 11 months ago, # ^ |   0 This problem made by me . I dont know is there any similar type of problem ? I got the problem idea from here : http://www.lightoj.com/volume_showproblem.php?problem=1088
 » 11 months ago, # |   0 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.
 » 11 months ago, # |   0 Auto comment: topic has been updated by Sleep_Lover (previous revision, new revision, compare).
 » 11 months ago, # |   0 Sorry in input i missed a newline so Q=1 and Xi=8 shown in the same line . 41 63 75 96 918
 » 11 months ago, # |   0 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
 » 11 months ago, # |   0 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...
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 I used the technique which has been used in this problem ( Two Tv's http://codeforces.com/problemset/problem/845/C ) MY QlogN solution#includeusing namespace std;#define debug(...) printf( VA_ARGS )//#define debug(...) /****nothing****/#define pb push_back#define mp make_pair#define LL long longint n,q,xi,ans;pair ar[200000];int main(){ while(cin>>n) { vector > vct; for(int i=1;i<=n;i++) { scanf("%d %d",&ar[i].first,&ar[i].second) ; vct.push_back(make_pair(ar[i].first,1)) ; vct.push_back(make_pair(ar[i].second+1,-1)) ; } sort(vct.begin(),vct.end()); int cnt=0; map val; for(int i=0;i>q; while(q--) { scanf("%d",&xi); map::iterator it=val.upper_bound(xi); it--; printf("%d\n",it->second); } } return 0;}I used the technique which has been used in this problem ( Two Tv's http://codeforces.com/problemset/problem/845/C )
 » 11 months ago, # |   +5
•  » » 11 months ago, # ^ |   0 I used the technique which has been used in this problem ( Two Tv's http://codeforces.com/problemset/problem/845/C ) MY QlogN solution#includeusing namespace std;#define debug(...) printf( VA_ARGS )//#define debug(...) /****nothing****/#define pb push_back#define mp make_pair#define LL long longint n,q,xi,ans;pair ar[200000];int main(){ while(cin>>n) { vector > vct; for(int i=1;i<=n;i++) { scanf("%d %d",&ar[i].first,&ar[i].second) ; vct.push_back(make_pair(ar[i].first,1)) ; vct.push_back(make_pair(ar[i].second+1,-1)) ; } sort(vct.begin(),vct.end()); int cnt=0; map val; for(int i=0;i>q; while(q--) { scanf("%d",&xi); map::iterator it=val.upper_bound(xi); it--; printf("%d\n",it->second); } } return 0;}I used the technique which has been used in this problem ( Two Tv's http://codeforces.com/problemset/problem/845/C )
 » 9 months ago, # |   0 this problem is similar to http://lightoj.com/volume_showproblem.php?problem=1089