1 条题解

  • 0
    #include <iostream>
    #include <vector>
    #define int long long 
    using namespace std;
    int ans=0;
    void mergesort(vector<int>&a,int l,int mid,int r){
    	int *tmp=new int[r-l+1];
    	int i=l,j=mid+1,index=0;
    	while(i<=mid&&j<=r){
    		if(a[i]<=a[j])tmp[index++]=a[i++];
    		else{
    			tmp[index++]=a[j++];
    			ans+=mid-i+1;
    		}
    	}
    	while(i<=mid)tmp[index++]=a[i++];
    	while(j<=r)tmp[index++]=a[j++];
    	for(int i=0;i<index;i++){
    		a[l+i]=tmp[i];
    	}
    	delete[]tmp;
    }
    void merge_up2down(vector<int>&a,int l,int r){
    	if(l>=r)return;
    	int mid=(l+r)>>1;
    	merge_up2down(a,l,mid);
    	merge_up2down(a,mid+1,r);
    	mergesort(a,l,mid,r);
    }
    signed main(){
    	int n;
    	cin>>n;
    	vector<int> a(n);
    	for(int i=0;i<n;i++)cin>>a[i];
    	merge_up2down(a,0,n-1);
    	cout<<ans<<endl;
    	return 0;
    }
    
    • 1

    信息

    ID
    1252
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    40
    已通过
    16
    上传者