PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
If we find some losing position (x0, y0) then all points on the same row and column will be winning and all points on its diagonal for which x have the same residue as x0 modulo d will be winning. Call this residue winning for this diagonal. Hence in each row and each column we have exactly one losing position. So we will have at most N losing positions in the square 1 <= x <= N, 1 <= y <= N. In order to find them efficiently let store for each diagonal all residues that is not already winning and also maintain the first not winning diagonal (where at least one not winning residue is left) and the first not winning row. Then at each step we will find the new losing position simply iterating from maximal of first not winning row and first not winning diagonal until we find the free point. By direct running of this approach it can be shown that for N <= 200000 and d <= 20 it performs at most 8 * N operations for inner iterating. It is clear that all other stuff is linear here.
Now we talk about how to answer the queries. Each query is equivalent to 4 queries for rectangles with one of the corner in (0,0). Let’s sort all queries by x. In binary indexed tree (BIT) we maintain for each y the number of losing positions that has this y and x <= xcur where xcur is the x of the current query. Then answer to the query (xcur, ycur) is the sum of first ycur elements of out BIT and can be found in O(log N) time. Before processing queries with x = xcur we need to add losing position with x = xcur to our BIT. And this also can be done in O(log N) time.
Thus we obtain an algorithm with complexity O(N log N).
Problem tester has noted an interesting fact about this game. If (x, y) is the losing position and x > y then there are no losing positions (a, b) such that x > a > b > y + d. This fact allows us to answer the query in O(d) time if we precalculate the number of losing positions in squares 1 <= x <= n, 1 <= y <= n for all n. See its solution as a reference for this approach.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.