思路及代码参考：https://blog.csdn.net/u014800748/article/details/45420085
There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions aand b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and pi > pj.
Input
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of swapoperations applied to the sequence.
Each of the next n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) — the arguments of the swap operation.
Output
Print a single integer — the number of inversions in the resulting sequence.
Examples
2
4 2
1 4
4
3
1 6
3 4
2 5
15
Note
In the first sample the sequence is being modified as follows: . It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).
代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<cmath> const int maxn=2e5+5; typedef long long ll; using namespace std; ll s[maxn],sum[maxn]; int ss[maxn]; int a[maxn],b[maxn],pos[maxn]; int lowbit(int x) { return x&(-x); } int n; void update(int pos,int ad) { while(pos<=maxn) { s[pos]+=ad; pos+=lowbit(pos); } } ll getnum(int pos) { ll res=0; while(pos>0) { res+=s[pos]; pos-=lowbit(pos); } return res; } int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i], &b[i]); ss[i] = a[i]; ss[i + n] = b[i]; pos[i] = i; pos[i + n] = i + n; } sort(ss + 1, ss + 2 * n + 1); ss[0] = 0; int cnt = 0; for (int i = 1; i <= 2 * n;i++) if (i == 1 || ss[i] != ss[i - 1]) ss[++cnt] = ss[i]; sum[0] = 0; for (int i = 1; i <= cnt; i++) sum[i] = sum[i - 1] + ss[i] - ss[i - 1] - 1; for (int i = 1; i <= n; i++) { int aa = lower_bound(ss + 1, ss + cnt + 1, a[i]) - ss; int bb = lower_bound(ss + 1,ss + cnt + 1, b[i]) - ss; swap(pos[aa], pos[bb]); } memset(s, 0, sizeof(s)); ll ans = 0; for (int i = cnt; i; i--) { ans += getnum(pos[i]); ans += abs(sum[i]-sum[pos[i]]); update(pos[i], 1); } printf("%lld\n", ans); } return 0; }
原文：https://www.cnblogs.com/Staceyacm/p/11312245.html