题目就是求多组数据的逆序对。对于每组数据，$n$ 的范围较大，为 $1 \le n \le 10^6$。而求逆序对，就需要树状数组加上离散化。
离散化
就是把无限空间中有限的个体映射到有限的空间中去，这样即使 $a_i$ 较大，也不会导致 $\texttt{MLE}$。
首先把用 $a_i$ 记录输入的数，$b_i$ 记录编号 $i$，然后根据 $a_i$ 的大小将 $b$ 数据进行排序。这样，较大的数就由编号进行替代了。
1
2
3
4
5
6
7
8
9
| for(register ll i = 1;i <= n;++i) scanf("%lld",&a[i]),b[i] = i;
sort(b + 1,b + 1 + n,cmp);
for(register ll i = 1;i <= n;++i) a[b[i]] = i;
bool cmp(ll x,ll y)
{
if(a[x] == a[y]) return x < y;
return a[x] < a[y];
}
|
树状数组
具体的写法见 【模板】树状数组 1，在此介绍如何统计逆序对的个数。
对于编号为 $i$ 的数，若是要构成逆序对，则需要找到编号为 $1$ 至 $i - 1$ 且比 $a_i$ 大的数才行。每次加向树状数组能新加数之前先查询比将要加入的数大的个数，于是遍历 $1$ 至 $n$ 后，个数相加的和就是逆序对的个数了。因此有如下代码：
1
2
| ans += i - 1 - find(a[i]);
add(a[i]);
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define ll long long
#define init(x) memset (x,0,sizeof (x))
using namespace std;
const int MAX = 1e6 + 50;
ll a[MAX],b[MAX],c[MAX],n,ans;
int t;
bool cmp(ll x,ll y);
ll lowbit(ll x);
ll find(ll x);
void add(ll x);
int main()
{
while (scanf("%d",&n) != EOF)
{
init (a);init (b);init (c);ans = 0;
for(register ll i = 1;i <= n;++i) scanf("%lld",&a[i]),b[i] = i;
sort(b + 1,b + 1 + n,cmp);
for(register ll i = 1;i <= n;++i) a[b[i]] = i;
for(register ll i = 1;i <= n;++i)
{
ans += i - 1 - find(a[i]);
add(a[i]);
}
printf("%lld\n",ans);
}
return 0;
}
bool cmp(ll x,ll y)
{
if(a[x] == a[y]) return x < y;
return a[x] < a[y];
}
ll lowbit(ll x)
{
return x & (-x);
}
ll find(ll x)
{
ll num = 0;
for(ll i = x;i >= 1;i -= lowbit(i)) num += c[i];
return num;
}
void add(ll x)
{
for(ll i = x;i <= n;i += lowbit(i)) ++c[i];
}
|
