比赛 2024暑假C班集训5 评测结果 EEAEEEEEEE
题目名称 充电宝 最终得分 10
用户昵称 flyfree 运行时间 1.591 s
代码语言 C++ 内存使用 43.88 MiB
提交时间 2024-07-05 10:20:34
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000005
ll a[MAXN],used[MAXN],s[MAXN];
ll n,ans,cnt;
struct node{
    ll l,r;
}line[MAXN];
bool cmp(node a,node b){
    return a.l<b.l;
}
ll lowbit(ll idx){
    return idx&(-idx);
}
ll ad_(ll idx,ll f){
    while(idx<=n){
        s[idx]+=f;
        idx+=lowbit(idx); 
    }
}
ll re_(ll idx){
    ll ans=0;
    while(idx){
        ans+=s[idx];
        idx-=lowbit(idx);
    }
    return ans;
}
int main(){
    freopen("charger.in","r",stdin);
    freopen("charger.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!used[a[i]]){
            used[a[i]]=i;
        }else{
            line[++cnt].l=used[a[i]],line[cnt].r=i;
            used[a[i]]=i;
            ad_(i,1);
        }
    } 
    sort(line+1,line+1+cnt,cmp);
    ll num=1;
    for(int i=1;i<n;i++){
        while(num<=cnt){
            if(line[num].l<i){
                ad_(line[num].r,-1);
                num++;
            }else break;
        }
        if(line[num].l==i){
            ans+=line[num].r-i-re_(line[num].r);
        }else{
            ans+=n-i-re_(n);
        }
    }
    cout<<ans;
    return 0;
}