前言

打完杭电多校看有人说有原题，就跑过来看看。

Solution

据说这个题有 O(n) 的做法，但是我不会，赛场上想了个 O(n\log n) 的解法，常数比较小勉强可以过。

由于值域比较小，考虑对每个不同的值统计合法的区间个数；又因为是统计区间个数，最直接的想法就是枚举端点，但是这样复杂度就炸掉了。

考虑对每个值 x 求众数为 x 时的区间个数，设 cnt_i 为 [1,i] 中 x 的个数，那么区间 (L,R] 的众数是 x 的充要条件是

\dfrac{cnt_R-cnt_L}{R-L}>\dfrac{1}{2}

将式子稍作变换可得

2cnt_R-R>2cnt_L-L

发现左右两边形式相同，设 b_i=2cnt_i-i ，则有

ans_R=\sum\limits_{i=0}^{R-1}[b[i]<b[R]]

这个东西也可以写成二维偏序，就是

L<R,b[L]<b[R]

那么有一个显然的想法是枚举右端点，用树状数组求二维偏序。
接下来就要解决枚举复杂度过高的问题。
注意到所有值的总数量是 n 个，那么能不能在枚举的时候只枚举值为 x 的位置呢？
考虑一下 b 数组长什么样子，比如 [0, 1, 0, 0, 0, 1, 1, 0 ,0, 0, ...] 就是

-1,0,-1,-2,-3,-2,-1,-2,-3,-4,...

这样的以每个值为 x 的位置为开头的若干个等差数列，那么这就是非常好的性质了，我们接着来考虑怎么用这个等差数列。
单独考虑一段，在枚举右端点的过程中， b[R] 是单调减的，所以只有这一段之前的 L 才会对 R 产生贡献，然后这一段的 b 值是一个连续区间，而且每次查询的位置也构成一个连续区间，那么整理一下，我们需要维护两个操作：

• 求出这一段之前的 L 对这一段中每个 R 的总贡献，可以看成连续位置的前缀和之和
• 在表示b数组的某个区间内每个位置都+1，表示为这个值的L个数

于是考虑在值域上建树状数组，显然值域是[-n, n]，由于有负数，我们将其+n+1变成[1, 2n + 1]的值域。
然后就是要用树状数组维护求区间三次前缀和、区间加的操作，区间加很简单，直接维护差分数组 d[] ，区间三次前缀和形式化表示就是维护

\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j}d[k]

这里就顺便写一下树状数组维护高次前缀和的通法，我们将这个式子进行一些运算

\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j}d[k]=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j+1)d[j]

实际上这一步只是将后面两个 \sum 展开写，将 d[j] 的系数加起来，得到的就是这个结果，再进行类似的变换就可以得到

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j+1)d[j]=\dfrac{1}{2}\sum\limits_{i=1}^{n}((n^2+3n+2)d[i]-(2n+3)i\cdot d[i]+i^2\cdot d[i])

那么对于 d[i],i\cdot d[i],i^2\cdot d[i] ，其前面的系数是相同的，所以我们考虑用维护 d[i],i\cdot d[i],i^2\cdot d[i] 的值，最后直接按照上面的式子去算就行了，相当于结果就是

\dfrac{1}{2}((n^2+3n+2)\sum\limits_{i=1}^nd[i]-(2n+3)\sum\limits_{i=1}^{n}i\cdot d[i]+\sum\limits_{i=1}^ni^2\cdot d[i])

所以分开维护就好了。
那么写到这里解法就很清楚了，我们直接枚举值为 x 的位置，然后处理从上一个位置到 x 之前的贡献，并将这一段计入树状数组。
由于枚举的位置总数是 O(n) 的，所以总复杂度是 O(n\log n) ，树状数组常数比较小，所以跑得也很快。

ll c0[N], c1[N], c2[N];
int a[N], top;
pair<int, int>st[N];
vector<int>loc[N >> 1];
void update(ll x, int n, ll data) {
    ll i = x * data, ii = x * x * data;
    while (x <= n) {
        c0[x] += data;
        c1[x] += i;
        c2[x] += ii;
        x += lowbit(x);
    }
}
ll query(ll x) {
    ll ans = 0, k1 = x * x + 3 * x + 2, k2 = 2 * x + 3;
    while (x) {
        ans += k1 * c0[x] - k2 * c1[x] + c2[x];
        x -= lowbit(x);
    }
    return ans >> 1;
}

int main() {
    int n = fast_IO::read(), m = 0; fast_IO::read();
    for (int i = 1; i <= n; ++i)loc[a[i] = fast_IO::read()].push_back(i), m = max(m, a[i]);
    ll ans = 0;
    for (int i = 0; i <= m; ++i) {
        if (loc[i].empty())continue;
        int now = n + 1, pre = 0;
        loc[i].push_back(n + 1);
        for (auto j : loc[i]) {
            ll del = query(now - 1) - query(now - (j - pre) - 1);
            ans += del;
            update(now - (j - pre) + 1, (n << 1) | 1, 1);
            update(now + 1, (n << 1) | 1, -1);
            st[++top] = make_pair(now - (j - pre) + 1, -1);
            st[++top] = make_pair(now + 1, 1);
            now = now - (j - pre) + 2;
            pre = j;
        }
        //清空一下树状数组
        while (top) {
            update(st[top].first, (n << 1) | 1, st[top].second);
            --top;
        }
    }
    printf("%lld\n", ans);
    return 0;
}