算法導論歸并排序那塊的一道思考題：
1.merge的時候統計逆序數的個數。
#include<iostream>
using namespace std;
int a[1000];
int cnt;
int merge(int a[],int p,int q,int z)
{
int l[1000],r[1000];
l[0]=q-p+1;
r[0]=z-q;
l[l[0]+1]=0x7fffffff;
r[r[0]+1]=0x7fffffff;
int i,j,k;
for(i=1;i<=l[0];i++)
{
l[i]=a[p+i-1];
}
for(j=1;j<=r[0];j++)
{
r[j]=a[q+j];
}
i=1;
j=1;
for(k=p;k<=z;k++)
{
if(l[i]<=r[j])
a[k]=l[i++];
else
{
a[k]=r[j++];
cnt+=(l[0]-i+1);
}
}
return 0;
}
int mergesort(int a[],int p,int q)
{
if(p>=q)
return 0;
else
{
int mid=(p+q)>>1;
mergesort(a,p,mid);
mergesort(a,mid+1,q);
merge(a,p,mid,q);
}
return 0;
}
int main()
{
int n;
int i;
printf("輸入待排序的數字個數：\n");
scanf("%d",&n);
printf("輸入待排序數組:\n");
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("待排序數組：\n");
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
mergesort(a,1,n);
printf("已排序數組：\n");
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
printf("\n逆序數為：");
printf("%d\n",cnt);
system("pause");
return 0;
}
2.離散化，掃描原始數列，若已插入某數字，設某數字離散化的位置為t，則t的cnt+1，維護樹狀數組。每次cnt+1之前之前算一下sum[n]-sum[t](n為離散化后數組中元素的個數)，然后插入。
//PKU 2299
#include<iostream>
#include<algorithm>
#define N 500010
using namespace std;
int c[N];
int a[N];
int b[N];
int n;
int num=1;
int lowbit(int t)
{
return t&(t^(t-1));
}
int getsum(int t)
{
int sum=0;
for(int i=t;i>0;i-=lowbit(i))
sum+=c[i];
return sum;
}
void update(int t)
{
for(int i=t;i<=num;i+=lowbit(i))
c[i]++;
}
int search(int i)
{
int mid,l=1,r=num;
while(l<=r)
{
mid=(l+r)/2;
if(a[mid]==i)
return mid;
else if(a[mid]>i)
r=mid-1;
else l=mid+1;
}
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
num=1;
sort(a+1,a+1+n);
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1])
a[++num]=a[i];
}
memset(c,0,sizeof(c));
long long sum=0;
update(search(b[1]));
for(int i=2;i<=n;i++)
{
int t=search(b[i]);
sum+=getsum(num)-getsum(t);
update(t);
}
printf("%lld\n",sum);
}
}