| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Given an array A of n elements and queries of type (l r k),find the number of occurrences of k in the range l to r
If there are no updates, we can solve the problem by having a map<int,vector> and doing a binary search.
But what if there are updates involved.
I read somewhere that we can use bit..
But I am not sure how that would be useful
Thank you in advance
Auto comment: topic has been updated by arshad2117 (previous revision, new revision, compare).
You can use SQRT decomposition. Time complexity is O(q*sqrt(n)*lg(n)+n*lg(n)).
You can also do it offline and compress the numbers in queries, and the time complexity would be O(q*sqrt(n)+n).
Can you please elaborate or provide some relevant link?
I don't have any links, let's wait for the others to respond.
Never mind,got it thanks!!!
Batman please explain how to compress numbers in queries. this is new for me.
Now you can use lower_bound(b,b+new_n,x) to find where x is.
You can use de merge sorte tree, that is, a segmente tree where each node is a sorted vector(from l to r), the in each query you just do a lower bound an a upper bound. https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial
Thanks
You can do update and query in
, using map<int, Tree>, where Tree is Treap/AVL/Red-black/... tree.