比赛 |
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;
}