Hello codeforces!
Recently in the problem I came across with this data structure, which can perform this operations:
add element
delete element
return the maximal of it
with O(1) for query.
So the question is simple: is it exist?
# | User | Rating |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
3 | adamant | 162 |
4 | TheScrasse | 158 |
5 | nor | 153 |
5 | maroonrk | 153 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
9 | orz | 145 |
10 | pajenegod | 144 |
Hello codeforces!
Recently in the problem I came across with this data structure, which can perform this operations:
add element
delete element
return the maximal of it
with O(1) for query.
So the question is simple: is it exist?
Name |
---|
Auto comment: topic has been updated by waipoli (previous revision, new revision, compare).
Auto comment: topic has been updated by waipoli (previous revision, new revision, compare).
You can use heap but it is O(log n) for each. I think it is the best for your need.
I have forgot to mention that i'm happy with offline solution
Offline approach where you have addition and deletion?? Is it possible?
Doesn't set do same thing or am I missing something?
No. Consider there exists some ds which perfoms given operations in O(1). Suppose I insert N elements.
Further I would store current maximal element (say in an array) and delete it in O(2) and continue this process N times. The resultant vector would contain sorted elements in effective time of O(3N) which is not possile.
(It can be proved worst case time complexity of sorting an array cannot be less than NlogN.)
Thank you!
:)
nice argument
You can write a Fibonacci's heap, which can add element and get min/max in $$$O(1)$$$. But it can delete only in $$$log(n)$$$ time