given an array of integers with (N <= 1e6) and Q (Q <= 1e6) queries with L and R.. what is the mostly repeated number in range [L,R] ? is there any fast way to work it out ?
given an array of integers with (N <= 1e6) and Q (Q <= 1e6) queries with L and R.. what is the mostly repeated number in range [L,R] ? is there any fast way to work it out ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
That is the range mode query problem. It has a lot of solution in
with either just Sqrt-decomposition or MO's algorithm. You can also do it with bitset.
If you know that the number of times the mode appears in the range is large, you can refer to this problem.