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

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

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

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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.

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

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

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

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

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

        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!

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

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

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

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

→ Ответить