http://www.spoj.com/problems/FREQUENT/ . I solved this question using segment tree but i was wondering if it can be solved with MO's algorithm . Does anyone have an idea of how to apply MO's algorithm on this and keep track of the most frequent value along with it . Thanks in Advance.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.05.2026 22:18:16 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
It can be solved using Mo's alorithm. We need a structure that can handle the following operations:
1) Insert a number
2) Delete a number
3) Get the most frequent number
It turns out that std::set does the job. In our set we will store a structure (Number, Occurrences). Of course, our set will sort the elements by Occurrences and the answer is the first/last element in the set. When we need to insert/delete a number we just find it and erase it from the set, then increase/decrease its number of occurrences and then insert back into the set.
cant it be solved without using a set or anything that consumes O(log(n) ) ?
I am not sure about this... Maybe somebody smarter than me can help you, sorry :(
The bad thing here is that if you don't know how to eliminate the O(log N) you can't prove that it is impossible...
BTW, the problem is about finding the maximum number in a set online and I think that there is no better algorithm than O(log N) per query using priority queue or set.
I m getting tle with MO's algorithm using set
k
Instead of std::set, store them in continious arrays, each of size (BLOCK). Every (BLOCK) queries, reconstruct all the arrays.
To answer "find" query, just see last element in last array. \ To answer "insert" query, find array, find position in the array, then insert it in O(number_of_elements_in_array). \ Delete -- same as insert.
With help of reconstructions, number_of_elements_in_array <= 2 * BLOCK. BLOCK = sqrt(N).
Complexity: O(N*sqrtN)
I don't understand why is it O(N * sqrtN). Isn't it O(N * sqrtN * sqrtN) which is O(N^2)?
Overall reconstructions: O(M / sqrtN + sqrtN) = O(sqrtN) -- reconstruct: O(n) Overall insertions\deletions: M -- insert\delete: O(sqrtN + sqrtN) (first — to find array, second — to find position) Overall find: M -- find: same as insert\delete.
I keep (occurrences, number) pairs sorted, if that's what confused you. But that involves using associative array :((, and adds M*logN, which, though, does not affect N*sqrtN complexity. P.S. Sorry for log.
When you need O(sqrtN) per query, then doesn't it make O(N * sqrtN * sqrtN)? Sorry for the stupid question, but can you provide a short code for me to understand it completely, please?
http://pastebin.com/FTVxTnhT
http://ideone.com/b7rbPr Here is my sqrt(n) * n code .
I m getting tle with MO's algorithm using set ..
gj
This blog entry is exactly what you need.
thanks a lot