AeonARY's blog

By AeonARY, history, 2 months ago, In English

Problem: give an array A of N (1 <= N <= 2 * 10^6) integer. Find the number of good triplets (i, j, k), where i, j, k are all distinct indices such that 1 <= i < j < k <= N. A good triplet (i, j, k) is a triplet such that A[i] = x, A[j] = y, A[k] = z(x, y, z are given numbers).

Example 1:

Input: 5

1 2 2 1 2

1 2 1

Output:

2

Explanation: two triplets are (1,2,4) and (1,3,4)

Example 2:

Input:

5

1 2 2 1 2

2 1 1

Output:

0

Explanation: there are no good triplets

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Spoiler
»
2 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

you can use frequency array or map as you wish and use product to calculate the answer freq[x]*freq[y]*freq[z]if they are distinct.