思路 1. 转化贡献 假设一个子数组中出现的元素集合为 \{a,b,c,d...\}，那么这个集合产生的贡献在数值上相当于集合中所有的元素二元组个数，即 (a,a),(a,b),\dots,(d,c),(d,d) 在这个集合中各产生 1 贡献。 也就是说统计「所有子数组的不同元素个数平方和」在数值上相当于统计「每个子数组包含多少个元素二元组 (x,y) 」，即统计「每个元素二元组 (x,y) 被多少个子数组 a_{l...r} 包含」。 2. 计算每个右端点的贡献 假设我们固定了右端点 r，其中包含元素二元组…