好吧，看到这个图片就知道是干什么的了，求逆序数- -
可以用线段树，貌似还可以用归并排序，这题应该是考的归并排序，毕竟是递归分治- -
基本上都忘了，再写一写试试吧。
AC
/////////////////////////////////////////////////////////////////////////////////////////////
#include<stdio.h> #define maxn 500005 int a[maxn], b[maxn];
long long sum=0; void MergeSort(int a[], int N);
void Merge(int a[], int N); int main()
{
int i, n; while(scanf("%d", &n), n)
{
for(i=0; i<n; i++)
scanf("%d", &a[i]); sum=0;
MergeSort(a, n); printf("%I64d\n", sum);
} return 0;
}
void MergeSort(int a[], int N)
{
if(N > 1)
{
MergeSort(a, N/2);
MergeSort(a+N/2, N-N/2);
Merge(a, N);
}
}
void Merge(int a[], int N)
{
int i=0, j=N/2, k=0;
int M=j;
while(i < M && j<N)
{
if(a[i] > a[j])
{
b[k++] = a[j++];
sum += M-i;
}
else
b[k++] = a[i++];
} while(i<M)
b[k++] = a[i++];
while(j<N)
b[k++] = a[j++]; for(i=0; i<N; i++)
a[i] = b[i];
}