STRATEGY: 求关于区间的不重复元素数的基本思路：用线段树维护 F(i,r)
那么这一提就很简单了。把原题中的式子看成对于每一个枚举的右端点r,\(\sum_{i\le r}f(i,r)\)造一棵线段树，维护一个数组\(g[i\in [1,n]]\) 表示i到当前右端点r的f(i,r)。考虑每次移动右端点造成的影响。
显然，记上一个a[r]出现的位置为j（如果a[r]是第一次出现j就是0），那么发现g[j+1...r]都会++，于是，若用sum记录每一个r的答案，则sum+=\(r-j+2\times\sum_{i=j+1...r}g[i]\)
则把每一次的sum加起来就是答案
另，卡常
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e9+7;
int n,a[N],t[N<<2],tag[N<<2];
map<int,int>M;
inline void pushup(int k){t[k]=t[k<<1]+t[k<<1|1];}
inline void pushdown(int l,int r,int k){
if(!tag[k])return;
register int mid=l+r>>1;
tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
t[k<<1]+=tag[k]*(mid-l+1)%mod;
t[k<<1|1]+=tag[k]*(r-mid)%mod;
tag[k]=0;
}
inline void add(int L,int R,int l,int r,int k){
if(L<=l&&r<=R){t[k]+=r-l+1;tag[k]++;return;}
pushdown(l,r,k);
register int mid=l+r>>1;
if(L<=mid)add(L,R,l,mid,k<<1);if(R>mid)add(L,R,mid+1,r,k<<1|1);
pushup(k);
}
inline int ask(int L,int R,int l,int r,int k){
if(L<=l&&r<=R)return t[k];
pushdown(l,r,k);
register int mid=l+r>>1,ans=0;
if(L<=mid)ans+=ask(L,R,l,mid,k<<1);if(R>mid)ans+=ask(L,R,mid+1,r,k<<1|1);
return ans;
}
inline int read(){
register char ch=getchar();register int x=0,f=1;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
signed main(){
n=read();for(register int i=1;i<=n;i++)a[i]=read();
int sum=0,ans=0;
for(register int i=1;i<=n;i++){
register int &j=M[a[i]];
sum+=2*ask(j+1,i,0,n,1)%mod+i-j;sum%=mod;
add(j+1,i,0,n,1);
j=i;ans=(ans+sum)%mod;
}cout<<ans;
}