SPOJ DQUERY TLE HELP

general
,
1

[Problem][1]


[2]

I have used hash map to store frequencies at each node of segment tree. Then I am simply querying it for the required answer. Is there something wrong in my approach i.e. I mean if the time constraints were not there was my logic correct. I can only verify my logic on sample test cases. Also what should be done to get this done in time limit.

P.S. I don't know MO's Algorithm

  [1]: https://www.spoj.com/problems/DQUERY/
  [2]: https://ideone.com/uPyp1M
2

Mo’s algorithm is nothing but sorting queries in a particular order to reduce time complexity of each query to sqrt (n)
Just you need add and remove operations… Like if I have answer of
l,r then how to find ans for l,r+1
Also
If I have ans of l,r then how to find l+1,r answer…
Just doing this is Mo… you can find some tutorial and code for Mo… just change add and remove function accordingly…

1 Like
3

Is my logic correct irrespective of time limit or is there some fault in my logic . Also could you provide some sources to learn MO’s algo.
Also what would be the time complexity of my solution .
Asking too many questions ain’t I ^.^

4

You can read about MO’s Algorithm from here

Tutorial

There is a specific video on this particular question you can watch that here :

DQUERY SPOJ

MO with update

2 Likes