The logN factor is for mapping the value because it's quite big. You can use O(1) hash to avoid the logN part.

UPD: But finding max is still logN. I haven't any idea about how to reduce it. Sorry.

then how to find max frequency in O(1)?

ho-jo-bo-ro-lo Finding max is logN. I can't find a better way.

void add(int x){
    cnt[ x ]++;
    suf[ cnt[x] ]++;
}

void remove(int x){
    suf[ cnt[x] ]--;
    cnt[ x ]--;
}

here suf[x] is maintaining how many cnt array index has value >= x

now a variable "ans" that will maintain maximum value in cnt .

now this "ans" will be the maximum frequency and suf[ans] will be the occurrences of such value.

moinul.shaon suppose after performing a few remove() operations suf[ans] becomes zero.

Then how will you get the new maximum occuring frequency?

yes , cnt[x] value may reach negative value (will have to handle RE :p, but i didnt mention here to make it more simple ) , but as you can see the query range will contain atleast one number , so cnt array will never contain zero in all position , after all add and remove operations are performed for a query . so if "ans" variable will be alteast 1 and suf will also be valid .

moinul.shaon thanks for your nice and simple solution for finding max frequency. I think negative problem can be solved by ordering the while loop in Mo's algo. Add first then remove, isn't it?

BTW: Are you a member of BUET_Abacus?

i was wondering about cases like:

1 2 1 2

first query: 1 4

next query : 2 4

for this keeping maximum frequency seemed troublesome but now i realize it's easily possible using the "suf" array you mentioned!

yes , i am @rumman

moinul.shaon

Say we have this example

1 2 1 2

first query: 1 4

next query : 3 4

After first query we'll have cnt[1]=2 cnt[2]=2

also suf[2]=2

So answer will be 2

Now in second query we'll have cnt[1]=1 cnt[2]=1 suf[1]=2

but how we'll update our answer to 1.

Do we need to re-itaerate the whole cnt[] to get the maximum occuring element.

It'd be great if you could provide code for this problem

But by this how

you have to maintain maximum value in cnt in a variable say "ans".

after adding to cnt[x] , if ( cnt[x] > ans )then ans = cnt[x] ;

after removing if ( suf[ans] == 0 ) then ans--;

because in single remove operation maximum value can decrease at most one

moinul.shaon

I have one doubt, Say we have our array as

2 2 2 2 2 3 3 first query is — 1 7 second query — 5 7

say after remove() suf[5]=0

but in your code how will you now update that suf[4]=1

as according to your code value of suf[x] increases only on calling add() function?

Or we have to increment suf[x] also on every remove() operation

i think , you dont even realize what i am doing . suf[x] is maintaining how many cnt array index has value >= x . In first query 1-7 suf will be suf[0]=2; suf[1]=2; suf[2]=2; suf[3]=1; suf[4]=1; suf[5]=1;

"ans" variable will be saving 5 , so occurance is 1.

in second query 5-7, suf[5]will become 0 and "ans" variable will be 4 .again occurence is 1 in suf[4].

i only need to increase suf in add and decrease in remove . the code is correct .