Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/NOIolsequence/

前言

由于 NOI Online 还未评测，民间数据尚未出炉，因此本题解可能有错误……
待测评后若有误可能会撤下/修改。
当然笔者是不想有误的

Update:
在修改了没开 long long，数组开小、到处忘记取模的问题之后，吸了氧通过了洛谷民间数据……
也就是说交上去要暴毙了，只能获得暴力分
代码不修改了，注意把 maxn 开大，#define int long long 即可。
最后笔者还是没查出来哪里溢出了QAQ

题意

题目原文：

定义 $f(l,r)$ 为 $[l,r]$ 内不同的整数个数。
求 $\sum _{l=1} ^n \sum _{r=l}^n (f(l,r))^2$，即每段子区间的 $f(l,r)^2$ 和。

解法

考虑先维护 $f(1,i),i\in[1,n]$，随后不断右移左端点，维护并统计答案。

确定左端点后，开一个 set 一路扫过去即可统计 $f(l,r)$。

记 $sum[i] = f(1,i)$

for(int i = 1;i<=n;++i)
{
    read(a[i]);
    s.insert(a[i]);
    ans = (ans + (sum[i] = s.size())) % mod;
}

考虑左端点移动会对 $sum$ 产生什么影响。

例如：

移动前：[1 2 3 1 2]移动后：1 [2 3 1 2]

$sum$ 数组变化：
移动前：[1 2 3 3 3]移动后: x [1 2 3 3]

从左端点开始，到移动前左端点所在处的数下次出现的位置的 $sum$ 值都减少了 $1$。

记 $next_i$ 为位置为 $i$ 的数后第一个与其相等的数的位置。
设当前左端点为 $l$，那么上述规律可以总结为：

$[l + 1,next_l – 1]$ 区间内的 $sum$ 减少了 $1$。

这样转移后，$sum_i = f(l + 1,i)$。

预处理出 $next$，用线段树来进行区间操作。
统计答案时，使用线段树维护平方和的技巧。

预处理使用 map，复杂度 $O(n \log n)$。
每次移动左端点复杂度 $O(\log n)$。
总复杂度 $O(n \log n)$。

常数过大可能被1e6的数据卡死？

代码

使用线段树维护 $sum$ 数组。
统计答案的方差和 $qsum$ 数组。

#include <cstdio>
#include <map>
const int bufSize = 1e6;
inline char nc()
{
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
void read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); c > '9' || c < '0'; c = nc());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = nc());
}
const int maxn = 1e6;
const int mod = 1e9 + 7;
int n;
long long a[maxn];
std::map<long long, int> last;
int next[maxn];
long long sum[maxn << 2], tag[maxn << 2], qsum[maxn << 2];
inline void push_up(const int &p)
{
    qsum[p] = qsum[p << 1] + qsum[p << 1 | 1];
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
inline void push_down(const int &l, const int &r, const int &p)
{
    if (!tag[p])
        return;
    int mid = l + r >> 1;
    tag[p << 1] = (tag[p << 1] + tag[p]) % mod;
    tag[p << 1 | 1] = (tag[p << 1 | 1] + tag[p]) % mod;
    qsum[p << 1] = (qsum[p << 1] + (long long)tag[p] * tag[p] * (mid - l + 1)) % mod;
    qsum[p << 1] = (qsum[p << 1] + tag[p] * 2 * sum[p << 1]) % mod;
    qsum[p << 1 | 1] = (qsum[p << 1 | 1] + tag[p] * tag[p] * (r - mid)) % mod;
    qsum[p << 1 | 1] = (qsum[p << 1 | 1] + tag[p] * 2 * sum[p << 1 | 1]) % mod;
    sum[p << 1] = (sum[p << 1] + (mid - l + 1) * tag[p]) % mod;
    sum[p << 1 | 1] = (sum[p << 1 | 1] + (r - mid) * tag[p]) % mod;
    tag[p] = 0;
}
void modify(const int &l, const int &r, const int &p, const int &ll, const int &rr, const int &k)
{
    if (ll <= l && rr >= r)
    {
        qsum[p] += k * k * (r - l + 1);
        qsum[p] += k * 2 * sum[p];
        sum[p] += (r - l + 1) * k;
        tag[p] += k;
        return;
    }
    push_down(l, r, p);
    int mid = l + r >> 1;
    if (ll <= mid)
        modify(l, mid, p << 1, ll, rr, k);
    if (rr > mid)
        modify(mid + 1, r, p << 1 | 1, ll, rr, k);
    push_up(p);
}
long long ask(const int &l, const int &r, const int &p, const int &ll, const int &rr)
{
    if (ll <= l && rr >= r)
        return qsum[p];
    push_down(l, r, p);
    int mid = l + r >> 1;
    long long ans = 0;
    if (ll <= mid)
        ans += ask(l, mid, p << 1, ll, rr);
    if (rr > mid)
        ans += ask(mid + 1, r, p << 1 | 1, ll, rr);
    return ans;
}
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int siz = last.size();
        int t = last[a[i]];
        if (t == 0)//当前数未出现过
            siz++;
        modify(1, n, 1, i, i, siz);
        ans = (ans + siz * siz) % mod;
        if (t)
            next[t] = i;
        last[a[i]] = i;
    }
    for (int i = 1; i < n; ++i)
    {
        //弹出I
        if (next[i])
        {
            modify(1, n, 1, i + 1, next[i] - 1, -1);
            ans = (ans + ask(1, n, 1, i + 1, n)) % mod;
        }
        else
        {
            modify(1, n, 1, i + 1, n, -1);
            ans = (ans + ask(1, n, 1, i + 1, n)) % mod;
        }
    }
    printf("%lld", (ans + mod) % mod);
    return 0;
}