考点
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, tot, arr[maxn], dis[maxn], bit[maxn];
int lowbit(int x) { return x & -x; }
void add(int x, int v) {
while (x <= n) {
bit[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += bit[x];
x -= lowbit(x);
}
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i], dis[i] = arr[i];
sort(dis + 1, dis + 1 + n);
tot = unique(dis + 1, dis + 1 + n) - 1 - dis;
int x, ans = 0;
for (int i = 1; i <= n; ++i) {
x = lower_bound(dis + 1, dis + 1 + tot, arr[i]) - dis;
ans = max(ans, query(n) - query(x));
add(x, 1);
}
cout << ans + 1;
return 0;
}
|
思路
对排序精髓的考验，很好的结论题；以序列5 4 3 2 1为例
逆序对的定义为\(i<j,a_i>a_j\)
初始时，元素4有1个，3有2个，2有3个，1有4个
冒泡排序一次后，序列变成了4 3 2 1 5
此时，元素4有0个，3有1个，2有2个，1有3个
这意味着，每一次冒泡排序实际上就是减少每个元素的逆序对，冒泡排序的执行次数就等于最大逆序对个数！
套用离散化+树状数组依次求每个元素的逆序对个数，挨个打擂台保存最大逆序对个数即可。