Can anyone please help me to solve this problem, ? (http://www.spoj.com/problems/RRANGE/) I am not good at data structures
Can anyone please help me to solve this problem, ? (http://www.spoj.com/problems/RRANGE/) I am not good at data structures
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 7 | nik_exists | 133 |
| 9 | Dominater069 | 131 |
| 10 | AmShZ | 130 |
This problem is not about data structures, it's rather brute force involving a little math. You have at most 1000 updates and 1000 queries, so for every query, consider every update and see how it affects the answer.
but it can be solved with segment tree or BIT?
I wouldn't see the point in compressing the numbers (because N can be as big as 109) and then using a segment tree with complicated queries, when you can solve the problems with only 4 or 5 lines of code and no data structures besides two simple arrays.