原题链接
看到形如 $\sum_{l=1}^{n} \sum_{r=l}^n $ 两个 \(sum\) 叠加的形式，考虑枚举单独一维来统计一个端点固定的子序列贡献。
尝试枚举右端点，记 \(g(r) = \sum_{l=1}^{r} f(l,r)^2\) ，此时我们需要知道如何从 \(g(r)\) 转移到 \(g(r+1)\) 才能在枚举右端点时通过某种方式维护 \(g\) 的贡献。
对于区间颜色个数，加入一个新的右端点 \(r+1\)，会对以 \(l \in [pre_r+1,r+1]\) 为左端点的区间的 \(f\) 函数值加一，其中 \(pre_r\) 表示 \(a_r\) 上一次出现的位置。
区间加和区间求和的操作考虑线段树维护，因为题意要求的是平方和，每次区间加对平方和的影响可以用完全平方公式拆解（byd代码里把式子写错了调了100年）
\[\begin{align}
( (a_1+v)^2+(a_2+v)^2+(a_3+v)^2+(a_4+v)^2) \newline
=(a_1^2+a_2^2+a_3^2+a_4^2)+2v(a_1+a_2+a_3+a_4)+4v^2\end{align} \]
所以总的操作就是枚举右端点，每次对 \([pre_r+1,r]\) 区间加 \(1\)，线段树里维护区间和，区间平方和，对于每个右端点都查询一次 \([1,r]\) 的平方和即可。
\(1e6\) 级别的 \(n\) 线段树容易被卡常，不过当然不包括 \(zkw\) 线段树
时间复杂度 \(O(n \log n)\)
点击查看代码
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int pre[N],tmp[N],a[N],lsh[N],tot;
int sum1[N<<2],sum2[N<<2],tag[N<<2],P=1,DEP;
int ans,n;
ili void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
ili void pa(int i,int len,int v){add(sum2[i],2*sum1[i]*v%mod+len*v*v%mod);add(sum1[i],len*v);tag[i]+=v;
}
ili void pushdown(int i,int siz){siz>>=1;if(tag[i]){pa(ls(i),siz,tag[i]);pa(rs(i),siz,tag[i]);tag[i]=0;}
}
ili void update(int l,int r){l+=P-1,r+=P+1;int siz=1;for(int i=DEP;i;i--) pushdown(l>>i,1<<i),pushdown(r>>i,1<<i);while(l^1^r){if(~l&1) pa(l^1,siz,1);if(r&1) pa(r^1,siz,1);l>>=1,r>>=1,siz<<=1;sum1[l]=(sum1[ls(l)]+sum1[rs(l)])%mod,sum2[l]=(sum2[ls(l)]+sum2[rs(l)])%mod;sum1[r]=(sum1[ls(r)]+sum1[rs(r)])%mod,sum2[r]=(sum2[ls(r)]+sum2[rs(r)])%mod;}for(l>>=1;l;l>>=1) sum1[l]=(sum1[ls(l)]+sum1[rs(l)])%mod,sum2[l]=(sum2[ls(l)]+sum2[rs(l)])%mod;
}
ili int query(int l,int r){l+=P-1,r+=P+1;int res=0;for(int i=DEP;i;i--) pushdown(l>>i,1<<i),pushdown(r>>i,1<<i);while(l^1^r){if(~l&1) add(res,sum2[l^1]);if(r&1) add(res,sum2[r^1]);l>>=1,r>>=1;}return res;
}
void xpigeon(){rd(n);for(int i=1;i<=n;i++){rd(a[i]);lsh[i]=a[i];}sort(lsh+1,lsh+1+n);tot=unique(lsh+1,lsh+n+1)-(lsh+1);for(int i=1;i<=n;i++){a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;pre[i]=tmp[a[i]];tmp[a[i]]=i;}while(P<=n+1) P<<=1,DEP++;for(int r=1;r<=n;r++){update(pre[r]+1,r);add(ans,query(1,n));}cout<<ans%mod<<'\n';
}