看过题解之后总结需要注意的几个地方：

1. 虽然总体数据数量不过5e5，但数据的范围达到了1e9左右，这里树状数组维护了一种类似于bitmap的结构，1e9这么大的范围如果不离散化的话空间上肯定是不允许的；

2. 所以需要开一个数组（比如说叫做index[]）进行离散化，index[i]含义是：如果原序列中，位于i的元素在有序序列中的位置是j，那么index[i] = j。初始化和求和的时候都需要用离散化之后的这个数组进行操作；

3. 一个长度为n的向量中逆序对的数量O(n^2)，输出要用long long，如果用printf输出需要用%lld。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 5e5 + 5;
typedef long long LL;
struct Node { int val, pos; } a[N];
int tree[N], index[N], n;

bool cmp(const Node &x, const Node &y) { return x.val < y.val; }

#define lowbit(x) (x & -x)
void add(int idx) { while (idx <= n) tree[idx]++, idx += lowbit(idx); }
int sum(int idx) { int s = 0; while (idx > 0) s += tree[idx], idx -= lowbit(idx); return s; }

int main()
{
	while (scanf("%d", &n) == 1 && n)
	{
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++) scanf("%d", &(a[i].val)), a[i].pos = i;
		sort(a + 1, a + n + 1, cmp);
		for (int i = 1; i <= n; i++) index[ a[i].pos ] = i;
		
		LL ans = 0;
		for (int i = 1; i <= n; i++) add(index[i]), ans += i - sum(index[i]);
		printf("%lld\n", ans);
	}
	return 0;
}

• Re:树状数组 + 离散化 (1239) PvbeLLN 2024-11-02 19:03:18