Codeforces Round #301 (Div. 2) E . Infinite Inversions 树状数组求逆序数

E. Infinite Inversions

time limit per test

2 seconds

memory limit per test

256 megabytes

input standard input

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 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.

Input

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.

Output

Print a single integer — the number of inversions in the resulting sequence.

Sample test(s)

input

2
4 2
1 4

output

input

output

题意：一个无限长的数组（1， 2， 3， 4， .....）， n次操作，每次交换两个位置上的值.

输出最终有多少逆序对数。

由于这题是数字可能会很多，，我们只能离散化之后来求逆序数了，，先把所有操作读进来，，离散化被操作数。而那些被操作数之间的数字可以缩点来处理（就是把所有的数字看成一个数字来处理）。然后就可以求出结果了。。

  1 #include <set>
  2 #include <map>
  3 #include <cmath>
  4 #include <ctime>
  5 #include <queue>
  6 #include <stack>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 typedef unsigned long long ull;
 16 typedef long long ll;
 17 const int inf = 0x3f3f3f3f;
 18 const double eps = 1e-8;
 19 const int MAXN = 4e5+10;
 20 int a[MAXN], tot, n;
 21 int A[MAXN], B[MAXN];
 22 int lowbit (int x)
 23 {
 24     return x & -x;
 25 }
 26 long long arr[MAXN], M;
 27 void modify (int x, int d)
 28 {
 29     while (x < M)
 30     {
 31         arr[x] += d;
 32         x += lowbit (x);
 33     }
 34 }
 35 int sum(int x)
 36 {
 37     int ans = 0;
 38     while (x)
 39     {
 40         ans += arr[x];
 41         x -= lowbit (x);
 42     }
 43     return ans;
 44 }
 45 int p[MAXN],kk[MAXN];
 46 int main()
 47 {
 48     #ifndef ONLINE_JUDGE
 49         freopen("in.txt","r",stdin);
 50     #endif
 51     while (cin >> n)
 52     {
 53         int x, y;
 54         tot = 0;
 55         memset (arr, 0, sizeof (arr));
 56         memset(kk, 0, sizeof (kk));
 57         long long minv = inf;
 58         long long maxv = 0;
 59         map<int, int>pp;
 60         for (int i = 0; i < n; i++)
 61         {
 62             scanf ("%d%d", &x, &y);
 63             minv = min(minv, (long long)min(x, y));
 64             maxv = max(maxv, (long long)max(x, y));
 65             a[tot++] = x;
 66             a[tot++] = y;
 67             A[i] = x;
 68             B[i] = y;
 69         }
 70         sort (a, a+tot);
 71 
 72         tot = unique(a, a+tot) - a;
 73         int ok = 0;
 74         int tmp = tot;
 75         long long j = minv;
 76         int tt;
 77         vector<int>vec;
 78         for (int i = 0; i < tot; )
 79         {
 80             if (a[i] == j)
 81             {
 82                 i++;
 83                 j++;
 84                 ok = 0;
 85             }
 86             else
 87             {
 88                 if (ok == 0)            // 缩点
 89                 {
 90                     ok = j;
 91                     a[tmp++] = j;
 92                     tt = j;
 93                     vec.push_back(tt);
 94                 }
 95                 pp[ok] += a[i]-j;
 96                 j = a[i];
 97             }
 98         }
 99         tot = tmp;
100         sort (a, a+tot);
101         for (int i = 0; i < vec.size(); i++)
102         {
103             int qq = vec[i];
104             if (pp.count(qq) >= 1)
105             {
106                 int ix = lower_bound(a, a+tot, qq)-a+1;
107                 kk[ix] = pp[qq];
108             }
109         }
110         for (int i = 0; i < n; i++)
111         {
112             A[i] = lower_bound(a,a+tot, A[i]) - a + 1;   // 离散化
113             B[i] = lower_bound(a,a+tot, B[i]) - a + 1;
114         }
115         maxv = lower_bound(a, a+tot, maxv) - a + 1;
116         M = maxv+10;
117         for (int i = 1; i <= maxv; i++)
118         {
119             p[i] = i;
120         }
121         for (int i = 0; i < n; i++)
122         {
123             swap(p[A[i]], p[B[i]]);
124         }
125         long long ans = 0;
126         long long cnt = 0;
127         for (int i = 1; i <= maxv; i++)
128         {
129             ans += (long long)(i-1+cnt - sum(p[i]))*max(1,kk[i]);
130             modify(p[i], max(1,kk[i]));
131             cnt += max(1,kk[i]) - 1;
132         }
133         printf("%I64d
", ans);
134     }
135     return 0;
136 }