权值线段树 - AcWing241 - 楼兰图腾

题目不难,用权值线段树维护逆序对.
用树状数组也可解.常数更小

#include 
#include 
using namespace std;
#define MAX(a,b) (a>b?a:b)
typedef long long ll;
const int N = 200000+5;
int tree[N<<2];

void add(int l,int r,int rt,int p){
    tree[rt] += 1;
    int mid = l+r>>1;
    if(l==r){
        return;
    }
    if(p <= mid){
        add(l,mid,rt<<1,p);
    }else{
        add(mid+1,r,rt<<1|1,p);
    }
}

int query_less(int l,int r,int rt,int p){ // 查询区间内有多少个比p小的
    if(p <= l){
        return 0;
    }else if(p > r){
        return tree[rt];
    }else{
        int ans = 0;
        int mid = l+r>>1;
        ans += query_less(l,mid,rt<<1,p);
        if(p > mid+1){
            ans += query_less(mid+1,r,rt<<1|1,p);
        }
        return ans;
    }
}
int left_less[N];
int main(){
    int n,temp;
    ll up = 0,down = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&temp);
        add(1,n,1,temp);
        ll left_less = query_less(1,n,1,temp); // 左侧有多少个比其小的
        up += (ll)left_less * (ll)(temp-1-left_less);
        down += (ll)(i-1-left_less)*(ll)(n-temp-i+1+left_less); 
    }
    printf("%lld %lld",down,up);

    return 0;
}

原文：https://www.cnblogs.com/popodynasty/p/13961744.html