//定义线段树
class segtree{
public:
segtree* leftNode = NULL;
segtree* rightNode = NULL;
int left = 0;
int right = 0;
int sum = 0;
segtree() = default;
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector
*/
void pushdown(segtree* root){
if(root->leftNode == NULL) {
root->leftNode = new segtree();
}
if(root->rightNode == NULL) {
root->rightNode = new segtree();
}
int mid = (root->left + root->right) >> 1;
root->leftNode->left = root->left;
root->leftNode->right = mid;
root->rightNode->left = mid+1;
root->rightNode->right = root->right;
}
//只更新current 所在的节点
void update(segtree* root, int current){
if(root == NULL) {
return;
}
if(current == root->left && current == root->right) {
root->sum++;
return;
}
if(current >= root->left && current <= root->right) {
root->sum++;
pushdown(root);
int mid = (root->left + root->right) >> 1;
update(root->leftNode, current);
update(root->rightNode, current);
return;
}
}
int query(segtree* root, int l, int r){
if(root == NULL) {
return 0;
}
if(root->left == root->right) {
return root->sum;
}
pushdown(root);
int mid = (root->left + root->right) >> 1;
int res = 0;
if(root->left >= l && root->right <= r) {//查询的范围包含了当前节点的范围
return root->sum;
}
if(l > root->right || r < root->left) { //查询的范围不包含当前节点的范围
return 0;
}
//查询的范围和当前节点范围存在交集
if(l <= mid) {
res += query(root->leftNode, l, r);
}
if(r > mid){
res += query(root->rightNode, l, r);
}
return res;
}
vector<int> smallerCount(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 0);
segtree* root = new segtree();
root->left = -10000;
root->right = 10000;
res[n-1] = 0;
for (int i = n-2; i >= 0; i--) {
update(root, nums[i+1]);
res[i] = query(root,-10000, nums[i]-1);
}
return res;
}
};