自动搬运

查看原文

来自洛谷，原作者为

	OMG_wc 幻想家协会会长

搬运于2025-08-24 22:21:09，当前版本为作者最后更新于2020-04-28 12:32:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $g(r)=\sum\limits_{l=1}^{r}f(l,r)^2$，那么本题要求的答案为 $\sum\limits_{r=1}^n g(r)$。

思路很简单的，循环枚举 $r$，然后用数据结构在 $O(\log n)$ 的时间内求出 $g(r)$ （当然得利用 $g(r-1)$ 的值），这样总时间复杂度为 $O(n \log n)$。

首先预处理一个last 数组：last[i] 表示上一个等于 $a_i$ 的位置，不存在就为 $0$。用map可能会卡常，建议离散化。

下面考虑 $r\Rightarrow r+1$ 的变化：

此时新增了一个数 $a_{r+1}$ ，在 $l\in[last_{r+1}+1,r+1]$ 的范围内的 $f(l,r+1)=f(l,r)+1$ ，因为这部分原本没有 $a_{r+1}$ 这个数，而其余部分是不变的，对 $g$ 也毫无影响。

那么 $g(r+1)-g(r)=\sum\limits_{l=last_{r+1}+1}^{r+1}f(l,r+1)^2-f(l,r)^2=\sum\limits_{l=last_{r+1}+1}^{r+1}(2f(l,r)+1)=2\sum\limits_{l=last_{r+1}+1}^{r+1}f(l,r)+r+1-last_{r+1}$

那么对于当前固定的 $r$，我们的数据结构需要能查询 $f(l,r)$ 的一段区间和，其中 $l\in[last_{r+1}+1,r+1]$ ，并且让这段区间加 $1$ 。

线段树容易在 $10^6$ 范围内卡常，用两个树状数组就能解决区间求和、区间查询的问题，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 1000005;
LL c1[N], c2[N];
LL sum(int x) {
    LL res = 0;
    for (int i = x; i > 0; i -= i & -i) {
        res += c1[i] * (x + 1) - c2[i];
    }
    return res;
}
void add(int x, int d, int n) {
    for (int i = x; i <= n; i += i & -i) {
        c1[i] += d;
        c2[i] += (LL)d * x;
    }
}
int a[N], b[N], d[N], last[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i - 1] = a[i];
    }
    sort(b, b + n);
    int m = unique(b, b + n) - b;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b, b + m, a[i]) - b;
        last[i] = d[a[i]];
        d[a[i]] = i;
    }
    LL ans = 0, now = 0;
    for (int i = 1; i <= n; i++) {
        now += i - last[i] + 2 * (sum(i) - sum(last[i]));
        now %= mod;
        ans += now;
        add(last[i] + 1, 1, n);
        add(i + 1, -1, n);
    }
    printf("%lld\n", ans % mod);
    return 0;
}