ISuckAtLife's blog

Help with MO algorithm Question
By ISuckAtLife, history, 5 years ago, In English

We are given A array with N elements and Q queries are done on it. In each query, a range (L,R) and a no. K is given and we have to find no of element with frequency >=K in that range.

constraints A[i]<=1e6

N<=1e5

Q<=1e5

I am trying to do it using MO algorithm. Kepping an array to store frequency of each element. But how do i find elements with frequency >= k without transversing (otherwise complexity will be much higher)

Thanks in advance

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

UPD: I thought K is fixed.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    TselmegKh Actually K is changing in each query. so if i understood your approach correctly, it would not work.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should have a variable that keeps count on how many elements have a frequency greater or equal to k. This variable you only have to update it whenever a number gets to frequency k or k — 1.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    suppose currently in range (1,10) 5 element have frequency greater than k. so ans is 5 now. now in next query range is same i.e. (1,10) but new k is k-2. Then in mo algorithm no add or remove function will be called and ans will remain same. which can be wrong

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use BIT (binary indexed tree)as an additional data structure along with map, this BIT maintains the count of elements with particular frequency , now answer for a query is simply query(n)-query(K-1);

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Use a BST where you can get index of a value. Use this as your frequency "array". This way it is always sorted so you can calculate how many values are before/after k.

It is also possible to use a segment tree instead. Put a 1 on position i if freq[x]=i for some x. if there are two different values with same frequency, put a 2 there etc. You can now query sum in l..r to see how many different values have frequencies between l and r.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot. I got your BST approach.

    one question in your second approch. We need to sort the queries by increasing order of their right end. And query the sum between (K,'maximum frquency till now') in segment tree of your array.Am i Right?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Both approaches still use Mo's algo, so you sort the queries in Mo's algo order.

      But this will be complexity O(n * sqrt(n) * log(n)) so maybe too slow.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ohhk. Got it, Thanks a lot. And the question that I am trying is having 5 sec time limit so I think it should work.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use a fenwick tree for finding the no of elements with frequency>=k

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ISuckAtLife can you please give me the problem link? I want to solve it. Though it can be hard as it's a post from 10 months ago.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Use block technique to keep total complexity in O(n*sqrt(n)). In detail, maintain the frequency arry $$$Bi$$$ of each element $$$Ai$$$ and calculate the sum for each block. In this way you can move endpoint in O(1) complexity and answer each query in O(sqrt(n)).

→ Reply