title
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
示例 2：
输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
solution
记住涉及[a,b]之类的可以先排序第一个，再倒序第二个。
也可以按b的顺序把a的位置组成一个队列，此时左边小于当前元素的就是满足条件的。
class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
v2id = {}
for i in range(len(nums1)):
v2id[nums1[i]] = i
# 第二位倒序
d = [v2id[v] for v in nums2]
import sortedcontainers
s = sortedcontainers.SortedList()
import bisect
ans = 0
for i, v in enumerate(d):
k = bisect.bisect_left(s, v)
# 因为是[0,n-1], 然后就可以通过左边已知的小于v的数量k，算出i+1 - n-1 部分有多个个大于v的数量的了
right = n - 1 - v - (i - k)
s.add(v)
ans += k * right
return ans