AcWing 241. 楼兰图腾
原题链接
简单
作者:
越过山丘_0
,
2024-03-30 13:55:52
,
所有人可见
,
阅读 16
本题解注重于如何分析题目,并且详细分析求解的过程:
1.首先这个题的核心目标就是求出来每个点的左边有几个点比这个点高和低,每个点的右边有几个点比这个点高和低,
最后统一计算一下V和反V的数量即可
2.如果暴力统计的话每个点都要循环一遍所有点,时间复杂度是o(n^2)级别的,显然会超时,根据数据范围知,
本题应该是一个o(nlogn)的做法
3.因为a[i]对应的是一个1~n的一个全排列,全排列隐藏的条件是每个点只会选一次,通过这一点挖掘出可以用树状数组求解
首先假定y=a[i],
在本题中我们把树状数组的原数组看成y从1到n的一个排序,如果读到这个点,树状数组的y位置就会+1,还没读到的点,
树状数组对应的值是0
我们可以任选某个点的一边,先统计左边或者先统计右边是一样的,不妨先统计左边比这个点高和低的点有多少个
4.这道题要按照顺序,边建树状数组边统计,假定先统计每个点的左边,树状数组对应的原数组其实是y,也就是1~n,
树状数组已经读到的点就是当前点的左边的点,
还没读到的点在树状数组中就是0,也就是当前点右边的点,明白了这一性质就问题就简单多了
5.解决了左边点的相对位置的数量问题,再来解决右边有多少点比当前点高和低,首先重置树状数组,和计算左边的一样,
这次遍历a[i]的顺序变了,因为要统计右边,所以要从右往左建树状数组
,树状数组已经读入的数都是当前点右边的数,树状数组还没读入的数都是当前点左边的数
6.最后定义两个long long 类型防止爆int来累加计算即可
本题代码--注释较为详细
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200010;
typedef long long LL;
int n; //n个图腾
int a[N]; //存储n个图腾对应的y
int tree[N]; //树状数组
int higher[N]; //存储一个点左边比它高的点的个数
int lower[N]; //存储一个点左边比它低的点的个数
//树状数组三个函数,一个lowbit,一个修改,一个查询
int lowbit(int x){
return x&-x;
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i))tree[i]+=c;
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i))res+=tree[i];
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//首先统计每个点的左边
for(int i=1;i<=n;i++){ //顺序很重要,第一个是从左到右
int y=a[i];
higher[i]=query(n)-query(y);
lower[i]=query(y-1);
add(y,1);
}
LL ans1=0,ans2=0; //ans1表示正V的数量,ans2表示反V的数量
//清空树状数组,重新建树
memset(tree,0,sizeof tree);
for(int i=n;i>=1;i--){
int y=a[i];
ans1+=(LL)higher[i]*(query(n)-query(y));
ans2+=(LL)lower[i]*(query(y-1));
add(y,1);
}
printf("%ld %ld",ans1,ans2);
return 0;
}