indexed_set.cpp

// WE ARE NOT HERE TO TAKE PART , WE ARE HERE TO TAKE OVER
#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 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
/*
Suppose that we want a data structure that supports all the operations as a set in C++ in addition to the following:

order_of_key(x): counts the number of elements in the set that are strictly less than x.
find_by_order(k): similar to find, returns the iterator corresponding to the k-th lowest element in the set (0-indexed).

you can use it fa3udh matesta3mel segment tree ya bro :) :) :) :) it's not faster than segment tree
but it's just double so no big deal .
*/
/*
typedef pair<int,int> pii;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
Tree<pii> o;
*/
void solve(){
ordered_set X;
    X.insert(1);
    X.insert(2);
    X.insert(4);
    X.insert(8);
    X.insert(16);

    cout<<*X.find_by_order(1)<<endl; // 2
    cout<<*X.find_by_order(2)<<endl; // 4
    cout<<*X.find_by_order(4)<<endl; // 16
    cout<<(end(X)==X.find_by_order(6))<<endl; // true

    cout<<X.order_of_key(-5)<<endl;  // 0
    cout<<X.order_of_key(1)<<endl;   // 0
    cout<<X.order_of_key(3)<<endl;   // 2
    cout<<X.order_of_key(4)<<endl;   // 2
    cout<<X.order_of_key(400)<<endl; // 5
    
    int pos = *x.find_by_order(ind);
	x.erase(pos); boom :)
	
}
	
	

 
int main() {
	
	int tc=1;

	while(tc--){
		solve();
	}

	return 0;
}

/*
   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
 
 
 */