Submission #52862647

---

Source Code Expand

// #pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define lll __int128
struct BIT {
    ll n;
    vl tree;
    void init(ll n) { //初始化
        this->n = n;
        this->tree = vl(n + 1);
    }
    ll lowbit(ll x) {
        return x & (-x);
    }
    void upd(ll x, ll d) { //单修
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }
    ll query(ll x) { //查[1,x]
        ll ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
    ll query(ll l, ll r) { //查[l,r]
        if (l > r)
            return 0;
        return query(r) - query(l - 1);
    }
} bt, bt2;
const int N = 1e6 + 5;
ll n, a[N];
void solve() {
    cin >> n;
    set<ll> s;
    for (ll i = 1; i <= n; i++)
        cin >> a[i], s.insert(a[i]);
    map<ll, ll> mp;
    ll id = 0;
    for (ll x : s)
        mp[x] = ++id;
    bt.init(id), bt2.init(id);
    for (ll i = 1; i <= n; i++) {
        ll j = mp[a[i]];
        bt.upd(j, a[i]), bt2.upd(j, 1);
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll j = mp[a[i]];
        ll c = bt2.query(mp[a[i]] + 1, id);
        ans += bt.query(mp[a[i]] + 1, id) - c * a[i];
        bt.upd(j, -a[i]), bt2.upd(j, -1);
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Submission Info

Judge Result