1.题目描述：点击打开链接
2.解题思路：本题要求找出经过若干次交换后的数组中逆序对的个数。可以利用树状数组(BIT)解决。计数时可以分为两部分来分别统计。第一部分是统计位置i右边的所有不在原位置的元素中，小于rk[i]的个数。注意：这一部分统计的都是位置发生过变动的元素。第二部分统计位置i右边中仍在原位置的元素中，小于rk[i]的个数。接下来我们考虑如何快速求解这两部分的个数。
第一部分：因为这部分统计的元素均是不在原位置的元素。因此可以考虑用BIT求解。这是BIT的一个经典运用，务必要理解这种方法的原理：假设一共有cnt个不同的位置，从后往前依次考虑每个位置rk[i],如果设x[rk[i]]表示是否存在rk[i]这个元素，存在则设为1，否则设为0，那么所有小于rk[i]的元素就是x[rk[i]-1]+x[rk[i]-2]+...+x[2]+x[1]。而这正是BIT的一个经典的用法——求前缀和！由于是从后往前扫描的，因此凡是被标记过的肯定是位于i右边的元素！这里引入x数组只是为了便于理解，实际上只有s数组用来统计每个结点的和。
第二部分：举例解释如何计算这一部分。我们考虑这样的一个数组：1,2,3,4,5,6 。执行操作2,6,那么数组变为:1,6,3,4,5,2。再执行操作1,4，那么数组变为4,6,3,1,5,2.这时，我们考察元素6的第二部分的逆序对数。可以发现，仍在原位置的只有3,5。因此对于元素6，第二部分逆序对数是2。这个数我们也可以这样求解得到：提取出发生了位置变化的元素，即4,6,1,2。对其排序得到：1,2,4,6。在这个数组中，可以利用递推式sum[i]=sum[i-1]+x[i]-x[i-1]-1求出区间(0,i)之间小于x[i]且仍在原位置的元素的个数，不难得到sum[4]=2(x[4]=6)，sum[2]=0(x[2]=2),所以元素6的第二部分逆序个数为sum[4]-sum[2],即2-0=2个。
这样，只需要将两部分得到的逆序对数相加，即可得到离散化后下标i表示的位置rk[i]的逆序对数。累加所有的逆序对数即可得到答案。
3.代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
#define N 200050
typedef long long ll;
ll sum[N], s[N];
int x[N];
int a[N / 2], b[N / 2], rk[N];
int lowbit(int x)
{
return x&-x;
}
ll get(int k)//求前缀和
{
if (!k)return 0;
return s[k] + get(k - lowbit(k));
}
void add(int k, int v)//将下标为k处的元素增加v
{
if (k > N)return;
s[k] += v;
add(k + lowbit(k), v);
}
ll solve(int from, int to)//计算(from,to]之间的和
{
return (ll)abs(sum[to] - sum[from]);
}
int main()
{
//freopen("t.txt", "r", stdin);
int n;
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i], &b[i]);
x[i] = a[i]; x[i + n] = b[i];//x数组保存所有要交换的位置
rk[i] = i; rk[i + n] = i + n;//rk[i]表示第i个位置的下标
}
sort(x + 1, x + 2 * n + 1);//将这些位置从小到大排序
x[0] = 0;
int cnt = 0;
for (int i = 1; i <= 2 * n;i++)
if (i == 1 || x[i] != x[i - 1])
x[++cnt] = x[i];//去重操作
sum[0] = 0;//sum[i]表示区间(0,i)中比x[i]小的数的个数(在还没进行交换时,x[i]即表示下标，也表示下标对应的元素)
for (int i = 1; i <= cnt; i++)
sum[i] = sum[i - 1] + x[i] - x[i - 1] - 1;
for (int i = 1; i <= n; i++)
{
int aa = lower_bound(x + 1, x + cnt + 1, a[i]) - x;
int bb = lower_bound(x + 1, x + cnt + 1, b[i]) - x;
swap(rk[aa], rk[bb]);
}
memset(s, 0, sizeof(s));
ll ans = 0;
for (int i = cnt; i; i--)
{
ans += get(rk[i]);//第一部分：计算区间[i+1,n)中，有多少个元素的值小于rk[i]，只考虑位置发生过改变的元素
ans += solve(i, rk[i]);//第二部分：计算区间(i,rk[i])中，有多少个元素的值小于rk[i]，只考虑位置未发生过改变的元素
add(rk[i], 1);//标记rk[i]
}
printf("%I64d\n", ans);
}
return 0;
}#301 (div.2) E. Infinite Inversions
原文：http://blog.csdn.net/u014800748/article/details/45420085