// Count of Smaller Numbers After Self // divide and conquer typedef pair pii; #define REP(i, n) for (int i = 0; i < (n); i++) class Solution { vector a, b; vector c; void f(int l, int r) { if (r-l <= 1) return; int m = l+(r-l)/2; f(l, m); f(m, r); for (int i = l, j = m, k = l; i < m || j < r; ) if (j == r || i < m && a[i].first <= a[j].first) { c[a[i].second] += j-m; b[k++] = a[i++]; } else b[k++] = a[j++]; copy(b.begin()+l, b.begin()+r, a.begin()+l); } public: vector countSmaller(vector& nums) { int n = nums.size(); a.resize(n); b.resize(n); c.assign(n, 0); REP(i, n) a[i] = pii{nums[i], i}; f(0, n); return c; } }; // order statistics tree #include #include using namespace __gnu_pbds; typedef pair pii; #define ROF(i, a, b) for (int i = (b); --i >= (a); ) class Solution { public: vector countSmaller(vector& nums) { tree, rb_tree_tag, tree_order_statistics_node_update> tr; ROF(i, 0, nums.size()) { tr.insert(pii{nums[i], i}); nums[i] = tr.order_of_key(pii{nums[i], 0}); } return nums; } };