MO ALGO - Codeforces

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

MO ALGO

Автор vsanjay_nitdgp, история, 11 лет назад, По-английски

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

algorithms

-6

vsanjay_nitdgp
11 лет назад
8

Комментарии (8)

Написать комментарий?

vintage_Vlad_Makeev

11 лет назад, скрыть # |

← Rev. 2 →

-8

I am not sure it's possible to solve it with Mo algorithm.

It can be solved for O((N + Q)log²N) using some 2d tree.

→ Ответить

Gogito

11 лет назад, скрыть # ^ |

If by "2d tree" you mean 2D segment tree, then it doesn't have to be 2D.

→ Ответить

vintage_Vlad_Makeev

11 лет назад, скрыть # ^ |

How is it possible to solve it with 1d segment tree?

→ Ответить

Mhammad1

11 лет назад, скрыть # ^ |

← Rev. 2 →

Ok, it can be solved by 1D segment tree by the following:

let lastPos[i] it's the last index of the number i, so sort the queries by its r values in non-descending order then apply this:

buildSG(); //Build segment tree 
for(int i=0; i<N; i++)  {
     if (lastPos[a[i]] != -1) updateSG(lastPos[a[i]], -1); //decrease the value by 1
     lastPos[a[i]] = i; 

     foreach (Query q where q.r == i) {
        ans[q.id] = querySG(q.l, q.r); 
     }
}

You only need to implement Sum Range Query segment tree!

→ Ответить

P_Nyagolov

11 лет назад, скрыть # |

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

→ Ответить

ikbal

11 лет назад, скрыть # ^ |

+13

Challenge accepted. :P

→ Ответить

P_Nyagolov

11 лет назад, скрыть # ^ |

Congrats! And it works faster than my persistent tree. It makes me doubt in my implementation :(

→ Ответить

dalex

11 лет назад, скрыть # |

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

→ Ответить