涂料网站设计网络推广软文范文

树状数组+离散化求逆序对

用一个数组$w[]$来记录遍历到当前数时，每个数出现的次数
由于只关心每个数前边有多少个数比他大，遍历到$i$时，求大于$a[i]$的数有多少个，就是对$[a[i],n]$求和。
之后将$a[i]$的出现次数$w[a[i]]+1$再求后边的答案。

如果暴力来做是$O(n^2)$的（不知道这个对不对，不过不重要）

for (int i = 1; i <= n; i++) {int cnt = 0;for (int j = a[i]; j <= n; j++) {cnt += w[j];}ans += cnt;w[a[i]]++;
}

发现即要做单点修改$w[a[i]]+1$，又要做区间查询$\sum _{j=a[i]}^{n}w[j]$，于是用树状数组维护$w[]$来降低复杂度。

回顾树状数组的两个操作：区间查询 + 单点修改
$query(i)表示查询区间[1,i]的和$
$add(i,k)表示将含有a[i]的点都+k$

（实际上这里说的树状数组是权值树状数组，就是记录每个数出现的次数的树状数组）

一个前提：只关心相对大小，数本身有多大我并不关心，所以可以离散化（否则数据太大的话$w[]$放不下那么大的下标会爆掉）

写法1

按照每个数的大小降序排序，如果大小相等则按照位置降序排序（考虑为什么这么做？）

假设在排序后的数组中第$i$个数的原位置为$p[i]$，树状数组维护的是，每个原位置的数是否出现。
比如：

原数组：3 2 1 5 4
下标　：1 2 3 4 5排序后：5 4 3 2 1
原位置：4 5 1 2 3遍历到第2个数4时，记录情况为：[0, 0, 0, 1, 0]，即原位置为4的数已经出现了。
我们知道4的原位置为5，此时对区间[1, 5]求和，就是原位置5对应的逆序对数量。
把原位置5记录进去。遍历到第3个数3时，记录情况为：[0, 0, 0, 1, 1]，原位置4 5的数已经出现了
知道3的原位置为1，此时对区间[1, 1]求和，就是原位置1对应逆序对的数量。
把原位置1记录进去。遍历到第4个数2时，记录情况为：[1, 0, 0, 1, 1]，原位置1 4 5的数已经出现了
知道2的原位置为2，此时对区间[1, 2]求和，就是原位置2对应逆序对的数量。
把原位置2记录进去。遍历到第5个数1时，记录情况为：[1, 1, 0, 1, 1]，原位置1 2 4 5的数已经出现了
知道1的原位置为3，此时对区间[1, 3]求和，就是原位置3对应逆序对的数量。
把原位置3记录进去。

看懂这一丁点就行，下边是一顿胡扯，可以不看了

---

注意：以下所有情况都在排好序的数组中进行！！！

现在来考虑两个情况

1. 当前数是唯一的，不考虑相同数位置降序排序的情况

$记第i个数为a[i],排序前位置为p[i]$
要查询这个位置对应的逆序对数量
因为我们已经按照降序进行了排序，就变为查询 位置在$p[i]$之前且大于$a[i]$的数的个数
对应到排序后的数组中就是：
　　前$i-1$个数中原位置在$p[i]$之前的数。
　　因为排序已经确保了前$i-1$个数都是比$a[i]$大的数，现在只需要在前$i-1$个数中找到位置在$p[i]$前的数就可以了

比他大的数在排序前只有两种情况：在他前边/在他后边
只有 (排序前在他前边) 的数才会构成逆序对，在他后边的数不会构成逆序对

再次强调，因为是降序排序，故已经确保了 (遍历到第$i$个数时已经记录出现的数) 都是大于$a[i]$的。

那么对于第$i$个数，（比$a[i]$大） 且 （在$p[i]$之前出现） 的数的个数，实际上就是已经记录出现了的数的个数，即$[1,p[i]]$的和。求区间$[1,p[i]]$的和，就是$query(p[i])$。
最后将这个位置的数记为出现，$add(p[i],1)$

2. 如果数不唯一

数不唯一的话按照位置降序排序

考虑一下，假设已经按照位置进行了降序排序
当前数为$a[i]$，位置$p[i]$
排序后数组中在当前数之前的相同数$a[j]$，对应位置$p[j]$一定在$p[i]$后边
那么$[1,p[i]]$求和时，是这样的一个区间：
1 2 3 4 ... p[i] ... p[j] ...
就不会把相同的数也算到逆序对中，这样就避免了重复计算。

总结一下核心：降序排序后每个位置$i$要查询的区间和$[1,p[i]]$，是出现在原数组位置$p[i]$之前且大于当前数的元素个数

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>#define debug(x) std::cerr << "#x" << " = " << x << ' '
#define DEBUG(x) std::cerr << "#x" << " = " << x << std::endltypedef long long ll;
using namespace std;const int N_MAX = 500000 + 10;int n;
int tr[N_MAX];
struct Node {int v, p;bool operator < (const Node& other) const {if (v != other.v) return v > other.v;return p > other.p;}
}a[N_MAX];int lowbit(int x) {return x & -x;
}void inc(int x, int v) {for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}ll calc(int x) {ll sum = 0ll;for (int i = x; i >= 1; i -= lowbit(i)) sum += tr[i];return sum;
}int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i].v, a[i].p = i;sort(a + 1, a + n + 1);ll ans = 0ll;for (int i = 1; i <= n; i++) {ans += calc(a[i].p);inc(a[i].p, 1);}printf("%lld\n", ans);return 0;
}