Given n numbers and m queries for each query (L R) find the most frequent number from L to R and how many times it occurs in this interval
for example:
input:
7 3
3 5 3 5 5 3 3
2 4
3 3
1 3
output:
5 2
3 1
3 2
thanks in advance.
Given n numbers and m queries for each query (L R) find the most frequent number from L to R and how many times it occurs in this interval
for example:
input:
7 3
3 5 3 5 5 3 3
2 4
3 3
1 3
output:
5 2
3 1
3 2
thanks in advance.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Link
thanks :)
Hi! Please write the link of problem statement. I couldn't find that. Thanks
I think it can be solved by Treap or segment tree.
At each node we will save answer for current segment.
UPD: Wrong
Imagine we know answers for [l, mid) and [mid, r).
How to combine these answers and find it for [l, r)?
You can use MO's algorithm to solve, you can find detailed explanation here : http://blog.anudeep2011.com/mos-algorithm/