题解 | #小S按按钮#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using ld = long double;
const int N = 1e6+ 10;
int mod = 1e9 + 7;
ll n,m;
ll a[N];
int tree[N];
void add(int x, int val) {
    for(int i = x; i <= 1e6; i += (i & (-i))) tree[i] += val;
}
int query(int x) {
    int ret = 0;
    if(!x) return 0;
    for(int i = x; i; i -= (i & (-i))) ret += tree[i];
    return ret;
}
void solve()
{
    cin >> n;
    vector<ll> index(N, 0);
    vector<ll> pre(n+5, 0);
    vector<int> mx(n+5, 0);
    vector<ll> g[N];
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        add(a[i], 1);
        g[a[i]].push_back(i);
        if(index[a[i]] == 0) {
            index[a[i]] = i;
            mx[i] = i - query(a[i]);
            continue;
        }
        mx[i] = i - query(a[i]);
        int ret = query(a[i]);
        pre[i] = (i - ret) - mx[index[a[i]]];
        index[a[i]] = i;
    }
    ll sum = 0;
    for(int i = 1; i <= 1e6; i++) {
        if(g[i].size() <= 1) continue;
        ll ans = 0;
        m = g[i].size();
        for(int j = 1; j < g[i].size(); j++) {
            ans += pre[g[i][j]] * (ll)j * (m - j);
        }
        vector<int> tem;
        for(int j = 0; j < g[i].size(); j++) tem.push_back(g[i][j] % 2);
        vector<ll> p(m+5), l(m+5);
        for(int j = 1; j <= m; j++) {
            p[j] = p[j - 1] + (tem[j - 1] == 0);
            l[j] = l[j - 1] + (tem[j - 1] == 1);
        }
        for(int j = 2; j <= m; j++) {
            ll pp = (ll)p[j-1] * (l[m] - l[j-1]);
            ans += pre[g[i][j-1]] * pp;
            pp = (ll)l[j-1] * (p[m] - p[j-1]);
            ans += pre[g[i][j-1]] * pp;
        }
        sum += ans;
    }
    cout << sum;
}
int main()
{
  // 请在此输入您的代码
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
//     cin >> _;
    while(_--) solve();
}