Juniorandrade's blog

ZQUERY — SPOJ — std::deque is slow? [SOLVED]
By Juniorandrade, history, 9 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Juniorandrade (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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)) )

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Wow! This is a beautiful solution!

    One Question, in this case, the query's can be answered online right?

    Thanks for help! :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      No..Step 3 is MO's... so offline only.

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply