Doubt in MO's algo -

help
, ,
1

Can anyone clear one doubt regarding MO’s algo , Why we sort the queries (L,R) , by the block size why not sort just simple (L,R) way ?

@everule1 @rahulmysuru7

2

I think we are sorting based on block number in which L is residing . Correct me I’m wrong.

3

But why ?

what happens if we sort just (L,R) instead of block size ?

4

Don’t you think it’s basically sorted on L only. And one reasons to restrict L within block is that we need to transfer that L pointer at max √n . Else its basically sorted on L and then if both are in same block then we try to sort it usingR value. So that when we count Rpointer value at that time we don’t need too much travellingbopointer.

5

Actually I m still struggling that how by sorting via block only moves pointer at most root(n) ? give me an example.

6

We have sort all this based on block number so and two adjacent query will have difference of at most √n. As size of block is also the same so left point will move at max √n . If prev query has starting of block and current is having ending of block index.

7

means u wanna say that by sorting via blocks tends to this -

( R1 - L1 ) - ( R2 - L2 ) is at-most \sqrt(n) ?

8

If you sort based on only L R ,
consider these queries, and N=20,000
1 5
2 15000
3 4
1200 15000

If you just sort L R ,ur 2nd pointer must iterate much more, leading upto O(n) per query.

1 Like
9

To actually say, where do u want to use MO’s algorithm?
Since there are no update queries ,u can just store a prefix sum array, and answer each query in O(1) ,total time complexity O(n+q) for sum queries.

10

Yeah , I understand now bcz we have to move ML , MR pointer so if we sort by blocks it will more efficient , also -

bool cmp(query a , query b)
{
    lli blk_num_a = a.l / blk_sz;
    lli blk_num_b = b.l / blk_sz;
    
    if(blk_num_a != blk_num_b)
        return(blk_num_a < blk_num_b);
    
    return(a.r < b.r);
}

bool fast_cmp(query a , query b)
{
    lli blk_num_a = a.l / blk_sz;
    lli blk_num_b = b.l / blk_sz;
    
    if(blk_num_a != blk_num_b)
        return(a.l < b.l);
    
    return ( (blk_num_a % 2) ? (a.r > b.r) : (a.r < b.r) );
    
    // In odd blocks sort the right index in ascending order and in even blocks sort it in descending order. 
    // This will minimize the movement of right pointer, as the normal sorting will move the right pointer 
    // from the end back to the beginning at the start of every block. With the improved version this resetting 
    // is no more necessary.
}

the first cmp function is one way to sort while second one is more more faster , in same question when I apply first one it passed in 4898 ms , while second one passed in 3242 ms.

Question : “Problem - D - Codeforces”
4898 ms code : “Submission #93328318 - Codeforces” [1st func]
3242 ms code : “Submission #93328257 - Codeforces”[2nd func]

@rahulmysuru7

1 Like
11

Many questions uses MO algo below is one of them -

“https://codeforces.com/gym/101879/problem/H”

More problems - “Problem Topics - Codeforces”

1 Like