pat顶级1009 Triple Inversions (35 分)

本文主要是介绍pat顶级1009 Triple Inversions (35 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎访问我的pat顶级题解目录哦

题目描述

算法设计

可以利用树状数组来解决这个问题。
由于输入序列的每个元素的值都不会超过$10^5$，因此我们可以开辟一个长$10^5+5$的树状数组c。设计getSum(x)函数表示1到x这些数字在序列中出现次数之和。设计update函数用于更新数字出现次数。
我们要对整个序列A进行两次遍历，第一次从前向后遍历，针对遍历到的数字A[i]，求其左侧比A[i]大的数字出现次数之和，并把结果存储到数组left中。第二次从后向前遍历，针对遍历到的数字A[i]，求其右侧比A[i]小的数字出现次数之和，假设为k，计算$A[i]\ast k$，即为以A[i]为中间的数的triple inversion的个数。累加所有这样的$A[i]\ast k$，即为最终结果。

C++代码

#include <bits/stdc++.h>
using namespace std;
auto lowbit = [](int x) { return x & (-x); };
vector<int> c(100005);
void update(int x, int v) {for (int i = x; i < c.size(); i += lowbit(i))c[i] += v;
}
int getSum(int x) {int sum = 0;for (int i = x; i > 0; i -= lowbit(i))sum += c[i];return sum;
}
int main() {int n;long long ans = 0;cin >> n;vector<int> A(n), left(n);for (int i = 0; i < A.size(); ++i) {cin >> A[i];update(A[i], 1);left[i] = i + 1 - getSum(A[i]);}fill(c.begin(), c.end(), 0);for (int i = A.size() - 1; i >= 0; --i) {update(A[i], 1);ans += left[i] * 1LL * getSum(A[i] - 1);}cout << ans;return 0;
}

这篇关于pat顶级1009 Triple Inversions (35 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---