# Divide and conquer (like merge sort) / order statistics tree

• ``````// Count of Smaller Numbers After Self
// divide and conquer
typedef pair<int, int> pii;
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
vector<pii> a, b;
vector<int> 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<int> countSmaller(vector<int>& 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 <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef pair<int, int> pii;
#define ROF(i, a, b) for (int i = (b); --i >= (a); )

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
tree<pii, null_type, less<pii>, 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;
}
};
``````

Sadly, Policy-Based Data Structures seem unavailable.

``````Line 3: ‘__gnu_pbds’ is not a namespace-name
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.