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!