蒟蒻求助
  • 板块P1908 逆序对
  • 楼主sxyn
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/7/27 10:36
  • 上次更新2023/11/6 22:08:35
查看原帖
蒟蒻求助
197479
sxyn楼主2020/7/27 10:36

不知道哪里出错了。。求指导

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[22233333],b[22233333],ans=0;
long long nxd(int l,int r)
{
	if(l==r) return 0;
	int m=(l+r)/2;
	ans=nxd(l,m)+nxd(m+1,r);
	int p1=l,p2=m+1;
	for(int i=l;i<=r;i++)
	{
		if(p1>m)
		{
			b[i]=a[p2];
			p2++;
		}
		else if(p2>r)
		{
			b[i]=a[p1];
			p1++;
		}
		else if(a[p1]<b[p2])
		{
			b[i]=a[p1];
			p1++;
		}
		else 
		{
			b[i]=a[p2];
			p2++;
			ans+=m-p1+1;
		}
	}
	for(int i=l;i<=r;i++)
		a[i]=b[i];
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cout<<nxd(1,n)<<endl;
	return 0;
}
2020/7/27 10:36
加载中...