Mo's Algorithm with extra backtracking Problem

Revision en2, by Bungmint, 2021-07-05 22:52:32

I was trying to solve this problem on CodeChef, QCHEF, using Mo's algorithm and realized it is not so simple to come up with a data structure that can save previous results, so that you can simply obtain the result after deletion. I looked up how to maintain previous results, and found this nice comment, link, where it describes this abstract notion on how one could have one function, snapshot(), for saving the current results, and another function, rollback() to go back to the previous state. I tried to implement this, code below, but it failed miserably. Any help would be appreciated.

UPD: Apparently I had a typo in one of the add functions, and fixing that immediately solved the problem lol.

Code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Bungmint 2021-07-05 22:52:32 116 Update1
en1 English Bungmint 2021-07-05 21:42:00 5306 Initial revision (published)