Lower bound and Upper bound showing opposite result in less_equal PBDS set.

Revision en1, by harshad2112, 2022-05-11 05:56:37

In recent Div4 contest, I was going through PBDS, and was using less_equal PBDS, where I found out that lower Bound shows result for the upper bound and vice versa. Here's the code for the following.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 4 6

Also If I use less instead of less_equal, it shows correct output.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 6 4

Help me if I am wrong.

Tags div4, pbds, set, 1676

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English harshad2112 2022-05-11 05:56:37 1265 Initial revision (published)