#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 1005;

typedef struct Node
{
	int pos;
	int value;
}Node;
Node node[MAXN];
int tree[MAXN], temp[MAXN];//离散化
int n;

bool cmp(Node a, Node b)
{
	/*if(a.value == b.value)
	{
		return a.pos < b.pos;
	}*/
	return a.value < b.value;
}

int lowbit(int x)
{
	return x & (-x); 
}

int getsum(int pos)
{
	int sum = 0;
	while (pos > 0)
	{
		sum += tree[pos];
		pos -= lowbit(pos);
	}
	return sum;
}

void update(int pos, int value)
{
	while (pos <= n)
	{
		tree[pos] += value;
		pos += lowbit(pos);
	}
}
int main()
{
	freopen("in.txt", "r", stdin);
	int t, ans;
	scanf("%d", &t);
	for(int i = 1; i <= t; i++)
	{
		scanf("%d", &n);
		ans = 0;
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &node[j].value);
			node[j].pos = j;
		}
		sort(node + 1, node + n + 1, cmp);
		for (int j = 1; j <= n; j++)
		{
			temp[node[j].pos] = j;
		}
		memset(tree, 0, sizeof(tree));
		for (int j = 1; j <= n; j++)
		{
			update(temp[j], 1);
			ans += j - getsum(temp[j]);
		}
		printf("Scenario #%d:\n", i);
		printf("%d\n\n", ans);
	}
	return 0;
}
为什么不加这一句/*if(a.value == b.value)
	{
		return a.pos < b.pos;
	}*/，   WA呢？求解！

• Re:树状数组离散化的一个问题 (32) Alethia 2019-06-27 23:47:40