题解：P10589 楼兰图腾

· · 题解

讲一下蒟蒻的原始思路，就是暴力。

求尖刀图腾时，建一个数组分别求每个点左边和右边比该点的坐标高的点，再相乘求出由该点为中心的尖刀图腾数量。求铁锹图腾时相反，建一个数组分别求每个点左边和右边比该点的坐标低的点，再相乘求出由该点为中心的铁锹图腾数量。

具体代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200001],L[200001],R[200001],l[200001],r[200001],ans1,ans2;//L，R数组记录铁锹，l,r数组记录尖刀，ans1，ans2分别指尖刀与铁锹
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }for(int i=2;i<n;i++){
        for(int j=1;j<i;j++){
            if(a[j]>a[i])L[i]++;//统计左边比该点大的点
            if(a[j]<a[i])l[i]++;//统计左边比该点小的点
        }for(int j=i+1;j<=n;j++){
            if(a[j]>a[i])R[i]++;//统计右边比该点大的点
            if(a[j]<a[i])r[i]++;//统计右边比该点小的点
        }
    }for(int i=2;i<n;i++){
        ans1+=L[i]*R[i];//统计答案
        ans2+=l[i]*r[i];
    }cout<<ans1<<" "<<ans2;
    return 0;
}

最后是不出意外的超时了，拿到了半道绿题。

现在讲下正解：树状数组。

这道题可以先倒序遍历序列 a，求出每个 a _ i 后面有多少个数比它大，记为 r _ i。再正序遍历序列 a，利用树状数组求出每个 a _ i 前面有多少个数比它大，记为 l _ i。

用数组 t 来记录数值出现的次数，后面的处理与上一个的思路的处理差不多，就不仔细讲了。

代码：

#include<bits/stdc++.h>
#define int long long//不开long long见祖宗
using namespace std;
int n,a[200001],ans1,ans2;
int L[200001][2],R[200001][2],t[200001];//数组
int lowbit(int x){//模板
    return x&-x;
}void add(int x,int y){
    while(x<=n){
        t[x]+=y;
        x=x+lowbit(x);
    }return ;
}int ask(int x){
    int cnt=0;
    while(x){
        cnt+=t[x];
        x=x-lowbit(x);
    }return cnt;
}signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }for(int i=1;i<=n;i++){//统计数量
        L[i][0]=i-1-ask(a[i]);
        L[i][1]=ask(a[i]-1);
        add(a[i],1);
    }memset(t,0,sizeof(t));
    for(int i=n;i>=1;i--){//统计数量
        R[i][0]=n-i-ask(a[i]);
        R[i][1]=ask(a[i]-1);
        add(a[i],1);
    }for(int i=1;i<=n;i++){//处理答案
        ans1+=L[i][0]*R[i][0];
        ans2+=L[i][1]*R[i][1];
    }cout<<ans1<<" "<<ans2;
    return 0;
}