When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Rhangel's blog

By Rhangel, history, 7 years ago, In English

Hello people of Codeforces :)

I was solving a problem that had two types of operations: 1 — Insert element X the sequence 2- What is the kth largest element of the sequence. How to solve this type of problem?

The sequence may have 10 ^ 5 elements, and may have 10 ^ 5 queries.

Tks. :D

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Treap data structure will be extremely useful ;)

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You can do these types of operations quite easily with any balanced binary search tree. I prefer a Treap because the tree rotations that occur after insertion/deletion are very simple. Others might be a splay tree, red-black tree, AVL, etc. You can keep track of the number of elements stored in the subtree of each node in your tree, then it becomes easy to count the number of elements smaller than X. You can insert, delete and count the kth largest in O(log(N)) time.

»
7 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

You can take the sequence and the insert queries first. Sort the elements according to their values (including insert queries) and give them sorted indices in the final sequence. Set all elements position of the initial sequence to 1 and insert queries to 0. For each insert query you can update the element's position to 1. To get the Kth element you just need to find the smallest index where the cumulative sum is K from the first position. You can easily manage this update and find query with a segment tree. Complexity of per insert and find query of this technique is O(log(N)).

»
7 years ago, # |
Rev. 5   Vote: I like it +40 Vote: I do not like it

Hello! You can learn about Indexed Set in C++ (it is policy-based data structure). Antti Laaksonen (pllk) also wrote about that in his book (here you can download and find about Indexed Set in page 44).

Indexed Set can find position of x and x'th element in set in O(logn) but constant of complexity is a little big. Here I wrote program with Indexed Set for finding k'th maximum in array:

Code

UPD: I found problem like that with delete update, original solution is by treap, but my code with Indexed Set got AC 135ms. https://www.e-olymp.com/en/problems/687
Solution: https://pastebin.com/10iu04L9

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    TooNewbie, Is there any similar policy based DS to find kth smallest element in which there can be duplicate elements?. Indexed set gives wrong answer on duplicate elements. Is there indexed multiset ?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      You can do it with the same DS. Simply when inserting, maintain a pair<value, idx>, where idx is the index of the element you are inserting. If you didn't understand what I mean you can imagine that you will have indexed_set<pair<int, int> > S and a map<int, int> M keeping the number of elements with a given value.

      Then the insert will be something like:

      S.insert({x, M[x]++});

      And the delete will be something like:

      S.erase({x, --M[x]});

      UPD: To find K-th smallest element, you will have to do S.find_by_order(K).first and to find number of elements with value less than K, you will do S.order_of_key({K, -1}).

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      You can use a pair in indexed set. For example, if x has 3 duplicates in set, let them be {x,1}, {x,2}, {x,3}. Note that while comparing pairs priority of the first element of pair is more than second.

      EDIT: Snipped by Radoslav :P

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When defining the indexed set, you can use less_equal as comparer instead of less. This makes the set work as a multiset. Both inserting and kth element work, but remove() isn't guaranteed to work correctly in this case.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      This topic is related to a problem in an on going contest, so can you please discuss it after the end of "Week of Code 38" on HackerRank.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can solve this problem with O(log(n)²) per query. Just make a binary search over X and use a BIT (Segtree, whatever) to determine how many elements are bigger than X, with this you can determine if you have to go left or right.

You can do better using just a SegTree.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can do binsearch in segtree in O(log(MAX)).

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do in O(log n) using a binary search tree, a BIT or a segtree... all of them support binary searching in O(log n)

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know that. I'm the author of the problem, so I just wanted to mention one of the simplest ways to solve it.

»
7 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

No hard data structures are needed if K is constant (see replies). Please write more detailed constraints.

priority_queue<int> q;

// preparation
for (int i = 0; i < n; ++i) {
    q.push(a[i]);
    if (q.size() > k) q.pop();
}

// operation 1
q.push(X);
q.pop();

// operation 2
cout << q.front() << endl;
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i thought K is not constant

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    K is no constant. For each query you have a new value of K.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      I understand why they suggested balanced search trees. I think BIT is easiest and fastest if range of X is enough small. (Also thank you RapperGuy.)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give the link to the problem? Thanks!