D query doubt (conceptual)

#1

Sir ,

  1. i am unable to understand where we used square root decomposition in this problem . All i see is mo 's algo??
  2. Also why we used block in comparator for sorting queries , if we can sort it on the basis of l and r ?
#2

@shivampandey9599,

  1. Mo’s algorithm is based on sqrt decomposition. (Read more, here)

  2. I think you have misunderstood the ordering of queries in Mo’s, it is not simple sorting of ascending pairs, rather:

image
image1918×170 21.8 KB

(Maybe this is the bug in your code that is causing WA in SPOJ).