nyoj 322 Sort 【树阵】

这个问题实际上是在测试树的数组。

代码：

#include <cstdio>
#include <cstring>
int c[1005];

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

int getsum(int x){
	int sum = 0;
	while(x){
		sum += c[x]; x -= lowbit(x);
	}
	return sum;
}

void add(int x, int val){
	while(x <= 1004){
		c[x] += val;
		x += lowbit(x);
	}
}
int main(){
	int t, n, ans, s;
	scanf("%d", &t);
	while(t --){
		scanf("%d", &n);
		ans = 0;
		memset(c, 0, sizeof(c));
		for(int i = 1; i <= n; i ++){
			scanf("%d", &s);
			ans += (s-getsum(s)-1);
			add(s, 1);
		}
		printf("%d
", ans);
	}
	return 0;
}        

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=322

版权声明：本文博客原创文章，博客，未经同意，不得转载。