You are given n points in the x-y plane and a rectangle of given height and width whose sides are aligned with the coordinate axes. You need to tell if you are allowed to translate the rectangle parallel to the axes what is the maximum no of points that can lie inside the rectangle at any point in time.
Yesterday, I quickly realized that the ABC's problem F was essentially this but could not find an optimal solution.
problem link doesn't work
I think we can use segment tree with Lazy Propagation. Here's how I m thinking. I will iterate along the x-axis,
For any particular window of width w and left endpoint p along x-axis,to get all the points for the next window, i will just remove the points with x-coordinate = p and will add points with x-coordinate = p+w+1.
Now for any new point suppose (x,y) added, i will range update in my segtree [y-h,y] by +1 and for any old point removed suppose (x1,y1), I will range update in my segtree [y1-h,y1] by -1 where h was the height of rectangle.
Now after updation I just want the maximum element.