P10589 楼兰图腾（树状数组）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 200010;
template <class T>
struct BIT
{
	T c[N];
	int sz;
	void init(int s)
	{
		sz = s;
		for(int i=1;i<=sz;++i) c[i] = 0;
	}
	T lowbit(int x)
	{
		return x&-x;
	}
	T sum(int x) 
	{
		assert(x <= sz);
		T res=0;
		while(x) res+=c[x],x-=lowbit(x);
		return res;
	}
    T query(int L, int R)
    {
        return sum(R) - sum(L-1);
    }
	void update(int x,int y) 
	{
		assert(x != 0);
		while(x<=sz) c[x]+=y,x+=lowbit(x);
	}
};
//正向反向各扫一遍
BIT<int> zheng,fan;
int zheng_up[N],zheng_down[N],fan_up[N],fan_down[N];
void solve()
{
    ll res_up = 0, res_down = 0;
    int n;
    cin>>n;
    zheng.init(n);fan.init(n);
    vector<int> a(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    
    for(int i=1;i<=n;++i)
    {
        zheng.update(a[i],1);
        zheng_up[i] = zheng.query(a[i]+1,n);
        zheng_down[i] = zheng.query(1,a[i]-1);
    }
    for(int i=n;i;--i)
    {
        fan.update(a[i],1);
        fan_up[i] = fan.query(a[i]+1,n);
        fan_down[i] = fan.query(1,a[i]-1);
    }
    for(int i=2;i<n;++i)
    {
        res_up += (ll)zheng_up[i]*fan_up[i];
        res_down += (ll)zheng_down[i]*fan_down[i];
    }
    cout<<res_up<<' '<<res_down<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}