题解 P6477 【[NOI Online #2 提高组]子序列问题（民间数据）】

· · 题解

设 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;
}