首页 > itarticle > codeforces 1004 c

codeforces 1004 c

admin 1月 18, 2021 0

链接：

http://codeforces.com/contest/1004/problem/C

题意：

给定一个数列，求不同的（$a_i$,$b_j$）i<j的数量

思路：

去重加计数。

代码：


#include <bits/stdc++.h>
using namespace std;

int s[100005];
int unq[100005];
bool vis[100005];
set<int> ss;
int ()
{
    memset(vis,0,sizeof vis);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&s[i]);
    }
    for(int i=n-1;i>=0;i--)
    {
        ss.insert(s[i]);
        unq[i]=ss.size();
    }
    long long ans=0;
    for(int i=0;i<n-1;i++)
    {
        if(vis[s[i]]==false){
            ans+=unq[i+1];
            vis[s[i]]=true;
        }else{
            continue;
        }
    }
    cout<<ans<<endl;
    return 0;
}