T2
题意:给一个长度为$n$的序列$A$.定义$f(l,r)$为$A[l,r]$中不同的数字个数.求
$$
(\sum_{i=1}^n\sum_{j=i}^nf(l,r)^2 )mod\ 10^9+7
$$
$n\le 10^6$,$1\le A_i\le 10^9$
暴力:先离散化,然后枚举两个端点统计即可.时间复杂度$\mathcal O(n^2)$
考虑优化:(这里记$i$为右端点,$j$为左端点)
考虑加入$i$后的贡献,即$f(j,i)-f(j,i-1)$.求出$last(A_i)$表示$A_i$上一次出现的位置(未出现过则为0)
- 对于$j\le last(A_i),f(j,i)=f(j,i-1)$
- 否则$f(j,i)=f(j,i-1)+1$
然后$\sum_{j=1}^i f(j,i)^2$就是$i$对答案的贡献了.这个东西显然就是区间加,区间平方和.这个东西线段树好像不能直接做.考虑$f(j,i-1)^2$到$f(j,i)^2$的变化(对于$j>last(A_i)$)
$$
f(j,i-1)^2-f(j,i)^2=(f(j,i)+1)^2-f(j,i)^2\\
=2f(j,i)+1
$$
所以只需要区间加,区间和就行了.线段树即可维护.时间复杂度$\mathcal O(n\log n)$ (据说有点卡常,但我觉得常数正常的线段树都能过啊....)
