pb_ds tree

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

using namespace std;
using namespace __gnu_pbds;

typedef __gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbt;


int main()
{
    rbt T;


    //insert()
    T.insert(9);
    T.insert(1);
    T.insert(3);
    T.insert(3);
    T.insert(5);
    T.insert(10);

    printf("T:\n");
    for(auto x : T)
        printf("%d ", x); // 1 3 5 9 10
    puts("\n");


    //erase()
    T.erase(1);

    printf("T:\n");
    for(auto x : T)
        printf("%d ", x); // 3 5 9 10
    puts("\n");


    //find()
    auto a = T.find(10);
    auto b = T.find(11);

    puts((a == T.end() ? "Not Find 10" : "Find 10")); // Find 10
    puts((b == T.end() ? "Not Find 11" : "Find 11")); // Not Find 11
    puts("");


    //lower_bound(), upper_bound()
    a = T.lower_bound(5);
    b = T.upper_bound(5);

    printf("a = %d\n", *a); // 5
    printf("b = %d\n", *b); // 9
    puts("");


    //find_by_order()
    auto x = T.find_by_order(0);
    auto y = T.find_by_order(1);
    auto z = T.find_by_order(5);

    if(x == T.end())            // 3
        printf("not find\n");
    else
        printf("%d\n", *x);

    if(y == T.end())            // 5
        printf("not find\n");
    else
        printf("%d\n", *y);

    if(z == T.end())            // not find
        printf("not find\n");
    else
        printf("%d\n", *z);
    puts("");


    //order_of_key()
    printf("%d\n", T.order_of_key(3));  // 0
    printf("%d\n", T.order_of_key(5));  // 1
    printf("%d\n", T.order_of_key(11)); // 4
    puts("");


    //traverse
    for(auto i = T.begin(); i != T.end(); ++i) // 3 5 9 10
        printf("%d ", *i);
    puts("\n");

    //clear()
    T.clear();


    return 0;
}