Subtask 1 [20%]

This subtask was intended for brute force solutions.

Time Complexity: \(O(RCQ)\)

Subtask 2 [30%]

Note that each cell only has two values, with updates equivalent to a bitwise XOR update. This allows us to keep more general flags as to if some group of cells have been updated.

Treat each row as a distinct group, with each group maintaining a count of poisoned candies and a flag for if this row has been updated. Row updates become a simple flag update, while column updates require you to update each group. Count queries require a sum of each group's count along with their flag.

If \(R > C\), then flip the rows and columns around.

Time Complexity: \(O(Q \cdot \text{min}(R, C))\)

Subtask 3 [50%]

If we maintain flags for each row and column, along with a count of poisoned cells in their base state, we can easily do constant time updates. Count queries can be done by maintaining a general count of poisoned cells and by considering the number of changed poisoned cells every update.

Time Complexity: \(O(Q)\)

Author's Note: The solution noted in subtask 2 is similar to a technique called square root decomposition, where large data structures of \(N\) items are broken down into roughly \(\sqrt{N}\) blocks, each with \(\sqrt{N}\) elements. However, due to the high constraints in this subtask, it is unlikely that any solution using this would pass, as \(O(Q \cdot \text{min}(R, C))\) would require a hundred million operations.