Death_Scythe's blog

QCHEF — Help needed with Mo's Algorithm
By Death_Scythe, history, 8 years ago, In English

Hello!

I am trying to solve this problem https://www.codechef.com/problems/QCHEF using Mo's Algorithm+Segment Tree but my solution times out. Complexity of my solution is . Is it possible to eliminate the log factor? I know there is an editorial with the problem, (it uses a different decomposition, I think) but I am wondering if my solution can be optimised to .

My solution: https://www.codechef.com/viewsolution/10638667

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Seems to me like it can.

I didn't actually read your solution, but it most likely suffers from usual hard case in Mo's algo which is erasing some value from the interval when you need to change borders.

The first solution that came into my mind is with maintaining some structure like deque <int> mp[MAX_A] and when you add some value X to the left you mp[X].push_front() and mp[x].push_back() if you add it to the right. To delete some value you pop_back() and pop_front() in a same way.

Also you store multiset <int> of values and after adding / deleting value you insert / erase

mp[X].back() - mp[X].front()

That's our bottleneck now, here's the log factor

To fix this log factor you should do it in a same way, you need to backtrack your changes instead of using set to keep them all.

There is a nice and short editorial with an example of code.

→ Reply