Блог пользователя 444iq

Автор 444iq, история, 5 лет назад, По-английски

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

add 17 to array

array becomes 10 15 17 20

3rd largest = 15

Q <= 10^5.

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

You can use PBDS

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    array can contain duplicates too, i tried it with pdbs but it work for unique elements.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      use less_equal instead of less.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        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 ?

        nilesh8757

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          You can keep pairs $$$(a_i, id)$$$ in the ordered set ($$$less$$$), where $$$id$$$ is unique for each pair.

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Ordered_multiset

Just change less to less_equal

Like this:

#define ordered_set tree<int , null_type,less_equal<int >, rb_tree_tag,tree_order_statistics_node_update> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    But it is giving wrong answer after I perform delete, and I am not able to delete single element from it.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can use find_by_order to find kth element and add is just insert

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You need to write

      while(a.find(k) != a.end()){
         a.erase(a.find(k));
      }
      
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          RetiredPlayer but there is one problem here.

          suppose 1 , 3 , 3 , 5 , 7 , 9 , 11

          3rd largest = 3

          less than 9 = 5 elements

          delete(3)

          it becomes 1 , 3 , 5 , 7 , 9 , 11

          3rd smallest = 5 , but it is showing 3. http://ideone.com/Oessur

          No of elements less than 9 are 5 , but it should be 4

          after deletion things are not working as it should be.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 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))

»
5 лет назад, # |
  Проголосовать: нравится 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 !!