自动搬运

查看原文

来自洛谷，原作者为

	xdd 赶紧低估自己 || 代词使用她（但是实际上是他） || 可互私信喵 || 但建议不要理会这个没勾的傻逼 || 最高估值排名 915 但估值屁用没有所以现在反名歧

搬运于2025-08-24 23:09:19，当前版本为作者最后更新于2025-02-04 11:36:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先容易想到，如果一个数出现两次，那么答案就增加这个数字前面与他不同的数字的种类，比如样例 #1 中，因为数字 $4$ 出现了大于两次，答案就为 $4$ 前面的数字种类 $3$ 种，计数可以使用桶计数实现。

以上算法如果直接倒着遍历，复杂度是 $\mathcal{O}(n^2)$ 的，会 TLE。

复杂度的瓶颈在于找到两个相同数字后的向前的查找，定义 $sum_i$ 为截止第 $i$ 位前面的数字种类，这里用前缀和实现，如果发现了新的数字，就把这个位置设为 $1$，其他位置设为 $0$，做一个前缀和，查找到两个相同数字后，就 $ans\leftarrow ans+sum_{i-1}$。

最后，因为会出现 1 1 1 这样三个数字相同的情况，因为前面我们给每个数字做了计数，遍历数列里每个数字，对于某个数字，如果出现了 $3$ 次及以上，那么他肯定至少有一个类似上面的错解，$ans\leftarrow ans-1$。

#include<bits/stdc++.h>
#define endl '\n'
#define maxn 1000000+5
#define int long long
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
int n,a[maxn],cnt[maxn],sum[maxn],ans;
bool flag[maxn];
signed main(){
    cin >> n;
    //预处理
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(flag[a[i]]==0){
            sum[i]++;
        }
        flag[a[i]]=1;
        sum[i]+=sum[i-1];
    }
    //找解
    for(int i=n;i>=1;i--){
        cnt[a[i]]++;
        if(cnt[a[i]]==2){
            ans+=sum[i-1];
        }
    }
    //最后检查错解
    for(int i=1;i<=n;i++){
        if(cnt[i]>=3){
            ans--;
        }
    }
    cout << ans;
    return 0;
}