I was trying to solve this problem on spoj and i discovered MO’s algorithm. I understood the algorithm but i have one doubt on its time complexity.
for each query ( as queries will be sorted ) left pointer moves atmost sqrt(n) times but doesnt right pointer moves o(n) at the worst case which makes whole algorithms complexity as o(q*n)?
Thanks in advance.
why right pointer moves N time ?
share your code for sorting the query.
I use generally two codes -
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 faster_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.
}
not for sorting. after queries are sorted.
for example after sorting if my queries looks like this (assuming block_size to be 4 and array length to be 18):
[ 1,10]
[2,14]
.
.
.
here for each query right doesnt pointer moves o(n) or am i missing something?
okay will check it once again
yes, it can move O(n) places but just once for each block because right limit is sorted inside each block. So complexity is O(n * sqrt(n)) or O ((n+q) * sqrt(n)) to be more precisely
He said complexity will be q*n ? and this is wrong explain littile bit more.
you move n places once for block, you have sqrt(n) blocks so overall it’s sqrt(n)*n; I wouldn’t know how to explain it more 
Understood. sorry for the late reply.