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 ?
You can use
std::set. Type 1 can be handled using simple insert. For type 2 queries, you canupper_boundon 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.You can use
stl::setand do alower_boundbut withrbegin()andrend()and usegreater<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_boundnormally, likeset<int, greater<int>> sethen you can use*se.lower_bound(6)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).
Without STL , I think balanced tree may be a better choice. For query 1,you can simply insert x into the tree For query 2,you can first find if x exists in the tree.If not ,than search the prefix of x. You can use Treap(https://en.wikipedia.org/wiki/Treap) ,or Splay(https://en.wikipedia.org/wiki/Splay_tree)
Time Complexity $$$O(\log n)$$$,though the constant may be big.But it's still faster than STL set.
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
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);