Блог пользователя Chess.Master

Interesting Problem from ECPC qualifications day 2
Автор Chess.Master, история, 15 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
15 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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)$$$

      → Ответить