Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### 444iq's blog

By 444iq, history, 10 months ago, ,

How to find kth largest element each time where k will vary and array is modifiable. That is you can add new elements to the array array can have duplicates.

for example say array is 10 , 20 , 15.

2nd largest = 15

array becomes 10 15 17 20

3rd largest = 15

Q <= 10^5.

• -13

 » 10 months ago, # | ← Rev. 2 →   +3 You can use PBDS
•  » » 10 months ago, # ^ |   -7 array can contain duplicates too, i tried it with pdbs but it work for unique elements.
•  » » » 10 months ago, # ^ |   +3 use less_equal instead of less.
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot. It worked.Suppose we also want to delete a single element which occurs more than 1 time.A.erase(x) will delete all x. how to erase just a single x value ? 1600
•  » » » » » 10 months ago, # ^ |   +3 You can keep pairs $(a_i, id)$ in the ordered set ($less$), where $id$ is unique for each pair.
 » 10 months ago, # | ← Rev. 5 →   0 Ordered_multisetJust change less to less_equalLike this: #define ordered_set tree, rb_tree_tag,tree_order_statistics_node_update> #include #include using namespace __gnu_pbds; 
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 But it is giving wrong answer after I perform delete, and I am not able to delete single element from it.
•  » » » 10 months ago, # ^ |   0 You can use find_by_order to find kth element and add is just insert
•  » » » » 10 months ago, # ^ |   0 yes, but after deletes it doesn't work correctly. See above link.
•  » » » 10 months ago, # ^ |   0 You need to write while(a.find(k) != a.end()){ a.erase(a.find(k)); } 
•  » » » » 10 months ago, # ^ |   0 Thanks.
•  » » » » » 10 months ago, # ^ | ← Rev. 4 →   0 proggerkz but there is one problem here.suppose 1 , 3 , 3 , 5 , 7 , 9 , 113rd largest = 3less than 9 = 5 elementsdelete(3)it becomes 1 , 3 , 5 , 7 , 9 , 11 3rd smallest = 5 , but it is showing 3. http://ideone.com/OessurNo of elements less than 9 are 5 , but it should be 4after deletion things are not working as it should be.
•  » » » » » » 10 months ago, # ^ |   0 In the blog above you said about just adding and finding kth element, Ordered_set can't erase element x but it can erase k th element by doing A.erase(A.find_by_order(k))
•  » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 i just wanted adding and finding kth element for a problem.Rest I was just experimenting on myself. Sorry for trouble.Thanks for help.
 » 10 months ago, # |   0 Try implementing it with fenwick tree. If all the values are less than 1e5 then it becomes relatively easy. If the values can go high then you need to store the queries and process the elements offline so that you can compress the higher values to smaller values.Every element will be compressed to some element <=1e5 as the no. of unique values <= 1e5. Now you can use binary search on fenwick tree !!
 » 10 months ago, # | ← Rev. 3 →   0 I think that square root decomposition can handle this. Just compress the numbers and make two tables with respect to the rank. One will be O(N) in size, the other O(sqrt(N)) in size. I leave it as a small exercise for you to fill in the rest of the details.
•  » » 10 months ago, # ^ |   0 This solutions works even if you also have deletions from the array or you have point updates. But this cannot handle range updates.