题目
解法
考虑使用增量法求解。假设从 (r-1 ightarrow r)，上一个和 (A_r) 相同的数下标为 (lst_i)。那么对于 (lin (lst_i,r)) 的 (f(l,r)) 都增加了 (1)。那么对于 (lin (lst_i,r)) 有：
[Delta_l=f^2(l,r)-f^2(l,r-1)
]
[=(f(l,r-1)+1)^2-f^2(l,r-1)
]
[=2f(l,r-1)+1
]
至此，我们只需要维护 (f(i,r)) 的区间加和区间求和即可（其中 (r) 使我们枚举的量）。
可以用树状数组维护。区间修改首先让我们想到差分，不妨令 (a_i) 为维护的值，(c_i=a_i-a_{i-1})。那么：
[sum_{i=1}^na_i=sum_{i=1}^n sum_{j=1}^i c_j
]
[=sum_{i=1}^n (n-i+1)cdot c_i
]
[=left( ncdot sum_{i=1}^n c_i
ight)-sum_{i=1}^n(i-1)cdot c_i
]
于是开两个树状数组 (C_1,C_2)，分别维护 (c_i) 的前缀和，((i-1)cdot c_i) 的前缀和即可。
代码
相信自己！