Блог пользователя Juniorandrade

ZQUERY — SPOJ — std::deque is slow? [SOLVED]
Автор Juniorandrade, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Wow! This is a beautiful solution!

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

    Thanks for help! :)

    → Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить