逆序对是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对
对于这个问题，很容易能想到n^2的算法，但是显然很多时候这个复杂度太高了，我们今天谈谈nlogn的算法。
对于求逆序对，有很多种nlogn的算法，其中一种就是分治法。
其实，分治法求逆序对的算法就是归并排序的思想
假设我们要统计数列a中的逆序对的个数，我们可以先将数列a从中间分成两半得到数组b和c
于是我们有3种情况的逆序对
第一种：i,j都在数列b
第二种：i,j都在数列c
第三种：i在b, j在c
对于第一种和第二种，我们可以通过递归求得，而对于第三种，我们可以在有序的b、c数列基础上直接计算得到
代码奉上：
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <ctime> #include <cstdlib> #include <set> #include <map> #include <cctype> #include <list> #include <cmath> #include <bitset> #include <queue> #include <stack> #include <sstream> #include <functional> #include <cassert> using namespace std; #define tmax(a, b) if (b > a) a = b #define tmin(a, b) if (b < a) a = b char inc() { char _[10]; scanf("%s", _); return _[0]; } int ini() { int _; scanf("%d", &_); return _; } long long inll() { long long _; scanf("%I64d", &_); return _; } double ind() { double _; scanf("%lf", &_); return _; } string ins() { string _; cin >> _; return _; } int inl(char _[]) { if (!fgets(_, (int)1e8, stdin)) return -1; int i = strlen(_); if (_[i - 1] == '\n') _[--i] = 0; return i; } typedef pair<int, int> pii; typedef pair<char, char> pcc; typedef long long LL; const int inf = 0x3f3f3f3f; const LL lnf = 0x3f3f3f3f3f3f3f3f; const double pi = 3.14159265358979323846; const double eps = 1e-8; const int mod = 100007; const int maxn = 500 * 100 + 10; int Count(vector<int> &a) { if (a.size() <= 1) return 0; vector<int> b(a.begin(), a.begin() + a.size() / 2); vector<int> c(a.begin() + a.size() / 2, a.end()); int res = 0; res += Count(b); res += Count(c); int ai = 0, bi = 0, ci = 0; while (ai < a.size()) { if (bi == b.size() || b[bi] >= c[ci] && ci < c.size()) { a[ai++] = c[ci++]; } else { res += ci; a[ai++] = b[bi++]; } } return res; } int main() { int CAS = 0; //std::ios::sync_with_stdio(0); //std::cin.tie(0); #ifdef NIGHT_13 freopen("in.txt", "r", stdin); int time_night_13 = clock(); #endif // NIGHT_13 int n = ini(); vector<int> a; for (int i = 0; i < n; ++i) a.push_back(ini()); printf("%d\n", Count(a)); #ifdef NIGHT_13 fprintf(stderr, "\n-------------------------------------------\n"); fprintf(stderr, "\t Time: %dms", (int)clock() - time_night_13); fprintf(stderr, "\n-------------------------------------------\n\n"); #endif // NIGHT_13 return 0; }
