自动搬运

查看原文

来自洛谷，原作者为

	Deer_Peach Huh？||潜水ing~||私信前请看注意事项

搬运于2025-08-24 22:59:26，当前版本为作者最后更新于2024-06-17 21:46:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

具体代码如下：

#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;
}