tyvj 1432 楼兰图腾

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+10;
int T,n,m,k;
int a[maxn];
int sum[maxn<<2];

void PushUp(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void Update(int rt,int l,int r,int pos){
    if(l==r){
        sum[rt]++;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) Update(lson,pos);
    else Update(rson,pos);
    PushUp(rt);
}

ll Query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[rt];
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=Query(lson,L,R);
    if(R>mid) ans+=Query(rson,L,R);
    return ans;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(sum,0,sizeof(sum));
        ll ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            ll tmp1=Query(1,1,n,1,a[i]);
            ll tmp2=Query(1,1,n,a[i],n);
            ans1+=tmp2*(n-a[i]-tmp2);
            ans2+=tmp1*(a[i]-1-tmp1);
            Update(1,1,n,a[i]);
        }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}