题目描述
blablabla
样例
blablabla
算法1
(归并排序+逆序对) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
PII p[100010];//{身高,编号},额外记录变量是为了知道交换的数具体是哪个,用在原数组中的编号可以唯一代表某一个数
PII tmp[100010];
ll swapcnt[100010];
ll b[100010];
void msort(int l,int r)
{
if(l>=r) return;
int mid=(l+r)/2;
msort(l,mid); msort(mid+1,r);
int k=0,i=l,j=mid+1;
//此时有两个升序数组,起始指针分别以i,j开头.统计逆序对的数量,即看这两个数组中的逆序对数量(它们各自里的逆序对
已经被统计过了)
while(i<=mid&&j<=r)
{
//记录j指针之前的数的数量num2=j-mid-1
//记录i指针及i指针之后的数的数量num1=i-mid+1
//以下两个操作每一个都会将一个新数放入tmp当中,故每次放入新数时,可以统计新数的逆序对数量
//(tmp也是升序数组,这点对后续分析很重要)
if(p[i].x<=p[j].x)
{
swapcnt[p[i].y]+=j-mid-1;//1.i中的数刚被放入,则j指针之前的数(不包括j)均被放入了tmp数组,故均比a[i]小,均构成了逆序对
tmp[k++]=p[i++];
}
else
{
swapcnt[p[j].y]+=mid-i+1;//2.j中的数刚被放入,则i指针及i指针之后(包括i)的数均未放入tmp数组,故均比a[j]大,均构成了逆序对
tmp[k++]=p[j++];
}
}
while(i<=mid)
{
swapcnt[p[i].y]+=j-mid-1;//3.此时j指针指到了其末尾的后一个位置,故后续放入的i中的数均比j中的所有数都大,都构成了逆序对
tmp[k++]=p[i++];
}
while(j<=r) tmp[k++]=p[j++];//i中的数均已放完,后续放入j中数均比i中的大,故没有逆序对产生
for(int i=l,j=0;i<=r;i++,j++) p[i]=tmp[j];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&p[i].x),p[i].y=i;
msort(1,n);
ll res=0;
for(int i=1;i<=n;i++)
{
ll sum=swapcnt[i]*(swapcnt[i]+1)/2;
res+=sum;
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla