社区讨论

归并做的过不了,求救

P1908逆序对参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@locdzjg8
此快照首次捕获于
2023/10/30 12:15
2 年前
此快照最后确认于
2023/11/04 23:56
2 年前
查看原帖
代码
CPP
#include<bits/stdc++.h>
using namespace std;
long long a[500005],b[500005],sss=0;
void gb(int l,int r)
{
	if(l==r) 
	  return;
	long long m=(l+r)/2,i=l,j=m+1,k=l;
	gb(l,m);
	gb(m+1,r);
	while(i<=m&&j<=r)
	{
		if(a[i]<a[j]) 
		{
		  b[k++]=a[i++];
	    }
		else 
		{
		  b[k++]=a[j++];
		  sss=sss+m-l+1;
	    }
	}
	for(;i<=m;i++) 
	  b[k++]=a[i];
	for(;j<=r;j++) 
	  b[k++]=a[j];
	for(i=l;i<=r;i++) 
	  a[i]=b[i];
}
int main()
{ 
	long long n,m,p;
	cin>>n;
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    gb(1,n);
	cout<<sss;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...