shoya's blog

How to get max integer less than or equal to x in a set ?
By shoya, history, 5 years ago, In English

Consider initially an empty set and there are two types of queries:-
1) Given x, insert integer x in the set.
2) Given x, get the max integer y in the current set such that y<=x.

For Example :-
Suppose after several type 1 queries our set is {3,1,-14,1,5}.
Now type 2 comes with x=6 then answer would be 5.
Now type 1 comes with x=6 then set becomes {3,1,-14,1,5,6}.
Now type 2 comes with x=8 then answer would be 6.

How can we solve this problem without using policy based data structure ?

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

Comments Comments (6)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can use std::set. Type 1 can be handled using simple insert. For type 2 queries, you can upper_bound on the value x, and get the iterator of y by decrementing the iterator returned from the upper_bound. If there are duplicates, use a multiset instead.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use stl::set and do a lower_bound but with rbegin() and rend() and use greater<int>() comparator, for example: *lower_bound(se.rbegin(), se.rend(), 6, greater<int>())

or you can use a decreasing order set (greater comparator) and then you would use lower_bound normally, like set<int, greater<int>> se then you can use *se.lower_bound(6)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Or you can use BIT to solve this problem.

You can binary search the value y, and check that if there is a number inside.

The time complexity is O(log^2 n).

→ Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

you can do it manually:

multiset < int > s;

s.insert(x);

if(x==s.begin())cout<<-1<<endl; //there no number smaller or equal to x

else {

set::iterator i=s.find(x);

i--;

cout<<*i<<endl;

s.erase(s.find(x));

}

hope it will help you and sorry for my poor English

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

The best thing you can do is: set<int> s;

  • When you are inserting an element in the set just do this: s.insert(-x);

  • And to get the maximum value of y<=x: auto lb=s.lower_bound(-x); if(lb!=s.end()) cout<<-*(lb);

→ Reply