题面
给你一个长度为 (n) 的序列 ({a_i})，定义 (f(l,r)) 为 ([l,r]) 不同整数的个数，求 $$sum_{1le l le n}sum_{lle rle n}f(l,r)$$
题解
设 $$f(l,r)=sum_{i=l}^{r} [pre_i<l]$$其中 (pre_i) 为 上一次出现 (a_i) 的位置。
我们拆括号，考虑每一项的贡献。
对于形如 ([pre_i<l]^2) 的平方项，对结果产生的贡献是 (pre_i<lle i) 且 (rge i) 的二元组 ((l,r)) 的个数，即 ((i-pre_i) imes (n-i+1))。
对于形如 (2[pre_i<l][pre_j<l]) 的平方项，我们发现 ([pre_i<l]) 和 ([pre_j<l]) 是两个独立的条件，所以直接套用上面的式子，对结果产生的贡献是满足 (i) 和 (j) 的区间的交集。
我们依次考虑 (a_1,a_2,cdots,a_n) 和之前所有数的贡献。
对于 (pre_j<pre_i) 的 (j)，(l) 可选的范围是 ((pre_j,j])，(r) 可选的范围是 ([i,n])，对于 (pre_jge pre_i) 的 (j)，(l) 可选的范围是 ((pre_i,j])，不难发现是一个 (mbox{min}) 卷积的形式，按照上一场考试第二题的经验，我们可以用树状数组维护。
具体的，求的是 (sum_{j<i land pre_j<pre_i} (j-pre_j)) 和 (sum_{j<i land pre_jge pre_i} (pre_i-j)=(sum_{j<iland pre_jge pre_i}1) imes pre_i-sum_{j<i land pre_jge pre_i}j)，就可以用树状数组搞定了。
但是我们还有一个问题，就是第二种情况中，如果 (pre_i<j) ，结果应该是 (0)，而不是这个负的东西，所以重新定义 (j) 为 (pre_ile j<i) 的所有数，直接按原来的方法算，最后再用前缀和减一下就行了。
#include<bits/stdc++.h>
#define N 1005000
#define ri register int
#define LL long long
#define mod 1000000007
using namespace std;
inline int read() {
int ret=0,f=0; char ch=getchar();
while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
while (ch>='0' && ch<='9') ret*=10,ret+=ch-'0',ch=getchar();
return f?-ret:ret;
}
int n,a[N],aw[N],ton[N],pre[N];
struct node {
int x,v;
bool operator < (const node &rhs) const {
return x<rhs.x;
}
} b[N];
int add(int a,int b) {
a+=b; if (a>=mod) a-=mod;
return a;
}
int mul(int a,int b) {
LL c=a; c*=b;
return (int)(c%mod);
}
struct szsz {
int t1[N],t2[N],t3[N];
void insert(int x,int v) {
int tx=x; x++;
for (ri i=x;i<=n+1;i+=(i&(-i))) t1[i]++;
for (ri i=x;i<=n+1;i+=(i&(-i))) t2[i]=add(t2[i],v);
for (ri i=x;i<=n+1;i+=(i&(-i))) t3[i]=add(t3[i],v-tx);
}
int findgeval2(int x) {
int ret1=0;
for (ri i=n+1;i;i-=(i&(-i))) ret1=add(ret1,t3[i]);
int ret2=0;
for (ri i=x;i;i-=(i&(-i))) ret2=add(ret2,t3[i]);
return add(ret1,mod-ret2);
}
int findlcount(int x) {
int ret=0;
for (ri i=x;i;i-=(i&(-i))) ret=add(ret,t1[i]);
return ret;
}
int findlval1(int x) {
int ret=0;
for (ri i=x;i;i-=(i&(-i))) ret=add(ret,t2[i]);
return ret;
}
void clear() {
for (ri i=0;i<=n+1;i++) t1[i]=t2[i]=t3[i]=0;
}
} t;
int main() {
n=read();
for (ri i=1;i<=n;i++) a[i]=read();
for (ri i=1;i<=n;i++) aw[i]=a[i];
sort(aw+1,aw+n+1);
int nw=unique(aw+1,aw+n+1)-aw-1;
for (ri i=1;i<=n;i++) a[i]=lower_bound(aw+1,aw+nw+1,a[i])-aw;
for (ri i=1;i<=n;i++) {
pre[i]=ton[a[i]];
ton[a[i]]=i;
}
int ret=0;
for (ri i=1;i<=n;i++) {
int a3=t.findgeval2(pre[i]);
int a1=t.findlcount(pre[i]),a2=t.findlval1(pre[i]);
ret=add(ret,mul(2,mul(a3,n-i+1)));
ret=add(ret,mul(2,mul(add(a2,mod-mul(pre[i],a1)),n-i+1)));
t.insert(pre[i],i);
}
t.clear();
for (ri i=1;i<=n;i++) b[i]=(node){pre[i],i};
sort(b+1,b+n+1);
for (ri i=1,j=1;i<=n;i++) {
while (j<=b[i].x) t.insert(pre[j],j),j++;
int a1=t.findlcount(pre[b[i].v]),a2=t.findlval1(pre[b[i].v]);
ret=add(ret,mod-mul(mul(2,add(a2,mod-mul(pre[b[i].v],a1))),n-b[i].v+1));
}
for (ri i=1;i<=n;i++) ret=add(ret,mul(i-pre[i],n-i+1));
cout<<ret<<endl;
return 0;
}