LeetCode/cs/count-good-triplets-in-an-array.cs

public class Solution {
    private class FenwickTree {
        private int[] tree;

        public FenwickTree(int size) {
            tree = new int[size + 1];
        }

        public int this[int i] {
            get {
                var res = 0;

                for (++i; i > 0; i -= i & -i) {
                    res += tree[i];

                }

                return res;
            }
            set {
                for (++i; i < tree.Length; i += i & -i) {
                    tree[i] += value;
                }
            }
        }
    }

    public long GoodTriplets(int[] nums1, int[] nums2) {
        var n = nums1.Length;

        var pos2 = new int[n];
        for (var i = 0; i < n; ++i) {
            pos2[nums2[i]] = i;
        }

        var reversedMapping = new int[n];
        for (var i = 0; i < n; ++i) {
            reversedMapping[pos2[nums1[i]]] = i;
        }

        long count = 0;

        var t = new FenwickTree(n);
        for (var value = 0; value < n; ++value) {
            var pos = reversedMapping[value];

            var left = t[pos];
            t[pos] = 1;

            var right = (n - 1 - pos) - (value - left);
            count += (long)left * right;
        }

        return count;
    }
}