structSeg { int mi, ma, count; Seg *l, *r; Seg(vector<int>& A, int le, int ri) : mi(A[le]), ma(A[ri]), count(0), l(nullptr), r(nullptr){ if(le == ri) return; int m = le + (ri - le) / 2; l = newSeg(A, le, m); r = newSeg(A, m + 1, ri); } intquery(int s, int e){ if(mi > e or ma < s) return0; if(s <= mi and ma <= e) return count; return (l ? l->query(s, e) : 0) + (r ? r->query(s, e) : 0); } intinsert(int n){ if(mi <= n and n <= ma) { count++; if(l) l->insert(n); if(r) r->insert(n); } } };
classSolution{ Seg* seg; int mi; voidbuild(vector<int> A){ sort(begin(A), end(A)); A.erase(unique(begin(A), end(A)), end(A)); mi = A[0]; seg = newSeg(A, 0, A.size() - 1); } public: vector<int> constructLowerArray(int *arr, int n){ vector<int> res(n), A; for(int i = 0; i < n; i++) A.push_back(arr[i]);
build(A);
for(int i = n - 1; i >= 0; i--) { res[i] = seg->query(mi, A[i] - 1); seg->insert(A[i]); } return res; } };