Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

asifthegreat's blog

By asifthegreat, history, 4 weeks ago, In English,

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.

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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[] ?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Not for mo since the complexity would end up O(N^2). You could use a segment tree tho.