2 seconds
256 megabytes
output standard output
There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swapoperations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions a and 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.
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of swap operations 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.
Print a single integer — the number of inversions in the resulting sequence.
2
4 2
1 4
4
3
1 6
3 4
2 5
15
题意：一个无限 长的数组（1， 2， 3， 4， .....）， n次操作， 每次交换两个位置上的值.
输出最终 有多少逆序对数。
由于这题是 数字可能会很多，，我们只能 离散化之后来求 逆序数了，， 先把所有操作读进来，，离散化 被操作数。 而那些被操作数之间的数字可以缩点来处理（就是把所有的数字看成一个数字来处理）。然后就可以求出结果了。。
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int MAXN = 4e5+;
int a[MAXN], tot, n;
int A[MAXN], B[MAXN];
int lowbit (int x)
{
return x & -x;
}
long long arr[MAXN], M;
void modify (int x, int d)
{
while (x < M)
{
arr[x] += d;
x += lowbit (x);
}
}
int sum(int x)
{
int ans = ;
while (x)
{
ans += arr[x];
x -= lowbit (x);
}
return ans;
}
int p[MAXN],kk[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while (cin >> n)
{
int x, y;
tot = ;
memset (arr, , sizeof (arr));
memset(kk, , sizeof (kk));
long long minv = inf;
long long maxv = ;
map<int, int>pp;
for (int i = ; i < n; i++)
{
scanf ("%d%d", &x, &y);
minv = min(minv, (long long)min(x, y));
maxv = max(maxv, (long long)max(x, y));
a[tot++] = x;
a[tot++] = y;
A[i] = x;
B[i] = y;
}
sort (a, a+tot); tot = unique(a, a+tot) - a;
int ok = ;
int tmp = tot;
long long j = minv;
int tt;
vector<int>vec;
for (int i = ; i < tot; )
{
if (a[i] == j)
{
i++;
j++;
ok = ;
}
else
{
if (ok == ) // 缩点
{
ok = j;
a[tmp++] = j;
tt = j;
vec.push_back(tt);
}
pp[ok] += a[i]-j;
j = a[i];
}
}
tot = tmp;
sort (a, a+tot);
for (int i = ; i < vec.size(); i++)
{
int qq = vec[i];
if (pp.count(qq) >= )
{
int ix = lower_bound(a, a+tot, qq)-a+;
kk[ix] = pp[qq];
}
}
for (int i = ; i < n; i++)
{
A[i] = lower_bound(a,a+tot, A[i]) - a + ; // 离散化
B[i] = lower_bound(a,a+tot, B[i]) - a + ;
}
maxv = lower_bound(a, a+tot, maxv) - a + ;
M = maxv+;
for (int i = ; i <= maxv; i++)
{
p[i] = i;
}
for (int i = ; i < n; i++)
{
swap(p[A[i]], p[B[i]]);
}
long long ans = ;
long long cnt = ;
for (int i = ; i <= maxv; i++)
{
ans += (long long)(i-+cnt - sum(p[i]))*max(,kk[i]);
modify(p[i], max(,kk[i]));
cnt += max(,kk[i]) - ;
}
printf("%I64d\n", ans);
}
return ;
}