有没有Java大佬帮忙看一下，50分，后面全部MLE

charmmm @ 2023-03-27 13:31:45

import java.util.*;
import java.io.*;

public class Main {
    static int N = 500010;
    static int[] ranks = new int[N];
    static int[] tree = new int[N];
    // pair<val,index>
    static List<int[]> a = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(in.readLine()),val,idx;
        String[] s = in.readLine().split(" ");
        a.add(new int[]{0,0});
        for (int i = 1; i<=n; ++i) {
            val = Integer.parseInt(s[i-1]);
            idx = i;
            a.add(new int[]{val,idx});
        }
        // 排序
        Collections.sort(a,(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);
        for (int i = 1;i<=n; ++i) {
            ranks[a.get(i)[1]] = i;
        }
        long res = 0;
        for (int i = n; i>=1; --i) {
            int cnt = query(ranks[i]);
            res+=cnt;
            update(ranks[i],1,n);
        }
        out.write(res + "\n");
        out.flush();
        out.close();
        in.close();
    }

    public static int lowbit(int x) {
        return x&(-x);
    }

    public static void update(int x,int y,int n){
        for (int i = x; i<=n; i+=lowbit(i)) {
            tree[i]+=y;
        }
    }

    public static int query(int n) {
        int res = 0;
        for (int i = n; i!=0; i-=lowbit(i)) {
            res += tree[i];
        }
        return res;
    }
}

by Hagasei @ 2023-03-27 14:55:41

我猜只是数组开多了

by charmmm @ 2023-03-29 15:43:15

@Stream_X

import java.util.*;
import java.io.*;

public class Main {
    static int N = 500005,n;
    static int[] nums = new int[N];
    static List<Integer> all = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(in.readLine());
        String[] s = in.readLine().split(" ");
        for (int i = 1; i<=n; ++i) {
            nums[i] = Integer.parseInt(s[i-1]);
            all.add(nums[i]);
        }
        // 对数据进行离散化
        Collections.sort(all); // 排序
        unique(); // 去重
        // 将所有的数据元素离散化到[1,all.size()]中
        long res = 0;
        int[] tree = new int[all.size()+1];
        for (int i = 1; i<=n; ++i) {
            int tar = find(nums[i]);
            res+=query(tree,all.size())-query(tree,tar);
            update(tree,tar,1);
        }
        out.write(res + "\n");
        out.flush();
        out.close();
        in.close();
    }

    public static int lowbit(int x) {
        return x&(-x);
    }

    public static long query(int[] tree,int n) {
        long sum = 0;
        for (int i = n; i!=0; i-=lowbit(i))
            sum+=tree[i];
        return sum;
    }

    public static void update(int[] tree,int x,int y) {
        for (int i = x; i<=all.size(); i+=lowbit(i)) {
            tree[i]+=y;
        }
    }

    // 返回x离散化之后的值
    public static int find(int x) {
        int l = 0,r = all.size()-1;
        while (l<r) {
            int mid = l+r>>1;
            if (all.get(mid)>=x) r = mid;
            else l = mid+1;
        }
        return l+1; // 下标整体右移一位
    }

    public static void unique() {
        int idx = 0;
        for (int i = 0; i<all.size()-1; ++i) {
            if (i==0 || (all.get(i)!=all.get(i-1))) {
                all.set(idx++,all.get(i));
            }
        }
        all.subList(idx,all.size());
    }
}

佬能不能帮忙看看，我感觉没办法优化了已经，后面五个数据N开小了就RE，开大了就MLE，已经裂开了。。。。。。

by Hagasei @ 2023-03-29 22:10:24

@charmmm 其实是这样的，Java 作为 oo，他本身的内存开销就是很大的，一般像牛客之类的 OJ 为了照顾别语言选手，都会把非 C/C++ 开的时空限制增大。但是 luogu 并没有，所以过不了就只能换语言了

by Hagasei @ 2023-03-29 22:11:00

您是为了练习算法还是练习 java 语言本身呢

by charmmm @ 2023-03-30 09:27:31

@Stream_X 明白了，怪不得题解区找不到Java选手

by charmmm @ 2023-03-30 09:28:30

@Stream_X 算法，没有系统的学过C++，不熟悉STL，所以就一直用的Java

by charmmm @ 2023-03-30 09:28:59

@Stream_X 感谢佬