力扣315.计算右侧小于当前元素的个数

力扣315.计算右侧小于当前元素的个数

• 离散化 + 树状数组

•   const int N = 100010;int tr[N],n;class Solution {public:vector<int> countSmaller(vector<int>& nums) {n = nums.size();vector<int> tmp(nums);vector<int> res(n);memset(tr,0,sizeof tr);ranges::sort(tmp);int l = unique(tmp.begin(),tmp.end()) - tmp.begin();for(int i=0;i<n;i++)nums[i] = lower_bound(tmp.begin(),tmp.begin()+l,nums[i]) - tmp.begin() + 1;for(int i=n-1;i>=0;i--){int val = nums[i];cout<<val<<" ";res[i] = query(val - 1);cout<<tr[1]<<endl;add(val,1);}return res;}int lowbit(int x){return x&-x;}int query(int x) {int ret = 0;while (x) {ret += tr[x];x -= lowbit(x);}return ret;}void add(int x, int k) {while (x < n) {tr[x] += k;x += lowbit(x);}}};