I couldn't solve this. Please do tell me any simple approach which can pass the time constraint.↵
↵
**Problem:**↵
↵
You are given n intervals which are termed as special intervals. Each interval is of a different type. ↵
↵
Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval. ↵
↵
Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval. ↵
↵
↵
**Input format** ↵
↵
First line: n denoting the number of special intervals ↵
↵
Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.↵
↵
Next line: q denoting the number of non-special intervals↵
↵
Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval. ↵
↵
**Output format** ↵
↵
print q space-seperated integers denoting the answer for each of the q non-special integers.↵
↵
**Constraints**↵
↵
1<=n<=10^5↵
↵
-10^9<=lspecial[i]<=10^9↵
↵
-10^9<=rspecial[i]<=10^9↵
↵
↵
1<=q<= 5 * 10^4↵
↵
-10^9<=lnonspecial[i]<=10^9↵
↵
-10^9<=rnonspecial[i]<=10^9↵
↵
↵
**Sample Input**↵
↵
3↵
↵
1 2↵
↵
1 5↵
↵
1 7↵
↵
3↵
↵
1 3↵
↵
3 3↵
↵
6 7↵
↵
**Sample Output**↵
↵
3 2 1↵
↵
**Time Limit**↵
1 second↵
↵
**Problem:**↵
↵
You are given n intervals which are termed as special intervals. Each interval is of a different type. ↵
↵
Again, you are given a set of q non-special intervals. For each non-special interval in the given q intervals, you have to find the number of different types of special intervals in that non-special interval. ↵
↵
Note: A special interval is inside a non-special interval if there exists a point x which belongs to both special interval and non-special interval. ↵
↵
↵
**Input format** ↵
↵
First line: n denoting the number of special intervals ↵
↵
Next n lines: Two integers denoting lspecial[i] and rspecial[i] denoting the range [l,r] for the ith special interval.↵
↵
Next line: q denoting the number of non-special intervals↵
↵
Next q lines: Two integers denoting lnonspecial[i] and rnonspecial[i] denoting the range [l,r] for the ith non-special interval. ↵
↵
**Output format** ↵
↵
print q space-seperated integers denoting the answer for each of the q non-special integers.↵
↵
**Constraints**↵
↵
1<=n<=10^5↵
↵
-10^9<=lspecial[i]<=10^9↵
↵
-10^9<=rspecial[i]<=10^9↵
↵
↵
1<=q<= 5 * 10^4↵
↵
-10^9<=lnonspecial[i]<=10^9↵
↵
-10^9<=rnonspecial[i]<=10^9↵
↵
↵
**Sample Input**↵
↵
3↵
↵
1 2↵
↵
1 5↵
↵
1 7↵
↵
3↵
↵
1 3↵
↵
3 3↵
↵
6 7↵
↵
**Sample Output**↵
↵
3 2 1↵
↵
**Time Limit**↵
1 second↵
