题意：给定一个长度为 nn 的正整数序列 A1A_1, A2A_2, ⋯\cdots, AnA_n。定义一个函数 f(l,r)f(l,r) 表示：序列中下标在 [l,r][l,r] 范围内的子区间中，不同的整数个数。换句话说，f(l,r)f(l,r) 就是集合 {Al,Al+1,⋯ ,Ar}\{A_l,A_{l+1},\cdots,A_r\} 的大小，这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出 ∑l=1n∑r=ln(f(l,r))2\sum _{l=1} ^n \sum _{r=l} ^n (f(l,r)) ^2。由于答案可能很大，请输出答案对 109+710 ^9 +7 取模的结果。

考场上用暴力拿了 5050。。

最暴力的方法就是枚举左右端点，复杂度为 O(n2log⁡n)O(n ^2\log n)。

接下来有考虑算贡献，枚举 f(l,r)f(l,r) 的值再计算每个值的出现次数，但无法快速算出 f(l,r)f(l,r) 在多少区间内出现过。

这条路走不通，于是转而考虑计算序列里每个位置对答案得贡献。我们设 s(r)=∑l=1rf(l,r)2s ( r ) =\sum \limits_{l=1} ^r f(l,r) ^2，那么答案就是 ∑r=1ns(r)\sum \limits_{r=1} ^n s ( r )。

然后我们枚举 rr，用数据结构求出每个 s(r)s ( r ) 即可。

s(r+1)s(r+1) 可以由 s(r)s ( r ) 得到，我们考虑这样的变化，由 rr 到 r+1r+1 新多了一个数 ar+1a _{r+1}，设 last[i]last[i] 表示上一个等于 a[i]a[i] 的位置，否则为 00，那么这个数只有在 l∈[lastr+1+1,r+1]l\in [last _{r+1}+1,r+1] 的范围内才有贡献，因为他是这些区间内第一个这样的数，满足 f(l,r+1)=f(l,r)+1f(l,r+1)=f(l,r)+1，而其它区间由于不是第一次出现，没有贡献。

那么

s(r+1)−s(r)=f(r+1,r+1)2+∑l=lastr+1+1rf(l,r+1)2−f(l,r)2=1+∑l=lastr+1+1r(2f(l,r)+1)=2∑l=lastr+1+1rf(l,r)+(r−lastr+1−1+1)+1=2∑l=lastr+1+1rf(l,r)+r+1−lastr+1 s(r+1)-s ( r ) =f(r+1,r+1) ^2+\sum \limits_{l=last _{r+1}+1} ^{r} f(l,r+1) ^2 -f(l,r) ^2=1+\sum \limits_{l=last _{r+1}+1} ^{r} (2f(l,r)+1)=2\sum \limits_{l=last _{r+1}+1} ^{r} f(l,r)+(r-last _{r+1}-1+1)+1=2\sum \limits_{l=last _{r+1}+1} ^{r} f(l,r)+r+1-last _{r+1}

那么对于每一个 rr，我们很容易用一个区间查询的树状数组来维护 f(l,r)f(l,r) 来查询区间和， 同时对于 l∈[lastr+1,r+1]l\in [last _{r+1},r+1]，进行区间修改操作，+1+1。

最后记得离散化和开 long long。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const long long maxn=1000101;
const long long mod=1e9+7;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;long long f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
long long n,a[maxn],b[maxn],cnt,c[maxn];
long long last[maxn],t1[maxn],t2[maxn];
long long ans=0,num=0;
long long lowbit(long long x)
{
	return x&(-x);
}
void add(long long x,long long val)
{
	for(long long i=x;i<=n;i+=lowbit(i))
	{
		t1[i]+=val;
		t2[i]+=val*x;
	}
}
long long query(long long x)
{
	long long sum=0;
	for(long long i=x;i;i-=lowbit(i))
		sum+=t1[i]*(x+1)-t2[i];
	return sum;
}//标准维护差分数组，用于区间修改和区间查询的树状数组板子
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	cnt=unique(b+1,b+n+1)-b-1;
	for(long long i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+cnt+1,a[i])-b-1;
		last[i]=c[a[i]];
		c[a[i]]=i;
	}
	for(long long i=1;i<=n;i++)//枚举r
	{
		num=(num+i-last[i]+2*(query(i)-query(last[i])))%mod;//新的i，相当于上一个r+1，统计答案
		ans=(ans+num)%mod;
		add(last[i]+1,1);//i相当于r
		add(i+1,-1);
	}
	printf("%lld",ans%mod);
	return 0;
}