pat顶级1027 Larry and Inversions (35 分)

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

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

题目描述

pat顶级1027 Larry and Inversions (35 分)题目描述

算法设计

可以利用树状数组来解决这个问题。
由于n不会超过 $10^3$ ，因此我们可以开辟一个长1005的树状数组c。设计getSum(x)函数表示1到x这些数字在序列中出现次数之和。设计update函数用于更新数字出现次数。
首先我们要明白如果我们定义A[i]左侧比A[i]大的数字个数为S[i]，那么对于序列A[i]~A[j]，其逆序数为 $\sum _{k=i}^j S_k$ 。我们可以通过树状数组求解A[i]左侧比A[i]大的数字个数，进而可以求解一个序列的逆序数。建立一个二维数组ans，存储每个区间的逆序数，即ans[i][j]表示序列A[i]~A[j]的逆序个数。
接下来，假设我们求得序列A[i]~A[j]的逆序数为ans[i][j]，由于序列A[i]~A[j]任选两个数的情况数为 $C_{j-i+1}^2=\frac {(j-i+1)(j-i)} 2$ ，那么将序列A[i]~A[j]翻转后的逆序数就为 $C_{j-i+1}^2-ans[i][j]$ 。
如果我们求得序列A[1]~A[n]的逆序数为ans[1][n]，那么对于任意的 $\leq i \leq n, i \leq j \leq n$ ，将序列A[i]~A[j]翻转后的逆序数K应该为：
$K=ans[1][n]-ans[i][j]+C_{j-i+1}^2-ans[i][j]=ans[1][n]-2*ans[i][j]+\frac {(j-i+1)(j-i)} 2$

C++代码

#include <bits/stdc++.h>
using namespace std;
auto lowbit = [](int x) { return x & (-x); };
vector<int> c(1005);
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, a;cin >> n;vector<int> A(n + 1);for (int i = 1; i <= n; ++i)cin >> A[i];int ans[n + 1][n + 1] = {};for (int i = 1; i <= n; ++i) {fill(c.begin(), c.end(), 0);for (int j = i; j <= n; ++j) {update(A[j], 1);ans[i][j] = ans[i][j - 1] + j - i + 1 - getSum(A[j]);}}for (int i = 1; i <= n; ++i) {for (int j = i; j <= n; ++j) {int k = ans[1][n] - 2 * ans[i][j] + (j - i) * (j - i + 1) / 2;cout << k << (i == n && j == n ? "" : " ");}}return 0;
}