1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// 2179. Count Good Triplets in an Array
#include "leetcode.h"
/*
* 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
* three distinct values which are present in increasing order by position in
* both '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)'. return the total
* number of good triplets.
*/
#define MAX_SIZE 100010
static int tree[MAX_SIZE];
void tree_push(int idx, int val, int n) {
idx++;
while (idx <= n + 2) {
tree[idx] += val;
idx += idx & (-idx);
}
}
int tree_query(int idx) {
idx++;
int res = 0;
while (idx > 0) {
res += tree[idx];
idx -= idx & (-idx);
}
return res;
}
long long goodTriplets(int *nums1, int nums1Size, int *nums2, int nums2Size) {
int n = nums1Size, p2v[MAX_SIZE], arr[MAX_SIZE], left[MAX_SIZE] = {0};
for (int i = 0; i < n; i++)
p2v[nums2[i]] = i;
for (int i = 0; i < n; i++)
arr[i] = p2v[nums1[i]];
memset(tree, 0, sizeof(tree));
for (int i = 0; i < n; i++) {
left[i] = tree_query(arr[i] - 1);
tree_push(arr[i], 1, n);
}
memset(tree, 0, sizeof(tree));
long long ans = 0;
for (int i = n - 1; i >= 0; i--) {
int right = tree_query(n - 1) - tree_query(arr[i]);
ans += (long long)left[i] * right;
tree_push(arr[i], 1, n);
}
return ans;
}
int main() {
int n11[] = {2, 0, 1, 3}, n21[] = {0, 1, 2, 3};
int n12[] = {4, 0, 1, 3, 2}, n22[] = {4, 1, 0, 2, 3};
printf("%lld\n",
goodTriplets(n11, ARRAY_SIZE(n11), n21, ARRAY_SIZE(n21))); // expect: 1
printf("%lld\n",
goodTriplets(n12, ARRAY_SIZE(n12), n22, ARRAY_SIZE(n22))); // expect: 4
}
|