Ordered Set || PBDS || CPP
\n# Ordered set is a policy based data structure in g++ that keeps the unique elements in sorted order. It performs all the operations as performed by the set d
\n# ***Ordered set is a policy based data structure in g++ that keeps the unique elements in sorted order. It performs all the operations as performed by the set data structure in STL in log(n) complexity and performs two additional operations also in log(n) complexity .***\n\n    order_of_key (k) : Number of items strictly smaller than k .\n    find_by_order(k) : K-th element in a set (counting from zero).\n\n# ***For implementing ordered_set and GNU C++ library contains other Policy based data structures we need to include :***\n\n         Common file include <ext/pb_ds/assoc_container.hpp>\n         Including tree_order_statistics_node_update include <ext/pb_ds/tree_policy.hpp>\n\n\n# ***The first one is used to include the associative containers or group of templates such as set, multimap, map etc.The tree-based data structures which we will be using below is present in this header file. The second header file is used to include the tree_order_statistics_node update which is explained below:***\n\n         using namespace __gnu_pbds;\n\n# ***It is a namespace necessary for the GNU based Policy based data structures. The tree based container has a concrete structure but the necessary structure required for the ordered set implementation is :***\n\n         tree < int ,  null_type ,  less ,  rb_tree_tag ,  tree_order_statistics_node_update >\n\n# ***Additional Functions:***\n\n\n    find_by_order(k): It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time.To find the first element k must be zero. Let us assume we have a set s : {1, 5, 6, 17, 88}, then : *(s.find_by_order(2)) : 3rd element in the set i.e. 6 *(s.find_by_order(4)) : 5th element in the set i.e. 88\n\n    order_of_key(k) : It returns to the number of items that are strictly smaller than our item k in O(logn) time. Let us assume we have a set s : {1, 5, 6, 17, 88}, then : s.order_of_key(6) : Count of elements strictly smaller than 6 is 2. s.order_of_key(25) : Count of elements strictly smaller than 25 is 4.\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include <ext/pb_ds/assoc_container.hpp> \n#include <ext/pb_ds/tree_policy.hpp> \nusing namespace __gnu_pbds; \n\n#define ordered_set tree<pair<int,int>, null_type,greater<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> \nclass Solution {\npublic:\n    vector<int> resultArray(vector<int>& nums) {\n        vector<int>v1,v2;\n        ordered_set s1,s2;\n\n        v1.push_back(nums[0]);\n        s1.insert({nums[0],0});\n\n        v2.push_back(nums[1]);\n        s2.insert({nums[1],1});\n\n        for(int i = 2 ; i < nums.size() ; i++){\n            int sz1 = v1.size();\n            int sz2 = v2.size();\n\n            int g1 = s1.order_of_key({nums[i],i});\n            int g2 = s2.order_of_key({nums[i],i});\n\n            if(g1 > g2){\n                v1.push_back(nums[i]);\n                s1.insert({nums[i],i});\n            } \n            else if(g1 < g2){\n                v2.push_back(nums[i]);\n                s2.insert({nums[i],i});\n            }\n            else if(sz1 <= sz2){\n                v1.push_back(nums[i]);\n                s1.insert({nums[i],i});\n            }\n            else {\n                v2.push_back(nums[i]);\n                s2.insert({nums[i],i});\n            }\n        }\n\n        for(auto i : v2){\n            v1.push_back(i);\n        }\n        return v1;\n    }\n};\n```
['Array', 'Tree', 'Ordered Set', 'C++']