树状数组

原题链接：https://www.luogu.com.cn/problem/P8613

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>

#define ll long long


const ll N = 1e7;

ll n;

ll op[N],pz[N];
ll pr[N];
ll dp[N];

ll lowbit(ll a){
    return a & (-a);
}

void add(ll a,ll b){
    for(ll i = a; i <= n * 2; i += lowbit(i)) pr[i] += b;
}

ll check(ll a){
    ll res = 0;
    for(ll i = a; i; i -= lowbit(i)) res += pr[i];
    return res;
}

void solve(){
    std::cin >> n;
    for(ll i = 1; i <= n; i ++) std::cin >> op[i],pz[i] = op[i];
    std::sort(pz + 1,pz + 1 + n);
    std::map<ll,ll> oo;
    for(ll i = 1; i <= n; i ++){
        oo[pz[i]] = i;
    }
    for(ll i = 1; i <= n; i ++){
        op[i] = oo[op[i]];
//      std::cout << op[i] << " ";
    }
    for(ll i = 1; i <= n; i ++){
        add(op[i] + 1,1);
        dp[i] += (i - check(op[i] + 1));
    }
    std::memset(pr,0,sizeof pr);
    for(ll i = n; i >= 1; i --){
        add(op[i] + 1,1);
        dp[i] += (check(op[i]));
    }
    ll res = 0;
    for(ll i = 1; i <= n; i ++){
        res += (dp[i] * (dp[i] + 1) / 2);
    }
    std::cout << res;
    std::cout << "\n";
}

int main(){
    ll t = 1;
//  std::cin >> t;
    while(t --)
    solve();
    return 0;
}