Hello,

I don't quite understand the editorial to Mowing the Field (http://www.usaco.org/index.php?page=viewproblem2&cpid=601). The solution they gave here (http://www.usaco.org/current/data/sol_mowing_platinum_jan16.html) claims that you can answer the range queries in originally log(n)^3 time. However, I don't understand why. For a specific vertical segment i, we want to find how many times it intersects a horizontal segment. I see how we can use a range query tree for the conditions y_i^b < y_j < y_i^t and abs(t_i — t_j) >= T. But I don't see how the range query tree can solve the part x_j^l < x_i < x_j^r as you're querying with i. In addition, I'm not quite clear on how you can update the range tree without having to update at each point on each horizontal line. Can anybody provide some help with these questions?

Edit: I have thought about this some more, and there is no way that I can think of to not have a n^2 on the complexity besides incorporating some for of line sweep. If I am wrong, can someone point out how to remove the n^2 with just the range tree as it says in the editorial without the use of a line sweep?

-dx24816