2179. Count Good Triplets in an Array

You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, …, n - 1].

A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1v as the index of the value v in nums1 and pos2v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.

Return the total number of good triplets.

class Solution {
    map<int, int> indexMap;
    void update(vector<long long>& fenwick, int index, int value) {
        while(index < fenwick.size()) {
            fenwick[index] += value;
            index = index + (index & -index);
        }
    }
    
    long long sum(vector<long long>& fenwick, int index) {
        long long result = 0;
        while(index > 0) {
            result += fenwick[index];
            index = index - (index & -index);
        }
        return result;
    }
public:
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        for(int i = 0; i < nums1.size(); i++) {indexMap[nums1[i]] = i;}
        vector<long long> fenwickLeft(100003), fenwickRight(100003);
        vector<long long> sumLeft(nums1.size()), sumRight(nums1.size());
        for(int i = 0; i < nums2.size(); i++) {
            nums2[i] = indexMap[nums2[i]] + 1;
        }
        
        for(int i = 0; i < nums1.size(); i++) {
           sumLeft[i] = sum(fenwickLeft, nums2[i] - 1);
           update(fenwickLeft, nums2[i], 1);
        }
        
        for(int i = nums1.size() - 1; i >= 0; i--) {
            sumRight[i] = sum(fenwickRight, n) - sum(fenwickRight, nums2[i]);
            update(fenwickRight, nums2[i], 1);
        }
        
        long long res = 0;
        
        for(int i = 0; i < n; i++)
            res += sumLeft[i] * sumRight[i];
        
        return res;
    }
};