「模版」归并排序求逆序对 发表于 2018-11-02 | 分类于 OI NOIP考前练一练模版 1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <cstdio>#include <cctype>#define DEBUG(x) std::cerr << #x << "=" << x << std::endlinline int read() { char ch = getchar(); int res = 0; int flag = 1; for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = -1; for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + ch - '0'; return (flag * res);}const int N_MAX = 100007;int n, a[N_MAX], b[N_MAX];long long ans;void merge_sort(int l, int r) { if(l == r) return; int mid = (l + r) / 2; merge_sort(l, mid), merge_sort(mid + 1, r); int i = l; int j = mid + 1; for(int k = l; k <= r; k ++) { if(j > r || i <= mid && a[i] < a[j]) b[k] = a[i ++]; else b[k] = a[j ++], ans += mid - i + 1; } for(int k = l; k <= r; k ++) a[k] = b[k];}int main() { for(int i = 1; i < 100007; i ++) a[i] = i; for(int i = 1; i <= n; i ++) { int x = read(); int y = read(); std::swap(a[x], a[y]); } merge_sort(1, N_MAX - 1); printf("%lld\n", ans); return 0;}