Recently I tried to solve Loj-1339 and found some ideas.
The main problem is :
There are several communities in the city. Each community consists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.
Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community.
Each case starts with a line containing three integers n (1 ≤ n ≤ 105), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.
Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j (inclusive).
It can be done with Mo' algorithm. If I was told to find number of distinct integers from i to j then I can easily find the answer using Mo. but problems occur when max-min is wanted. I'm not able to keep track of the maximum community. When I add values, I can do this, but while removing,I can't find out a way to track the maximum. One of my friends told me to make a sqrt decomposition for the array. After adding/removing, somehow we have to maintain the aux[] array, and for queries, suppose we have sqrt(n) blocks, then from i to j, if any block is fully inside i and j then we just take the max from the block Id and if it doesn't , we just loop through the array. But I am not sure about this idea, also I can't implement it properly, can you please help me about this problem ? Thanks in advance.
Why doesn't simple Mo work for this problem? Mo can give you the maximum frequency and also how many that have that frequency so... isn't that it? When you remove, the maximum will be the current maximum or it — 1 since you removed 1.
suppose i have made a
freq[]array where freq[1] = 4 , fre1[2] = 3, freq[3] = 3 . now after removing 2 times, the freq[1] becomes 2 and rest of them doesn't change , then how to find the maximum freq[] ?You maintain an array of frequency of frequencies. So when you remove freq[1] to 3, total[4] will be 0 and you know the answer is 3 now.
wow, it makes sense now :-D thanks a lot. but can we do something like I said in the blog ? or .. is it a wrong approach ? I'm just curious about that
Not for mo since the complexity would end up O(N^2). You could use a segment tree tho.
We can simply find the number of houses for community $$$c$$$ in $$$i$$$ first houses(i.e house #$$$1$$$..house #$$$i$$$) for every $$$c$$$ and for every $$$i$$$, the complexity of precalculation is $$$O(n * c)$$$, and for every query just iterate over all communities and find the number of houses in the segment $$$i..j$$$. Then find the maximum number of a community's houses in the given segment(its $$$O(c)$$$, then multiply it with the number of such communities(strong communities). For sqrt decomposition, yes you can use it like any other sqrt decomposition problems, but i don't thing its needed to use Mo's algorithm.