Hi, I am currently trying an O(n(sqrt n)(lg n)) to problem 375D using Mo's Algorithm and a Fenwick Tree. My initial solution got a time limit exceeded on test case 53, so I tried to optimize it.
To optimize, I made a couple of changes to my check() function, that is called every time the Mo's Algorithm window is slid 1 tree node. I was thinking that this would make the algorithm run faster since check is the part that is run the most (n^1.5 lg n times).
My second submission didn't end up working. In fact, somehow, my new submission got TLE on test case 5, which the previous code could solve in 150ms!
Can someone help me figure out what could've happened that would make this attempted optimization run 10x slower?
Original Submission: http://mirror.codeforces.com/contest/375/submission/18813131
Second Submission: http://mirror.codeforces.com/contest/375/submission/18813311
Diff: https://www.diffchecker.com/nhyeayxp
Thank you very much!
When moving the query window, you can try to remove a color before adding it, which leads to infinite loop in the Fenwick update.
Changing the order of the check() calls seems to fix it: 18814449
Thank you so much! I definitely would not have seen that.