Chess.Master's blog

Interesting Problem from ECPC qualifications day 2
By Chess.Master, history, 15 months ago, In English

Hello codeforeces, I was trying to upsolve the ECPC Q day 2 and I am stuggle with this problem and need some help please.

image

I am thinking of using mo's algorithm but I can't solve this problem. Can any one help me please?

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

Comments Comments (4)
| Write comment?
»
15 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

You can just ignore it now. (I assume you don't know MO's algorithm)

This problem can be easily solved by MO's algorithm. As always ECPC problems are standard problems, either you know or you don't know.

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

    I already read about MO's algorithm and learned it... If i ignored it now how i will learn this!?

    Please write the solution if you know. as i am really interesed to solve this problem.

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

      spend your time learning binary search rather than more advanced algorithms that appear very infrequently.

      → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Just use MO, maintain a data of each freq how many time it appeared.

      Like say $$$freq[x]$$$ is how many time $$$x$$$ appeared, $$$freq2[x]$$$ how many time $$$x$$$ was a freq of a number, you can update that while adding/deleting one element in $$$O(1)$$$

      Then to check that every freq from $$$X$$$ to $$$Y$$$ appeared, go for loop check that every $$$freq2[X...Y]$$$ are greater than $$$0$$$.

      Sorting querys and maintainning data is $$$O(NsqrtN)$$$ as a standared MO is. For answering the query its extra $$$sqrtN$$$. (the for loop can't go more than $$$O(sqrtN)$$$ otherwise the sum of freq is greater than $$$N$$$ and that is impossible).

      Complexity : $$$O((N+Q)*sqrtN)$$$

      → Reply