这个问题实际上是在测试树的数组。
代码:
#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\n", ans);
}
return 0;
}
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=322
版权声明:本文博客原创文章,博客,未经同意,不得转载。