sir/mam,,,
i tried the following problem using MO bu getting TLE........
question:http://www.spoj.com/problems/DQUERY/en/
my solution:http://ideone.com/MqzGnu
could anyone help me in getting AC
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
sir/mam,,,
i tried the following problem using MO bu getting TLE........
question:http://www.spoj.com/problems/DQUERY/en/
my solution:http://ideone.com/MqzGnu
could anyone help me in getting AC
Name |
---|
I am not sure it's possible to solve it with Mo algorithm.
It can be solved for O((N + Q)log2N) using some 2d tree.
If by "2d tree" you mean 2D segment tree, then it doesn't have to be 2D.
How is it possible to solve it with 1d segment tree?
Ok, it can be solved by 1D segment tree by the following:
let
lastPos[i]
it's the last index of the numberi
, so sort the queries by itsr
values in non-descending order then apply this:You only need to implement Sum Range Query segment tree!
I don't believe Mo's Algorithm will work here. I needed to optimize even a solution with a persistent segment tree to get AC :)
Challenge accepted. :P
Congrats! And it works faster than my persistent tree. It makes me doubt in my implementation :(
You should divide all queries into sqrt(n) buckets by its left border, and process each bucket separately. To process a single bucket, sort the queries by their right borders. Then the right border will only increase, and for dealing with the left border you should iterate to the left through no more than sqrt(n) indices.
Example: n = 9, queries are (1,8), (3,7), (2,3), (2,8), (1,9).
Queries like (2,3) which length is very small, can be processed naively.
Then, sqrt(9) == 3, and sorted queries are (3,7), (2,8), (1,8), (1,9). Order or (2,8) and (1,8) even doesn't matter. All these queries, for the simplicity, belong to the first bucket (where 1 <= L <= 3).
We put the right pointer to the beginning of the next block (the index 4). For the first query (3,7), go forward through indices 4, 5, 6 and 7, then go back for the index 3, store the result, and rollback the index 3. For the next query (2,8), go forward, visiting the index 8, then go back through indices 3 and 2, store the result, and rollback the indices 2 and 3. And so on.
Then repeat it for each of sqrt(n) buckets of queries.
Right pointer goes only forward, so it gives O(n) movements for each of O(sqrt(n)) buckets. And left pointer for each of the q queries goes back for no more than sqrt(n) indices. So it's (n+q)*sqrt(n).
I believe this is the Mo's algorithm, but if it isn't, this is how I was learned to solve such problems (I firstly saw this name here, on CF).