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 200050typedef 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;}
不如意的时候不要尽往悲伤里钻，想想有笑声的日子吧
