<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
树状数组
这个问题难点不在树状数组的原理,在如何抽象为树状数组,但巧就巧在原序列是$1..n$的排列,所以n不仅表示长度n,还能表示范围$[1,n]$,之后就跟求逆序对差不多,以“尖刀”图腾为例,由于构成图腾的三个点y坐标中,第二个是最大的,那么分别求出左边比它小的和右边比它小的,乘起来就是“尖刀”图腾的数量,“铁锹”图腾相似,求左右两边比它大的,因此树状数组类的成员base中维护的应该是从1到当前位置,已出现值的个数
其余就没什么难点了,详情请见注释
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class BinaryIndexedTree {
private:
/*
* 阅读过STL源码的应该会发现,模板类开头有很多类似的using行
* 有些是为了降低冗余度,更多的则是为了关联实体含义,增强可读性
* 以下类型的重命名方式跟源码比较相似
*/
using _LL = long long;
using totem_counts = pair<_LL, _LL>;
/*
* arr是原序列,长度为n(length),也是1~n的排列
* base[x]表示的是1~x中已经出现了的数字个数
* higher[x],lower[x]类似的表示大于,小于x的数出现了几个
*/
vector<_LL> arr, base, higher, lower;
int length = 0;//树状数组真正的长度
_LL cntBlade = 0ll, cntSpade = 0ll;//两边都更小的是尖刀(Blade),两边都更大的是铁锹(Spade)
//低位运算
_LL lowbit(int x) {
return x & (-x);
}
//单个位置更新
void update(int id) {
for (int i = id; i <= length; i += lowbit(i)) {
base[i]++;
}
}
//前缀和查询
_LL preSum(int id) {
_LL sum = 0ll;
for (int i = id; i > 0; i -= lowbit(i)) {
sum += base[i];
}
return sum;
}
public:
BinaryIndexedTree(int n) {
length = n;
arr.resize(n + 2);
base.resize(n + 2);
higher.resize(n + 2);
lower.resize(n + 2);
//构造函数中给出原序列
for (int i = 1; i <= n; i++) cin >> arr[i];
}
totem_counts countBladeAndSpade() {
//正序遍历每个数,计算每个数左边大于,小于它的出现了多少次
for (int i = 1; i <= length; i++) {
higher[i] = preSum(length) - preSum(arr[i]);
lower[i] = preSum(arr[i] - 1);
update(arr[i]);//出现了就把它更新到base数组中
}
//为统计另一边做准备
fill(base.begin(), base.end(), 0);
//倒序遍历,计算每个数右边大于,小于它的出现了几次
for (int i = length; i > 0; i--) {
//左右两边乘起来
cntBlade += higher[i] * (preSum(length) - preSum(arr[i]));
cntSpade += lower[i] * preSum(arr[i] - 1);
update(arr[i]);//依旧是要更新base
}
//先输出尖刀数量,再输出铁锹数量
return make_pair(cntBlade, cntSpade);
}
};
//左移运算符重载也可以模板化,并且可以自动推导类型
template <typename T>
ostream& operator<<(ostream& cout, pair<T, T> p) {
cout << p.first << " " << p.second;
return cout;
}
int main() {
//输入规模较大,输入优化建议开启(也可以使用scanf_s)
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
//个人认为此处树状数组类不封装问题也不大,封装的目的只是体现整体性
BinaryIndexedTree BIT(n);
cout << BIT.countBladeAndSpade() << endl;
return 0;
}