First, we can use string \(T\) to mark all answers either correct or incorrect. The queries simply flip a correct answer into an incorrect answer or vice versa, so we don’t have to worry about \(T\) or the actual answers any more; instead we represent a correct answer with 1 and an incorrect answer with 0.

Note that during the qualifying procedure, all undetermined participants in step \(k\) share the prefix for the bits prior to bit \(k\). This suggests that we can use a bit trie to maintain the number of participants for each possible prefix. To flip a selected answer for a participant then amounts to removing that participant from the trie, then adding them back with the updated bitstring.

(To learn more about tries, see this article; you may ignore the sections from “Construction of an automaton” onwards. A bit trie is simply a trie with an alphabet size of \(2\).)

Initializing the trie takes \(O(NK)\) time. Updating a participant should take \(O(K)\) time, and so should determining whether the participant qualifies after the update. Therefore the solution should run in \(O((N + Q)K)\) time, which is fast enough.