这篇题解的做法

过了#1,2,3,5,10,11,14,15,17,20

似乎有一些数据点输出了负数，但是感觉并不是什么溢出的锅

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define fi first
#define se second
const int N = 5e5 + 10, B = 710, T = N - 10 + 1;
int n, vis[N], cnt[N], a[N], s[N * 3], tot[N];
vector<int>vec;
ll solve(int x) {
    //2*cnt[i]-i
    ll ret = 0;
    //求顺序对个数。
    ll sum = 0;
    int nw = 0;
    s[0 + T] = 1; 
    for(int i = 1; i <= n; i++) {
        if(a[i] == x) sum += s[nw + T], nw++;
        else sum -= s[nw - 1 + T], nw--;
        ret += sum; s[nw + T]++;
    }
    nw = 0;
    for(int i = 1; i <= n; i++) {
        if(a[i] == x) nw++; else nw--,
        s[nw + T]--;
    }
    s[0 + T] = 0;
    //cout<<"ret: "<<ret<<endl;
    return ret;
}
int main(){
    int tp;
    scanf("%d%d", &n, &tp);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]), cnt[a[i]]++;
        if(!vis[a[i]]) vis[a[i]] = 1, vec.push_back(a[i]);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        int mx = 0;
        for(int j = i; j <= min(n, i + 2 * B); j++) {
            tot[a[j]]++;
            if(tot[a[j]] > tot[mx]) mx = a[j];
            if(tot[mx] > (j - i + 1) / 2 && cnt[mx] < B) ans++;
        }
        for(int j = i; j <= min(n, i + 2 * B); j++)
            tot[a[j]]--;
    }
    //cout<<ans<<endl;
    for(int i = 0; i < vec.size(); i++) {
        int x = vec[i]; if(cnt[x] < B) continue;
        ans += solve(x);
    }
    printf("%lld\n", ans);
    return 0;
}