Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /************************************************************************************************
- The order-statistics tree supports the same operations as the set
- * find_by_order(k) : iterator to the kth smallest integer counting from 0
- * order_of_key(item): number of items in a set that are strictly smaller than our item
- **********************************************************************************************/
- #include <ext/pb_ds/assoc_container.hpp> // Common file
- #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
- using namespace __gnu_pbds;
- typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>OS;
- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- OS 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
- }
Add Comment
Please, Sign In to add comment