CF1883F You Are So Beautiful

jcs_pp · 2025-10-15 19:28:55 · 题解

这题乍一看挺难的，没关系，我说过（其实并没有），做 CodeForces 的题的第一步是手推样例。

我们看一看下面一组样例。

10
1 2 1 2 3 3 2 1 3

如果你把为 1 2 3 的子序列列举出来就可以看到，要么开头往前跑，要么结尾往后跑。

可以证明，因为如果找到可以淘汰备选子串的子序列，它的元素顺序是不变的。所以只要头尾不跑开，中间元素因为要保持顺序，也没法跑出去。

那如何阻止头尾逃跑呢？

如果头元素为第一次出现，尾元素为最后一次出现，那么它们就都没地方跑，这个子串就符合要求。

代码实现：

对于一个位置，当这个位置为头元素时，它的贡献是它后面（包括它）所有最后出现的元素数量。这你要直接枚举的话，时间必爆。要用后缀和优化。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int T,n;
int a[N],sum[N];
map<int,int>mp;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n+1;i++) sum[i]=0;
        mp.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=n;i;i--){
            mp[a[i]]++;//技术思想 
            sum[i]=sum[i+1]+(mp[a[i]]==1);//后缀和 
        }
        long long ans=0;
        mp.clear();
        for(int i=1;i<=n;i++){
            mp[a[i]]++;
            ans+=sum[i]*(mp[a[i]]==1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}