题意

竞赛被定义为一个包含 $N$（$1\le N\le 10^6$）个整数的数组 $a_1, a_2, \dots, a_N$（$1\le a_i\le N$）。Farmer John 定义哞叫为一个包含三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。一种哞叫被称为在竞赛中发生，如果可以从数组中移除整数，直到只剩下这一哞叫。

由于 Bessie 据称「在整个竞赛中一直哞哞叫」，请帮助 Elsie 计算竞赛中发生的不同哞叫的数量！两种哞叫是不同的，如果它们并非由相同的整数以相同的顺序组成。

即给定一个序列，求有多少个“ABB”子序列。

思路

进行预处理，求出前 $i$ 个字符中出现的不同元素数 $s_i$，顺便记录元素 $a_i$ 第一次出现的位置。

我们从后往前扫，遇到出现两次的整数“ B ”就根据前面出现过的“ A ”种类数，计算后两个整数为“ B ”的方案数。由于取的是最后两个“ B ”，所以一定会包含所有的可能。注意排除“ BBB ”，即“ B ”如果首次出现在最后两个“ B ”之前，要排除掉。

实现

记得开 long long。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int a[N],b[N],c[N],s[N];
LL res;
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);
	for(int i = 1; i <= n; i ++)
		if(!c[a[i]]) c[a[i]] = i,s[i] = s[i - 1] + 1;
		else s[i] = s[i - 1];
	for(int i = n; i >= 1; i --)
		if(++ b[a[i]] == 2) res += s[i - 1] - (c[a[i]] < i);
	cout<<res<<endl;
	return 0;
}

复杂度 $O(n)$，可以通过。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N], dif[N], cnt[N];
long long ans = 0;
 
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        if (cnt[a[i]] == 1)dif[i]=dif[i-1]+1;else dif[i]=dif[i-1];
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = n; i >= 1; i--) {
        cnt[a[i]]++;
        if (cnt[a[i]] == 2) ans += dif[i-1];
    }
    for (int i = 1; i <= n; i++) if (cnt[i] >= 3) ans--;
    cout << ans;
    return 0;
}