i have used (using two references: https://www.geeksforgeeks.org/number-of-intersections-between-two-ranges/ and Kth smallest element in a subarray - GeeksforGeeks) but failed to score 70% … one subtask got TLE (2.01xxx) … i have seen a comment which says BIT can solve this… so i want 2 know whether it’s possible to convert every segment tree based approach to BIT?
Visualization: Imagine a vertical line falling from y = infinity
Precomputation: Arrange all lazers and queries in a single queue in decreasing order of y co-ordinate.
Solution: When the falling vertical line hits a lazer at x = i, y = A[i], update seg tree from (i-1, A[i-1]) to (i+1, A[i+1]) with relevant addition or subtraction.
When you hit a query, just get the solution 
1 Like
Welcome to the community! Yes as far as point updates are concerned (Eg: given A[L…R] count zeros/find sum) etc…BIT and segment tree can be interconverted.As far as analysis of intervals and consequent queries are concerned (Eg Merge sort tree/Interval tree/Wavelet tree) using segment tree is efficient. For example : " There is no easy way of finding minimum of range [l,r] using Fenwick tree, as Fenwick tree can only answer queries of type [0,r]".(Quoted in Fenwick Tree - Algorithms for Competitive Programming) You need to use 2 BITS here and read some research paper to solely solve it using a BIT and trust me it will be cumbersome.
Nice approach…You are directly storing the counter as key in the segment tree right?
can we use line segment orentation to solve atleast first subtask of the problem
For the first subtask you can use simple quadratic equation : with condition :
(y-a[i])(y-a[i+1])<=0 for i belonging from [x1,x2). This is the necessary and sufficient condition for a line y to intersect a segment between (i,a[i]) and (i+1,a[i+1]). Just think, for intersection we need both points on opposite sides of the line, so difference in heights of line segments should be negative…simple brute force approach : (y-a[i])(y-a[i+1])<=0 
Here is the link: CodeChef: Practical coding for everyone
I used Segment Trees for solving the problem .However it was required to do small small optimizations to get AC in all tasks like using postfix operators etc.
MY C++ SOLUTION : Online Compiler and IDE - GeeksforGeeks
1 Like
My approach is fairly simple and I believe somewhat different than many others.
-
Observe that # of intersection in range [x1, x2] for some y will be as equal as
no. of intersection from [0, x2] - no. of intersection from [0, x1] for same y.
Let first part be ans2 and second part be ans1. We will maintain both answers for each query. -
Now we will move from 0 to n along x-direction. For each increment in i, a new segment
having endpoints (i-1, y1) and (i, y2) will get added. -
Maintain an array for y values and increment range [y1, y2] by 1, cuz for any ‘y’ belonging
to range [y1, y2] there will be an intersection from now onwards as we are considering lazer to be fired from y-axis i.e x = 0. Calculate ans1 and ans2 for queries starting and ending at current i respectively. -
But, 1 <= y <= 1e9 which doesn’t allow to range increment and query on y. But their can be at most 2*n distinct values of y (n from given + n from queries). For that I compressed values of y using coordinate compression and always used mapped values of y whenever needed.
my solution
4 Likes
Yes its different and more efficient I guess.
1 Like
Yes your approach is really awesome!
But can you elaborate what ans1 and ans2 does?
The link is not your approach but your code. If you are sharing it as your approach then at least include the comments in your code.
1 Like
For any query (x1, x2, y), ans1 stores answer for query(0, x1, y) and ans2 stores answer for query(0, x2, y). So our final answer becomes (ans2 - ans1) which will be storing answer for query (x1, x2, y).
Kind of inclusion and exclusion on the count of intersection.
Updated my solution with comments.
1 Like
Thanks. You had already explained your method. I asked for the comments from the main author of the post. But thanks ,now your answer code is really very simple to understand.
1 Like
Awesome approach!
1 Like
I solved it using policy based data structures (my solution here). Did anybody else use this same approach?
1 Like
I thought about it during the contest but was too lazy to study PBDS. It is also kind of an overkill for this question i guess 
Can you share some good resources to learn it?
Excellent solution. Interestingly, I thought of this approach, but could not optimize the algo/code properly.
1 Like
I mean all you have to do is type the header files and initialiser and you get a data structure that supports addition, deletion, find, and no. of elements less than given x in log n time. Basically set, but better.
2 Likes