Problem Link:Difficulty:Medium Prerequisites:linesweep, rankquery DS Problem:Given N points (Xi, Yi), and Q queries (x, y, d), find for each query how many of the N points lie within or on the boundary of the triangle formed by the triangle A(x+d, y), B(x,y), C(x,y+d). Explanation:This problem is solved by offline processing of the queries and using a linesweep. Unlike most linesweep problems, where you would sweep a (vertical) line across the Xaxis (or a horizontal line across the Yaxis), and keep an active set etc, in this problem, you sweep a line of the form "x+y=c" across the plane. (Note that the slope of the hypotenuse of our querytriangle is parallel to such a sweepline and hence the motivation for such a choice). In the figure shown, we want to find the number of points in or within the boundary of L2, B and G. If we are processing lattice points in the plane in order of sweepline, and have so far seen points below L2, we just need to remove from this set of seen points, the ones that are below G or to the left of B. This suggests that we have an active set of "seen points", wherein at time T, their X+Y <= T (i.e. T defines our sweepline). From this set of seen points, we want to remove those whose X <= x, or whose Y <= y. If we store the seen points in 2 Binary Indexed Trees (BIT): one for their X coordinate, one for their Y coordinate, and query for how many points <= x, or <= y, then using principle of inclusionexclusion, we get that the required answer = Total seen points  num(points left of B)  num(points below G) + num(points left of B and below G). How do we find num(points left of B and below G)? Thus, our algorithm is as follows: Finally, care has to be taken to ensure that we include the boundary of our triangle formed by B, G, L2. This is done by breaking ties of timepoint in the manner of L1type event comes before any Addpoint event which comes before any L2type event. Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 12 Feb '13, 18:20

Can't this problem also be solved by doing an orthogonal range search in 3 dimensions (between (x, y, x+y) and (x+d, y+d, x+y+d)) using range trees or kd trees? Something like this http://www.codechef.com/viewsolution/1809831 (kdtree, TLE, Complexity is q*(n^2/3)) Range trees with fractional cascading could solve this in O(q*((log(n))^2)) answered 13 Feb '13, 07:06

I tried to solve this in online mode: i stored count of points on different lines parallel to x+y=0 on query of (x,y,d) we can find points to the left of B and below G (as used in editorial) by using two segment trees. each segment tree is built with (level,x) and (level,y) correspondence (level is line no. with respect to x+y=0) i couldn't get rid of RTE in my submission but is this method good enough for this problem...?? answered 12 Feb '13, 21:47
@code_master01 I tried same logic too I am getting RTE too :(...
(13 Feb '13, 12:11)

Could somebody please tell me what do we mean by offline processing of points? And also why was I getting a runtime error in my code http://www.codechef.com/viewsolution/1802839 answered 12 Feb '13, 23:12
1
offline mode means that you "don't" calculate your answer of every input query separately but either you do some preprocesing before taking input or you take all the input and find answer to the all queries at the same time. [here same time means like you are going though the input queries and finding "half" answer to some queries and then coming back again and again]
(23 Feb '13, 12:35)

answered 12 Feb '13, 23:25
Your solution has complexity
(13 Feb '13, 00:58)
How to run it with N=3e5 and Q=2e5?
(14 Feb '13, 17:39)
I meant how to manually create such a test file.
(14 Feb '13, 17:54)
This is the code for manually creating a test file
(14 Feb '13, 21:19)
then direct the output of this program to the input of ur program. where input.txt is text file generated from the above code. ./a.out <input.txt
(14 Feb '13, 21:22)
Hey Jas, not like this. I know the direct(./a.out < input.txt) thing, but I want huge random tests. Not in a serial order like this.
(14 Feb '13, 22:13)
showing 5 of 6
show all

Could somebody explain me the update and read functions in the tester's solution? I couldn't get this line
What is the meaning of idx&idx? answered 25 Jun '13, 15:42

Could somebody help me with the editorial? Somebody explain me the update and read functions in the tester's solution? I couldn't get this line
What is the meaning of idx&idx? answered 25 Jun '13, 23:28
1
(25 Jun '13, 23:43)
its idx&idx the bitwise AND operation between idx and its negation
(25 Jun '13, 23:43)
Thanx @sparshgunner12. I finally understood whats happening.
(26 Jun '13, 19:39)

Excellent editorial and tester's solution. answered 26 Jun '13, 19:39

Setter nice and clear solution!
I have a problem here: >"How do we find num(points left of B and below G)? The answer lies in the line L1. When our sweepline was at L1, we have: Total number of points seen so far = points either left of B or below G."< I think if L1 sweep means all the points below this line in the diagram then it is "not" equal to the "points on the left of B or below G" because there can be some point b/w L2 and L1 and on the left of B which are not covered by L1 sweep. same for b/w L2 and L1 and below G. please clarify. Please also clarify the definition of linesweep.
got it. :) For this part of problem (refer above comment), it is a completely new BIT which is calculated from points and queries sorted by their x coordinate. see Setter's solution for clarification.