Hey guys, I need help in understanding the solution of this question - http://codeforces.com/contest/86/problem/D
We are solving it using Mo’s algorithm. My doubt here is that, most of the solutions have this-
while(l+1<=q[i].l) ret-=a[l]*(2*(key[a[l++]]--)-1); while(l-1>=q[i].l) ret+=a[--l]*(2*(key[a[l]]++)+1); while(r-1>=q[i].r) ret-=a[r]*(2*(key[a[r--]]--)-1); while(r+1<=q[i].r) ret+=a[++r]*(2*(key[a[r]]++)+1); ans[q[i].p]=ret;
While I understand the concept of sorting the queries and optimally moving points, what is the significance of diving array into sqrt(N) blocks if we are traversing through array 1 by 1 instead of bucket by bucket? Or am I missing something?
Editorial just confused me even more because of its format. I think there is some issue with English used cause-
Clearly, there doesn't exist an order in which we can go through the queries in o(n sqrt(n)) time as the transition from any interval to the other one is done in no less than sqrt(n) steps.
Nevertheless, there exists a traversal order that guarantees O(n sqrt(n)) steps in the worst case.
Even more lost after reading editorial. I will appreciate if anyone can explain the -
- Solution (comments/explanation appreciated )
- Time Complexity
- Why does it not get TLE if we are updating points by 1 instead of root(N)/Moving element by element instead of bucket by bucket.