花了近5个小时，改的乱七八糟，终于A了。
一个无限数列，1,2,3,4,...,n....,给n个数对<i,j>把数列的i,j两个元素做交换。求交换后数列的逆序对数。
很容易想到离散化+树状数组，但是发现那些没有交换的数也会产生逆序对数，但我没有算。
经明神提示， 把没有用到的数字段化成点。然后用树状数组算一下就好了。
然后我用一个数组记录每个点的长度。比如 <1,2><5,6>,1,2,3,4,5,6只有1,2,5,6用到了，那么离散化为1,2,3,4,5，f[1]=f[2]=f[4]=f[5]=1,f[3]=2，数对变为<1,2><4,5>
莫名有wa了第七组样例，看了数据（捂脸）后改为longlong，有莫名re一发，无脑改了数组长度，然后。。。就a了。。。
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std; typedef long long ll; struct node
{
int val;
int pos;
bool operator < (const node a) const
{
return val < a.val;
}
} x[500005]; int a[500005];
int b[500005];
int c[500005];
int d[500005]; int f[500005]; int lowbit(int x)
{
return x & (-x);
} int sum(int n)
{ int ans = 0;
while (n > 0)
{
ans += c[n];
n -= lowbit(n);
}
return ans;
} void update(int pos, int n, int num)
{ while(pos <= n)
{
c[pos] += num;
pos += lowbit(pos);
}
} int main()
{
int n;
scanf("%d", &n); for (int i = 0; i < 2 * n; ++i)
{
scanf("%d", &x[i].val);
x[i].pos = i;
}
// 离散化
sort(x, x + 2 * n);
int cnt = 0;
for (int i = 0; i < 2 * n; ++i)
{
if (i == 0 || x[i].val > x[i - 1].val)
{
++cnt;
if (x[i].val - x[i - 1].val > 1)
{
f[cnt++] = x[i].val - x[i - 1].val - 1;
}
f[cnt] = 1;
}
if (x[i].pos & 1)
b[x[i].pos / 2] = cnt;
else
a[x[i].pos / 2] = cnt;
}
for (int i = 1; i <= cnt; ++i) d[i] = i; //交换
for (int i = 0; i < n; ++i)
{
swap(d[a[i]], d[b[i]]);
} ll ans = 0;
ll tot = 0;
for (int i = 1; i <= cnt; ++i)
{
ll temp = sum(d[i]);
ans += (tot - temp) * f[i];
update(d[i], cnt, f[i]);
tot += f[i];
} printf("%lld", ans); return 0;
} /**
Input:
5
2 5
6 3
4 6
5 4
2 5 2
1 2
5 6 output:
5
2
*/