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 &lt;= x, y, z &lt;= n - 1, such that pos1x &lt; pos1y &lt; pos1z and pos2x &lt; pos2y &lt; pos2z.

Return the total number of good triplets.

&nbsp;
Example 1:

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation: 
There are 4 triplets (x,y,z) such that pos1x &lt; pos1y &lt; pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). 
Out of those triplets, only the triplet (0,1,3) satisfies pos2x &lt; pos2y &lt; pos2z. Hence, there is only 1 good triplet.


Example 2:

Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).


&nbsp;
Constraints:


	n == nums1.length == nums2.length
	3 &lt;= n &lt;= 105
	0 &lt;= nums1[i], nums2[i] &lt;= n - 1
	nums1 and nums2 are permutations of [0, 1, ..., n - 1].


from sortedcontainers import SortedList
class Solution:
    def goodTriplets(self, A: List[int], B: List[int]) -> int:
        # Index of a (from A) in B.
        pos = [0] * len(A)               
        for idx, b in enumerate(B):
            pos[b] = idx
        
        # Build pre_a[i]: number of elements on a[i]'s left in both A and B.
        # pos_in_b: sorted indexes (in B) of all the visited elements in A.
        pos_in_b, pre_a = SortedList([pos[A[0]]]), [0]      
        for a in A[1:]:       
            pos_in_b.add(pos[a])
            pre_a.append(pos_in_b.bisect_left(pos[a]))
    
        # Build suf_a[i]: number of elements on a[i]'s right in both A and B.
        pos_in_b, suf_a = SortedList([pos[A[-1]]]), [0]
        for a in reversed(A[:len(A)-1]):
            idx = pos_in_b.bisect(pos[a])
            suf_a.append(len(pos_in_b) - idx)
            pos_in_b.add(pos[a])
        suf_a.reverse()
        
        # Sum up all unique triplets centered on A[i].
        ans = 0
        for x, y in zip(pre_a, suf_a):
            ans += x * y
        return ans
class Solution {
    public long goodTriplets(int[] nums1, int[] nums2) {
        int n= nums1.length;
        int indices[]= new int[n];
        for(int i=0;i<n;i++)
        {
            indices[nums2[i]]=i;
        }
        int B[]= new int[n];
        for(int i=0;i<n;i++)
        {
            B[i]=indices[nums1[i]];
            B[i]++;
        }
        Fenw L=new Fenw(n+1);
        long []left= new long[n+1];
        long []right= new long[n+1];
        for(int i=1;i<=n;i++)
        {
            left[i]=L.sum(B[i-1]-1);
            L.update(B[i-1],1);
        }
         Fenw R=new Fenw(n+1);
        for(int i=n;i>0;i--)
        {
            right[i]=R.sum(n)-R.sum(B[i-1]);
            R.update(B[i-1],1);
        }
        long ans=0l;
        for(int i=0;i<=n;i++)
        {
            ans+=left[i]*right[i];
        }
        return ans;
    }
}
class Fenw
{
    long[]farr;
    int n;
    Fenw(int n)
    {
        this.n=n;
        farr=new long[n+1];
    }
    void update(int index, int val)
    {
        int c=0;
        for(int i=index;i<=n;i+=(i&-i))
        {
            c++;
            farr[i]+=val;
        }
    }
   
    long sum(int index)
    {
        long ans=0l;
        for(int i=index;i>0;i-=(i&-i))
        {
            ans+=farr[i];
        }
        return ans;
    }
}
typedef long long ll;
typedef long double ld;
#define mod 1000000007
#define all(x) begin(x),end(x)
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


class Solution {
public:
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mapping;
        int no = 1;
        for (int x : nums1){
            mapping[x] = no;
            no++;
        }
        for (int i = 0; i < nums2.size(); ++i)
            nums2[i] = mapping[nums2[i]];
        int n = nums2.size();
        ordered_set st1;
        ordered_set st2;
        for (int x : nums2)
            st2.insert(x);
        ll ans = 0;
        st1.insert(nums2[0]);
        st2.erase(st2.find(nums2[0]));
        for (int i = 1; i < n - 1; ++i)
        {
            st2.erase(st2.find(nums2[i]));
            ll less = (ll)st1.order_of_key(nums2[i]);
            ll great = (ll) (((int)st2.size()) - st2.order_of_key(nums2[i]));
            ans += (less * great);
            st1.insert(nums2[i]);
        }
        return ans;
    }
};
var goodTriplets = function(nums1, nums2) {
  let n = nums1.length, nums2_idx = Array(n);
  for (let i = 0; i < n; i++) nums2_idx[nums2[i]] = i;
  let idxs = Array(n);
  for (let i = 0; i < n; i++) idxs[i] = nums2_idx[nums1[i]];

  let smallerLeft = getSmallerLeft(idxs); // smallerLeft[i] = number of indices to the left of i smaller than idxs[i] in both nums1 and nums2
  let biggerRight = getBiggerRight(idxs); // biggerRight[i] = number of indices to the right of i bigger than idxs[i] in both nums1 and nums2
  let ans = 0;
  for (let i = 1; i < n - 1; i++) {
    ans += smallerLeft[i] * biggerRight[i];
  }
  return ans;
};

function getSmallerLeft(idxs) {
  let n = idxs.length, res = Array(n).fill(0);
  let segTree = new SegmentTree(n);
  for (let i = 0; i < n; i++) {
    res[i] = segTree.getSum(0, idxs[i] - 1);
    segTree.update(idxs[i], 1);
  }
  return res;
}

function getBiggerRight(idxs) {
  let n = idxs.length, res = Array(n).fill(0);
  let segTree = new SegmentTree(n);
  for (let i = n - 1; i >= 0; i--) {
    res[i] = segTree.getSum(idxs[i] + 1, n - 1);
    segTree.update(idxs[i], 1);
  }
  return res;
}

class SegmentTree {
  constructor(n) {
    this.size = n;
    this.segTree = Array(n * 2).fill(0);
  }
  update(index, val) {
    let n = this.size, idx = index + n;
    this.segTree[idx] += val;
    idx = Math.floor(idx / 2);

    while (idx > 0) {
      this.segTree[idx] = this.segTree[idx * 2] + this.segTree[idx * 2 + 1];
      idx = Math.floor(idx / 2);
    }
  }
  getSum(left, right) {
    let n = this.size, sum = 0;
    let left_idx = left + n, right_idx = right + n;
    // left must be even, right must be odd
    while (left_idx <= right_idx) {
      if (left_idx % 2 === 1) sum += this.segTree[left_idx++];
      if (right_idx % 2 === 0) sum += this.segTree[right_idx--];
      left_idx = Math.floor(left_idx / 2);
      right_idx = Math.floor(right_idx / 2);
    }
    return sum;
  }
}
Count Good Triplets in an Array