题解：P11668 [USACO25JAN] It's Mooin' Time II B

_xdd_ · 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;
}