树状数组过逆序对大家应该都会，如果不会就可以回去搞普及组了。博主今天就跟大家介绍一下用树状数组+离散化水过逆序对。大家可能很惊讶，洛谷数据那么弱，需要用离散化吗？博主只是用这个向大家介绍一下，做一个模板而已。好了，离散化是什么？就是当它的数据特别大而给出的值只关心大小而不改变答案时，就可以把这些值替换掉：
for(int i = 1;i <= n; ++ i) { scanf("%d", &a[i].val); a[i].id = i; } sort(a + 1, a + n + 1, cmp); for(int i = 1;i <= n; ++ i) f[a[i].id] = i;`离散化就这么容易，你理解了吗？
#include<iostream> #include<cmath> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; #define REP(i, a, b) for(int i = (a), _end_ = (b); i <= _end_; ++ i) const int maxn = 40010; int n, m; struct node { int val, id; }a[maxn]; int c[maxn], f[maxn]; int cmp(node x, node y) { return x.val < y.val; } int Lowbit(int x) { return x & (-x); } long long Getsum(int x) { long long sum = 0; for(int i = x;i > 0; i -= Lowbit(i)) sum += c[i]; return sum; } void Update(int t, int sum) { for(int i = t;i <= n; i += Lowbit(i)) c[i] += sum; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif scanf("%d", &n); REP(i, 1, n) { scanf("%d", &a[i].val); a[i].id = i; } sort(a + 1, a + n + 1, cmp); REP(i, 1, n) f[a[i].id] = i; long long ans = 0; REP(i, 1, n) { Update(f[i], 1); ans += i - Getsum(f[i]); } printf("%lld\n", ans); return 0; }