题解：P10589 楼兰图腾

· · 题解

本题解使用的是权值线段树，不过思路和权值树状数组是一样的。大概就是维护比 a_i 大（小）的数的数量，再使用乘法原理计算即可。

具体参见代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int n;
int a[N],tmp[N],top;
int val[N << 2];//权值线段树
int l_val1[N],l_val2[N];
long long ans1,ans2; 
void update(int root,int l,int r,int v){//将v所在的节点加1
    val[root]++;//经过的节点肯定会加1 
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    int lchild = root << 1,rchild = lchild + 1;
    if(v <= mid)
        update(lchild,l,mid,v);
    else
        update(rchild,mid + 1,r,v);
}
int query(int root,int l,int r,int v){//查询当前序列有多少个不超过v的数
    if(!val[root])
        return 0;
    if(l == r)
        return val[root];
    int mid = (l + r) >> 1;
    int lchild = root << 1,rchild = lchild + 1;
    int ret = 0;
    if(v <= mid)
        ret = query(lchild,l,mid,v);
    else
        ret = val[lchild] + query(rchild,mid + 1,r,v);
    return ret;
}
int main(){
    scanf("%d", &n);
    tmp[++top] = 0;
    for(int i = 1;i <= n;i++){
        scanf("%d", &a[i]);
        tmp[++top] = a[i];
    }
    //离散化 
    sort(tmp + 1,tmp + top + 1);
    top = unique(tmp + 1,tmp + top + 1) - (tmp + 1);;
    for(int i = 1;i <= n;i++)
        a[i] = lower_bound(tmp + 1,tmp + top + 1,a[i]) - tmp;
    for(int i = 1;i <= n;i++){
        update(1,1,top,a[i]);//将a[i]在计数器上加1（在权值线段树上更新） 
        l_val1[i] = query(1,1,top,a[i] - 1);
        l_val2[i] = i - query(1,1,top,a[i]);
    }
    memset(val,0,sizeof val);
    for(int i = n;i >= 1;i--){
        update(1,1,top,a[i]);//将a[i]在计数器上加1（在权值线段树上更新） 
        int r_val1 = ((n - i + 1) - query(1,1,top,a[i]));
        int r_val2 =  query(1,1,top,a[i] - 1);
        ans1 += 1ll * r_val1 * l_val2[i];
        ans2 += 1ll * r_val2 * l_val1[i];
//      printf("在a[%d]左侧有%d个数比a[%d]小，有%d个数比a[%d]大\n",i,l_val1[i],i,l_val2[i],i);
//      printf("在a[%d]右侧有%d个数比a[%d]小，有%d个数比a[%d]大\n\n",i,r_val2,i,r_val1,i);
    }
    printf("%lld %lld",ans1,ans2);
    return 0;
}