/// Add / remove elements
/// No of elements < X
/// k-th smallest element
/// min / max
/// Time complexity = log(n)
#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_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int main()
{
/// Add elements in any random order
pbds A;
A.insert(11);
A.insert(1);
A.insert(5);
A.insert(3);
A.insert(7);
A.insert(9);
A.insert(3);
//Total contents
cout << "1, 3, 3 ,5, 7, 9, 11" << endl;
//K-th smallest
int k = 3;
cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
int X = 9;
cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
//DELETE Elements
cout << "Deleted 3" << endl;
A.erase(A.find(3));
//Total contents
cout << "1, 3 ,5 ,7, 9, 11" << endl;
//NO OF ELEMENTS < X
X = 9;
cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
k = 3;
cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
return 0;
}
Ly8vIEFkZCAvIHJlbW92ZSBlbGVtZW50cwovLy8gTm8gb2YgZWxlbWVudHMgPCBYCi8vLyBrLXRoIHNtYWxsZXN0IGVsZW1lbnQKLy8vIG1pbiAvIG1heAovLy8gVGltZSBjb21wbGV4aXR5ID0gbG9nKG4pCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CiNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKdHlwZWRlZiB0cmVlPGludCwgbnVsbF90eXBlLCBsZXNzX2VxdWFsPGludD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+IHBiZHM7CmludCBtYWluKCkKewogICAgLy8vIEFkZCBlbGVtZW50cyBpbiBhbnkgcmFuZG9tIG9yZGVyCiAgICBwYmRzIEE7CiAgICBBLmluc2VydCgxMSk7CiAgICBBLmluc2VydCgxKTsKICAgIEEuaW5zZXJ0KDUpOwoJQS5pbnNlcnQoMyk7CglBLmluc2VydCg3KTsKCUEuaW5zZXJ0KDkpOwoJQS5pbnNlcnQoMyk7CgoJLy9Ub3RhbCBjb250ZW50cwoJY291dCA8PCAiMSwgMywgMyAsNSwgNywgOSwgMTEiIDw8IGVuZGw7CgoJLy9LLXRoIHNtYWxsZXN0CglpbnQgayA9IDM7Cgljb3V0IDw8IGsgPDwgInJkIHNtYWxsZXN0OiAiIDw8ICpBLmZpbmRfYnlfb3JkZXIoay0xKSA8PCBlbmRsOwoKCS8vTk8gT0YgRUxFTUVOVFMgPCBYCglpbnQgWCA9IDk7CgoJY291dCA8PCAiTm8gb2YgZWxlbWVudHMgbGVzcyB0aGFuICIgPDwgWCA8PCAiIGFyZSAiIDw8IEEub3JkZXJfb2Zfa2V5KFgpIDw8IGVuZGw7CgoJLy9ERUxFVEUgRWxlbWVudHMKICAgIGNvdXQgPDwgIkRlbGV0ZWQgMyIgPDwgZW5kbDsKICAgIEEuZXJhc2UoQS5maW5kKDMpKTsKCiAgICAvL1RvdGFsIGNvbnRlbnRzCgljb3V0IDw8ICIxLCAzICw1ICw3LCA5LCAxMSIgPDwgZW5kbDsKCQoJLy9OTyBPRiBFTEVNRU5UUyA8IFgKCVggPSA5OwoKCWNvdXQgPDwgIk5vIG9mIGVsZW1lbnRzIGxlc3MgdGhhbiAiIDw8IFggPDwgIiBhcmUgIiA8PCBBLm9yZGVyX29mX2tleShYKSA8PCBlbmRsOwoJCgoJayA9IDM7Cgljb3V0IDw8IGsgPDwgInJkIHNtYWxsZXN0OiAiIDw8ICpBLmZpbmRfYnlfb3JkZXIoay0xKSA8PCBlbmRsOwoKCgoJcmV0dXJuIDA7Cn0K
1, 3, 3 ,5, 7, 9, 11
3rd smallest: 3
No of elements less than 9 are 5
Deleted 3
1, 3 ,5 ,7, 9, 11
No of elements less than 9 are 5
3rd smallest: 3