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 | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
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
You can use soft heap. It can add element or delete minimum ( and some other operations ) in O(1), but not delete some elements. Deleting I see as memorizing number of elements in some hashset and when we have x as minimum and number of x in that hashset is 0, we can say that it is minimum ( for maximum multiply all numbers by -1 ) and otherwise decrease it's number from hashset and perform operation one more time. The only issue there that the elements can be corrupted. You choose some E and then you can performe operations in O(log(1/E)) time and at most E*n out of n elements are corrupted. It is even more complicated them Fibonacci's heap.