Submission #52903977

---

Source Code Expand

// LUOGU_RID: 157309667
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 4e5 + 10;
int n;
struct BIT
{
    int c[maxn];
    int lowbit(int x){return x & (-x);}
    void update(int u,int val){while(u <= n){c[u] += val;u += lowbit(u);}}
    int query(int u){int ans = 0;while(u > 0){ans += c[u],u -= lowbit(u);}return ans;}
}sum,cnt;
pair<int,int> a[maxn];

signed main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1,a + n + 1);
    int ans = 0;
    for(int i = 1;i <= n;i++)
    {
        ans += cnt.query(a[i].second) * a[i].first - sum.query(a[i].second);
        cnt.update(a[i].second,1);
        sum.update(a[i].second,a[i].first);
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result