I used Mo's algo to solve this problem .
First compare function: It gives me wrong answer Submission1
bool comp(query &a,query &b)
{
int x=a.L/bsize;
int y=b.L/bsize;
if(x!=y)
return x<y;
if(x&1)
return (a.R > b.R);
else
return (a.R < b.R);
}
Second function : Gives me AC Submission2
bool comp(query &a,query &b)
{
int x=a.L/bsize;
int y=b.L/bsize;
if(x!=y)
return x<y;
else
return a.R < b.R;
}
First one is an optimisation,but not able to find why it gives wrong answer
In the first code, as you go backwards(going from (L1, R1) to some (L2, R2) such that L2 < L1 and R2 < L1) you will call dec on an element that has not yet been added. In order to avoid this, you should first increase the size of segment you're on, and then dec, i.e. first call inc(++right) and inc(--left) and then dec(left++) and dec(right--).
Thanks for the reply. It is clear now . Any sort function try to inc the range first and then dec.
So if I interchange less than and greater than as below. inc,inc,dec,dec will still work