Hi Codeforces!
I'm trying solve this problem http://www.spoj.com/problems/ZQUERY/ . My code has complexity O( n * sqrt(n) * log(n) ) using Mo's algorithm and Segment tree. But, i get TLE. My code use std::deque to find the solution of each interval.
This data structure is slow in this case? Is there any way to remove log(n)?
Thanks for advance!
My code in cpp: http://ideone.com/pHvCEH
you can use a multiset with deque instead of segment tree. It gets accepted because of less constant factor. Here is my code : http://ideone.com/HUkmtN
Really, the segtree increase my complexity, and now, i got AC! :) But, the execution time of my solution was too high! Anyway, thanks for help!
Auto comment: topic has been updated by Juniorandrade (previous revision, new revision, compare).
You can solve it in (Q+N)sqrt(N)
1) Compute prefix sums
2) An O(N) pre-processing to store previous and next occurrence of same value from given index
3) While processing a query, you make changes to an array in constant time (per change, not per query, using the precomputation) indicating which all sizes are available in current interval. O((Q+N)sqrt(N)). . This avoids the use of segment trees, and hence the logN factor can be removed.
4)Find the maximum value in this array using sqrt-decomposition (once per query,so O(Q*sqrt(N)) )
Wow! This is a beautiful solution!
One Question, in this case, the query's can be answered online right?
Thanks for help! :)
No..Step 3 is MO's... so offline only.
I understand your point number 3 but i am not able to implement it. Can you please give a little bit more detailed idea about the implementation.
I read about mo's algorithm from :- https://blog.anudeep2011.com/mos-algorithm/. I was able to modify the add function and update the answer but was unable to deal with the remove function.