Editorial for COCI '15 Contest 1 #4 Topovi
Submitting an official solution before solving the problem yourself is a bannable offence.
Let denote the total XOR of all rooks located in row
. Analogously, we define
as the total XOR of all rooks located in the column
. Let us notice that the total number of attacked fields is equal to the number of pairs
such that
(this is a direct consequence of the fact that the field
is attacked if and only if the total XOR in row
is different than the total XOR in column
).
In the beginning, we can calculate for each how many rows
there are such that
, and how many columns
there are such that
. 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 , we calculate the number of attacked fields in row
or column
and subtract it from the total number of attacked fields. When a rook moves to field
, we calculate the number of attacked fields in row
or column
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 , and the memory complexity
.
Comments