记录编号	576562	评测结果	AAAAAAAAAA
题目名称	充电宝	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	2.462 s
提交时间	2022-10-12 11:41:49	内存使用	14.47 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,s,ans,res;
int a[200010],c[200010],f[200010],pre[200010],sum[200010];
struct node{
	int l,r,id;
}q[200010];
bool cmp(node x,node y){
	if(x.l/s!=y.l/s) {
		return x.l/s<y.l/s;
	}
	if((x.l/s)&1){
	    return x.r>y.r;
    }
	return x.r<y.r;
}
void add(int x){
	if(!sum[a[x]]){
		res++;
	}
	sum[a[x]]++;
}
void del(int x){
	sum[a[x]]--;
	if(!sum[a[x]]){
		res--;
	}
}
signed main(){
 	freopen("charger.in","r",stdin);
 	freopen("charger.out","w",stdout);
 	ios::sync_with_stdio(0);
 	cin.tie(0);
 	cout.tie(0);
 	cin>>n;
	s=sqrt(n);
	for(int i= 1;i<=n;i++){
	    cin>>a[i];
		pre[i]=n+1;
	}
	for(int i=1;i<=n;i++){
		if(pre[f[a[i]]]){
			pre[f[a[i]]]=i;
		}
		f[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		q[i].l=i+1;
		q[i].r=pre[i]-1;
		q[i].id=i;
	}
	sort(q+1,q+n+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=n;i++){
		while(l>q[i].l){
			add(--l);
		}
		while(l<q[i].l){
			del(l++);
		}
		while(r>q[i].r){
			del(r--);
		}
		while(r<q[i].r){
			add(++r);
		}
		ans+=res;
	}
	cout<<ans<<endl;
    return 0;
}