[数据结构与算法]2179. 统计数组中好三元组数目(BIT)

2179. 统计数组中好三元组数目(BIT)

数组一转化成递增序，然后对数组二进行置换。然后就是套BIT枚举y，求左边比y小和右边比y大的更数，乘法原理即可。

class Solution {
public:
#define lowbit(x) x&(-x)
    long long goodTriplets(vector<int>& a, vector<int>& b) {
        int n = a.size();
        vector<int>mp(n);
        for(int i=0;i<n;i++) mp[a[i]] = i;
        for(int i=0;i<n;i++) b[i] = mp[b[i]]+1;
        vector<int>f(n+5);
        auto upd = [&](int x,int v){
            while(x<=n){
                f[x]+=v;
                x+=lowbit(x);
            }
        };
        auto que = [&](int x){
            int s = 0;
            while(x){
                s+=f[x];
                x-=lowbit(x);
            }
            return s;
        };
        long long ans = 0;
        for(int i=0;i<n;i++){
            int x = que(b[i]);
            ans+=1LL * x * (n-b[i]-(i-x));
            upd(b[i],1);
        }     
        return ans;

    }
};