提出 #71688193

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int a[maxn];
class BIT //树状数组
{
public:
    long long tr[maxn];
    int n;
    void init(int x) //清空并初始化
    {
        for (int i = 1; i <= x; i++)
            tr[i] = 0;
        n = x;
    }

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int x, long long d) //将第x个数+k
    {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += d;
    }

    long long sum(int x) //求前x个数的和
    {
        long long ans = 0;
        for (int i = x; i; i -= lowbit(i))
            ans += tr[i];
        return ans;
    }
} tr;
int loc[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        loc[a[i]]=i;
    }
    tr.n=n;
    long long ans=0;
    for (int i=1;i<=n;i++)
    {
        long long l=tr.sum(loc[i]);
        long long r=i-l;
        l++;
        ans+=l*r;
        tr.add(loc[i],1);
    }
    cout<<ans;
}

提出情報

ジャッジ結果