Thanks in advance.

....So why does this post keep getting negative feedback...

EDIT : Now it starts to get positive votes

How can this problem be solved with less time complexity?

is there any problems in oj?

I got a couple of questions: - Which value would S take if there wasn't any element having a value less than sqrt(N)? - Could you please describe the proof of the overall time complexity? EDIT: When you say the max integer which is less than sqrt(N) you mean floor(sqrt(N)), then it makes sense and the proof is easy as you already said, sorry for the misunderstading.

Why A.r > B.r? I can't see it, shouldn't it be < instead?

thanks for good algorithm.

I think it can be solved in .

1. Sort all queries with your comparator except A.r < B.r in the last line.
2. Make array cnt[] where cnt[x] is how many times number x was met. Also we will maintain the number maxNum which was met maximal number of times (cnt[maxNum] is this number of times).
3. Process the queries group by group. Queries A and B are in the same group if A.l == B.l. So there are such groups. Clear array cnt, then...
4. Start with r = k*S (k = 1, 2, ...) (it's the first element of the next block in sqrt-decomposition) and move it to the right, updating cnt and maxNum. If some query in this block has the right border equal to r, then...
5. Store number maxNum in the temp variable and move pointer l from position k*S to the left while it is not equal to current query's left border. It will move to distance no more than . Of course, we updating array cnt and variable maxNum during this process.
6. If l is equal to the query's left border we can answer the query — it is maxNum. Then move pointer l back to the right, to its initial place k*S, updating cnt with subtractions, not additions. Finally, variable maxNum — the most appearing number — is now wrong — we cannot maintain it when we subtract from cnt. But we stored its actual value (for segment [kS, r]) at the beginning of step 5. Our data structure became consistent and we can continue processing the queries.

Here is idea.

First of all, lets sort all queries using your comparator.

Let array S[N] be an array, which consist of N hashsets. S[i] contains all numbers, which appear in our current segment exactly i times. Let A[n] be an array(or hashmap), where A[i] contains the number of appearances of number i in our current segment. Let max be the biggest index of nonempty set in S

Using this structures, we can add or delete number in O(1) time:

1) Add some number v: delete v from S[A[v]], increase A[v] by 1, add v to S[A[v]], if A[v] > max — increase max by 1.

2) Delete some number v: delete v from S[A[v]], decrease A[v] by 1, add v to S[A[v]], if S[max].size() =  = 0 — decrease max by 1.

To get answer for the query we just take any number from S[max]

The total transformation cost is (N sqrt(N) + Q sqrt(N) )log N instead of N sqrt(N) log N, because for each query in the worst case you will have to go through a whole block of length sqrt(N).

There's one cool adaption of that: Say you have a data structure that supports insert trivially but not delete. There are lots of examples where this is the case.

Assume however that we can implement a snapshot() and rollback() function for our data structure, so that a rollback() brings us back to the state of the latest snapshot in , where k is the number of inserts since the snapshot. Every persistent data structure makes this possible trivially, but that's actually more than we need and often we can find tricks to implement these operations in a much simpler way, possibly even by using memcpy

We can still use the technique presented here with runtime . init() can have complexity .

In the following code, we assume zero-based indexing of the queries and inclusive right borders:

   rt = sqrt(n)
   init()  // this initializes our data structure (clears it)
   snapshot()
   sort queries (l, r) by (l / rt, r) ascending
   for all queries q
       if q.r - q.l + 1 <= rt + 1 // we process light queries
           for j := q.l to q.r
               insert(j)
           store answer for query q
           rollback()
   last_bucket = -1
   for all queries q 
       if q.r - q.l + 1 <= rt: continue
       bucket = q.l / rt

       if bucket != last_bucket
           init()
           l = (bucket + 1) * rt // right border of the bucket
           r = q.r
           for j := l to r
               insert(j)
       last_bucket = bucket

       while r < q.r 
           insert(++r)
       snapshot()
       for j := q.l to l - 1
           insert(j)
       store answer for query q
       rollback()

"First we need a data structure that can support: insert a number. delete a number. get the mode number. It can be solved easily by binary heap / balanced binary search tree."
Another easy way would be to keep a map of (number, frequency) and a set of pair (frequency,number). Insertion/Deletion are O(log N). Getting mode is O(1).

Thanks for sharing.It's really helpful for me to learn Mo's algorithm. I can hardly find a paper about Mo's algorithm on Internet.

It seems that this cmp is faster than your cmp:

bool cmp(Query A, Query B)
{
  if (A.l / S ！= B.l / S) return A.l< B.l;
  return (A.r < B.r)^(A.l/S%2);
}

2182 MS with above cmp: 15551689

3586 MS with your cmp: 15558775

If we had all queries with l in the same segment, except that in sorted order they alternate with one starting at the beginning of the segment, the next starting at the end of the segment. Wouldn't the time complexity for queries be O(Q log Q + Q * sqrt N)?
By segment I mean the sqrt N partition.

Тут предлагалось несколько вариантов избавления от множителя lgn в оценке времени. Еще один вариант: можно хранить кол-во текущих появлений в любой пирамиде. Т.к. в ней будут целые числа, то при изменении любого значения на 1 произойдет не более одного перемещения. Но чтобы по числу за O(1) найти его узел в пирамиде придется также заводить либо массив размером max{a[i]}, либо хештаблицу и тогда время будет ожидаемым O(1).

what is mos algo + dp my sol is not passing in 2 sec by only mo's algorithm where both n and q is 5e5

how to sort like this in python?