求助dalao,后面的点,一直卡ac和mle的边缘

P1908 逆序对

zzf12345666 @ 2023-03-27 20:58:07

import java.util.*;
public class 逆序对 {
    static int N=100010;
    static int [] q=new int[N];
    static int [] temp=new int[N];
    static int n;
    static long ans=0;
    public static void main(String[] args) {
       Scanner in =new Scanner(System.in);
       n=in.nextInt();
       for(int i=0;i<n;i++){
           q[i]=in.nextInt();
       }
       System.out.println(merge(0,n-1));
    }
    static long merge(int l,int r){
        if(l>=r){
            return 0;
        }
        int mid=(l+r)/2;
        ans=merge(l,mid)+merge(mid+1,r);
        int i=l;int k=0;int j=mid+1;
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]){
                temp[k++]=q[i++];
            }
            else {
                temp[k++]=q[j++];
                ans+=mid-i+1;
            }
        }
        while(i<=mid){
            temp[k++]=q[i++];
        }
        while(j<=r){
            temp[k++]=q[j++];
        }
        for(int z=l,y=0;z<=r;z++,y++){
            q[z]=temp[y];
        }
        return ans;
    }
}

by ACtheQ @ 2023-07-11 19:11:00

用c艹似乎可刑。


|