求助
  • 板块P1908 逆序对
  • 楼主Jacob333
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/23 17:55
  • 上次更新2024/1/23 18:26:25
查看原帖
求助
1222154
Jacob333楼主2024/1/23 17:55

大佬求助 悬关

#include<bits/stdc++.h> 
#define int long long
using namespace std;
#define MAXN 500005
int d[MAXN];
int a[MAXN],b[MAXN],c[MAXN];
int ans = 0;
void merge(int n,int m)
{
	int aa = 1,bb = 1;
	int cc = 0;
	while(aa <= n && bb <= m)
	{
		if(a[aa] < b[bb])
		{
			cc ++;
			c[cc] = a[aa];
			ans += bb - 1;
			aa ++;
		}
		else{
			cc ++;
			c[cc] = b[bb];
			bb ++;
		}
	}
	while(aa <= n)
	{
		cc ++;
		c[cc] = a[aa];
		ans += bb - 1;
		aa ++;
	}
	while(bb <= m)
	{
		cc ++;
		c[cc] = b[bb];
		bb ++;
	}
}
void guibing(int l,int r)
{
	if(l >= r)
	{
		return;
	}
	int mid = (l+r)/2;
	guibing(l,mid);
	guibing(mid+1,r);
	for(int i=l;i<=mid;++i)
	{
		a[i - l + 1] = d[i];
	}
	for(int i=mid+1;i<=r;++i)
	{
		b[i - mid] = d[i];
	}
	merge(mid - l + 1,r - mid);
	for(int i=l;i<=r;++i)
		d[i] = c[i - l + 1];
}
signed main()
{
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&d[i]); 
	}
	guibing(1,n);
	printf("%lld",ans);
}
2024/1/23 17:55
加载中...