indexed set

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// Define the indexed_set using a tree structure with order statistics
using isType = int;
typedef tree<isType, null_type, less<isType>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main() {
    // Create an indexed_set
    indexed_set s;

    // Insert elements into the indexed_set
    s.insert(5);
    s.insert(1);
    s.insert(10);
    s.insert(3);

    // Print the elements in the indexed_set (they are stored in sorted order)
    cout << "Elements in the set: ";
    for (auto x : s)
        cout << x << " "; // Output: 1 3 5 10
    cout << endl;

    // Find the k-th smallest element (0-indexed)
    cout << "1st smallest element: " << *s.find_by_order(0) << endl; // Output: 1
    cout << "2nd smallest element: " << *s.find_by_order(1) << endl; // Output: 3
    cout << "3rd smallest element: " << *s.find_by_order(2) << endl; // Output: 5

    // Find the number of elements strictly less than a given value
    cout << "Number of elements less than 5: " << s.order_of_key(5) << endl; // Output: 2
    cout << "Number of elements less than 6: " << s.order_of_key(6) << endl; // Output: 3

    // Erase an element
    s.erase(3);
    cout << "After erasing 3, elements in the set: ";
    for (auto x : s)
        cout << x << " "; // Output: 1 5 10
    cout << endl;

    return 0;
}