题目描述

给定一个长度为 $n$ 的正整数序列 $A _ 1, A _ 2, \cdots, A _ n$。

定义一个函数 $f(l, r)$ 表示：序列中下标在 $[l, r]$ 范围内的子区间中，不同的整数个数。

换句话说，$f(l,r)$ 就是集合 $A_l, A _ {l + 1}, \cdots, A _ r$ 的大小。

这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出 $\sum ^ n _ {l = 1} \sum ^ n _ {r = l} (f(l, r)) ^ 2$。

由于答案可能很大，请输出答案对 $10 ^ 9 + 7$ 取模的结果。

输入格式

第一行一个正整数 $n$，表示序列的长度。

第二行 $n$ 个正整数，相邻两个正整数用空格隔开，表示序列 $A _ 1, A _ 2, \cdots, A _ n$。

输出格式

仅一行一个非负整数，表示答案对 $10 ^ 9 + 7$ 取模的结果。

数据范围

$1 \leq n \leq 10 ^ 6$，集合中每个数的范围是 $[1, 10 ^ 9]$

样例

输入样例1：
4
2 1 3 2

输出样例1：
43

输入样例2：
3
1 1 1

输出样例2：
6

时隔不知道多长时间，这题窝终于会写了，于是决定来水篇题解

算法1

(暴力) $\mathcal O(n ^ 2)$

暴力嘛，照着题目模拟一遍就好啦~
题目中用了俩求和嵌套，那代码中用两个循环嵌套就好啦~
第一重循环枚举区间左端点 $l$，第二重循环枚举区间右端点 $r$
当然也不能太暴力，离散化一下~
时间复杂度 $\mathcal O(n ^ 2)$

算法

(树状数组) $\mathcal O(n \log n)$

先看一下上面的暴力算法过程。
求和嵌套太抽象了，先把外面的求和去掉，只看里面的求和。
$\sum ^ n _ {r = l} (f(l, r)) ^ 2$

一般不要用 $\sum$，不容易懂，最好写开，不要怕麻烦——yxc

yxc：我有说过这句话吗？？？

$f(l, l) ^ 2 + f(l, l + 1) ^ 2 + \cdots + f(l, n - 1) ^ 2 + f(l, n) ^ 2$

设值其为 $S[l]$
直接算肯定是不行的，所以窝萌康下 $S[l-1]$ 是个啥东东，能不能转移过来
根据定义：$S[l - 1] = f(l - 1, l - 1) ^ 2 + f(l - 1, l) ^ 2 + \cdots + f(l - 1, n - 1) ^ 2 + f(l - 1, n) ^ 2$
然后康一下 $f$ 的定义：

序列中下标在 $[l, r]$ 范围内的子区间中，不同的整数个数。
$f(l, r)$ 是集合 $A_l, A _ {l + 1}, \cdots, A _ r$ 的大小。

不难发现，$S[l]$ 和 $S[l - 1]$ 的区别就是 $S[l]$ 中的每个 $f(l, i)$ 的值都没有包括 $A _ {l - 1}$
所以只要计算 $A_{l-1}$ 对哪些 $f$ 有影响就可以啦

先预处理出一个 $last[A _ i]$ 表示 $A _ i$ 上一次出现的位置，若未出现则为 $0$。
计算时分两种情况：

• 若 $l <= last[A _ i]$，则说明当前区间中 $A _ i$ 已经出现过了。根据定义，不将其计入。所以 $f(l, r) = f(l, r - 1)$
• 否则说明当前区间中 $A _ i$ 第一次出现，所以 $f(l, r) = f(l, r - 1) + 1$

那么如何快速对 $f(l, r) ^ 2$ 求和呢？
对于上面第一种情况，直接加就好了，不用算。
那就康一下第二种情况里的 $f(l, r - 1) ^ 2$ 是个啥
$f(l, r - 1) ^ 2 = (f(l, r) + 1) ^ 2 = f(l, r) ^ 2 + 2f(l, r) + 1$
那总的贡献呢
$f(l, r - 1) ^ 2 - f(l, r) ^ 2 = 2 \times f(l, r) + 1$
所以只要区间加，区间求和就好啦~

线段树是可以做的，但是要写懒标记……
可窝懒，懒得写懒标记……

树状数组做就好啦~
可为啥其它题解都是用的线段树嘞？瞧不起我树状数组？

树状数组算是数据结构中的一股清流，好写，好调——yxc

树状数组例题

顺便说下思路吧 （秒杀例题的大佬请果断跳过）
假设要操作的序列为 $A _ 1, A _ 2, \cdots, A _ n$

首先树状数组可以做单点修改区间查询

那么树状数组+差分呢？
令 $B _ i = A _ i - A _ {i - 1}$
用树状数组对 $B$ 做单点修改区间查询
等价于是对 $A$ 做区间修改单点查询
要在 $A$ 的区间 $[l, r]$ 加上 $c$，可以在 $B _ l$ 加上 $c$，再在 $B _ {r + 1}$ 减去 $c$。
求 $A _ i$，可以转化为求 $B _ 1 + B _ 2 + \cdots + B _ i$。

那如果硬要区间修改区间查询呢？
首先把原数组转化为差分数组
$B _ i = A _ i - A _ {i - 1}$
区间修改就已经做到了，问题是区间查询。
要求区间 $[l, r]$ 的和，只要求出 $[1, r]$ 的和，再减去 $[1, l - 1]$ 的和即可
那么如何求出 $[1, i]$ 的和呢？
由于已经将原数组 $A$ 转化为差分数组 $B$，所以要求 $A$ 中 $[1, i]$ 的和，就要先看一下 $A$ 跟 $B$ 的关系
$A _ 1 = B _ 1$
$A _ 2 = B _ 1 + B _ 2$
$\cdots$
$A _ i = B _ 1 + B _ 2 + \cdots + B _ {i - 1} + B _ i$
将等式两边累加起来，
$A _ 1 + A _ 2 + \cdots + A _ i = i \times B _ 1 + (i - 1) \times B _ 2 + \cdots + 2 \times B _ {i - 1} + B _ i$
由于窝萌已经可以求出 $B _ 1 + B _ 2 + \cdots + B _ i$ 了，所以要把右边转化成一个和 $B _ 1 + B _ 2 + \cdots + B _ i$ 有关的式子
$i \times B _ 1 + (i - 1) \times B _ 2 + \cdots + 2 \times B _ {i - 1} + B _ i$
$= [(i + 1)B _ 1 - B _ 1] + [(i + 1)B _ 2 - 2 \times B _ 2] + \cdots + [(i + 1)B _ i - i \times B _ i]$
$= (i + 1)(B _ 1 + B _ 2 + \cdots + B _ n) - (B _ 1 + 2 \times B _ 2 + \cdots + (i - 1) \times B _ {i - 1} + i \times B _ i)$
左边这一坨，可以用$\mathcal O(\log n)$ 的时间复杂度求出，那右边这坨咋办嘞？
可以维护另一个树状数组，存 $i \times B _ i$。
这样，两边就都能用 $\mathcal O(\log n)$ 的时间求出来了。
也就完成了区间修改区间查询。

C++ 代码

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1000005, mod = 1e9 + 7;

int n;
int a[N], last[N];// a 存输入数据，last 见描述。
int alls[N], len;// alls 存离散化后的数组，len 存 alls 的长度。
int ans, sum;// ans 存答案，sum 存 S[i]，S[i] 见描述。
// 由于不需要记录所有的 S[i]，可以直接边求边算，所以只存一个值就可以了。
ll tr[N], tre[N];// tr 为 B 的树状数组，tre 为 Bi * i 的树状数组。

// 将 l ~ r 这段区间中每个数都 + 1
void add(int l, int r)
{
    for (int i = l; i <= n; i += i & -i) tr[i] ++ , tre[i] += l;
    for (int i = r; i <= n; i += i & -i) tr[i] -- , tre[i] -= r;
}

// 询问区间 (l, r] 所有数的和
ll query(int l, int r)
{
    ll res = 0;
    for (int i = r; i; i &= i - 1) res += tr[i] * (r + 1) - tre[i];
    for (int i = l; i; i &= i - 1) res -= tr[i] * (l + 1) - tre[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", a + i), alls[i] = a[i];
    sort(alls, alls + n);        // 离散化
    len = unique(alls, alls + n) - alls;
    for (int i = 0; i < n; i ++ ) a[i] = lower_bound(alls, alls + len, a[i]) - alls;
    for (int i = 1; i <= n; i ++ )
    {
        int &v = last[a[i - 1]]; // last 边做边求
        sum = (sum + (query(v, i)) * 2 + i - v) % mod; // S[i] 也边做边求
        ans = (ans + sum) % mod;
        add(v + 1, i + 1);
        v = i;
    }
    printf("%lld", ans);
    return 0;
}
// 不压行加注释共 50 行，树状数组是真的比线段树好写。。为啥没人用嘞。。