Question

一道编程题：求逆序对的个数

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目
输入：第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
输出：两行，第一行为所有逆序对总数，第二行为本质不同的逆序对总数。
样例输入：
4
3
2
3
2

样例输出：
3
1
数据范围：N<=105。Ai<=105。时间限制为1s。

哪位大牛帮下忙，讲下怎么用归并排序或树状数组做，主要是第二问，麻烦讲详细的，有程序的最好，PASCAL和C++的都可以

Answer 1

#include<stdio.h>
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)/*去掉相同的元素，再进行排序*/
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}

printf("%d\n%d",k,m);
}//呵呵，我只会用c写，不过结果是对的。

Answer 2

6分之一，把26个数看成4个数来计算，
得出的答案是一样的，
就是六分之一

Answer 3

引用jbpd34672251b的回答：
#include<stdio.h>
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)/*去掉相同的元素，再进行排序*/
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}

printf("%d\n%d",k,m);
}//呵呵，我只会用c写，不过结果是对的。

前面改成int main(),如果测试程序有时间限制的话，这个算法不够优化，时间超出限制，不过改之后是可以运行的