vsanjay_nitdgp's blog

MO ALGO
By vsanjay_nitdgp, history, 9 years ago, In English

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

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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!

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply