Let ~R_i~ denote the total XOR of all rooks located in row ~i~. Analogously, we define ~C_i~ as the total XOR of all rooks located in the column ~i~. Let us notice that the total number of attacked fields is equal to the number of pairs ~(i, j)~ such that ~R_i \ne C_j~ (this is a direct consequence of the fact that the field ~(i, j)~ is attacked if and only if the total XOR in row ~i~ is different than the total XOR in column ~j~).

In the beginning, we can calculate for each ~k~ how many rows ~i~ there are such that ~R_i = k~, and how many columns ~j~ there are such that ~C_j = k~. It is easy to calculate the number of attacked fields with this information.

When a move occurs, we need to be able to efficiently calculate the change in the number of attacked fields. When a rook moves from field ~(r, c)~, we calculate the number of attacked fields in row ~r~ or column ~c~ and subtract it from the total number of attacked fields. When a rook moves to field ~(r, c)~, we calculate the number of attacked fields in row ~r~ or column ~c~ and add it to the total number of attacked fields.

If we use a binary tree (e.g. map in C++) for storing the data, the total time complexity of this algorithm is ~\mathcal O(Q \log N)~, and the memory complexity ~\mathcal O(N)~.