程序填空题：求解逆序数问题（分治法）
设a1, a2,…, an是集合{1, 2, …, n}的一个排列，如果$$iaj，则序偶(ai, aj)称为该排列的一个逆序。例如，2, 3, 1有两个逆序：(3, 1)和(2, 1)。设计算法统计给定排列中含有逆序的个数。
```c++
#include
#include
#include
#include
#define N 1000
using namespace std;
int ans=0;
void Merge(int a[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=0;
int *tem=new int[(high-low+1)];
while(i<=mid&&j<=high)
{
if(@@[a[i]>a[j]](2))
{
tem[k++]=a[j++];
@@[ans+=mid-i+1](2);
}
else tem[k++]=a[i++];
}
while(i<=mid)
tem[k++]=a[i++];
while(j<=high)
tem[k++]=a[j++];
for(int k1=0;k1 @@[a[low+k1]=tem[k1]](2);
free(tem);
}
void mergesort(int a[],int low,int high)
{
if(low {
int mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
Merge(a,low,mid,high);
}
}
int main()
{
int a[N],n;
cin>>n;
for(int i=0;i cin>>a[i];
mergesort(a,0,n-1);
cout< return 0;
}
```
### 输入格式:
第一行输入集合中元素个数n，第二行输入n个集合元素。
```in
3
2 3 1
```
### 输出格式:
含有逆序的个数。
```out
2
```
答案：
第1空：a[i]>a[j]
第2空：ans+=mid-i+1
第3空：a[low+k1]=tem[k1]
```c++
#include
#include
#include
#include
#define N 1000
using namespace std;
int ans=0;
void Merge(int a[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=0;
int *tem=new int[(high-low+1)];
while(i<=mid&&j<=high)
{
if(@@[a[i]>a[j]](2))
{
tem[k++]=a[j++];
@@[ans+=mid-i+1](2);
}
else tem[k++]=a[i++];
}
while(i<=mid)
tem[k++]=a[i++];
while(j<=high)
tem[k++]=a[j++];
for(int k1=0;k1
free(tem);
}
void mergesort(int a[],int low,int high)
{
if(low
int mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
Merge(a,low,mid,high);
}
}
int main()
{
int a[N],n;
cin>>n;
for(int i=0;i
mergesort(a,0,n-1);
cout<
}
```
### 输入格式:
第一行输入集合中元素个数n，第二行输入n个集合元素。
```in
3
2 3 1
```
### 输出格式:
含有逆序的个数。
```out
2
```
答案：
第1空：a[i]>a[j]
第2空：ans+=mid-i+1
第3空：a[low+k1]=tem[k1]
