记录编号	589410	评测结果	AAAAAAAAAA
题目名称	充电宝	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	0.666 s
提交时间	2024-07-05 12:59:47	内存使用	126.66 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 4000005
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>0){
        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);
    line[cnt+1].l=n,line[cnt+1].r=n;
    ll num=1;
    for(int i=1;i<n;i++){
        while(num<=cnt){
            if(line[num].l<i){
                ad_(line[num].r,0-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;
}