huhu的小世界

1
package org.example;
2

3
import java.io.*;
4

5
// 小和问题
6
public class Main {
7

8
    public static int n;
9
    public static int[] arr = new int[100100];
10
    public static int[] help = new int[100100];
11
    // 结果可能数据比较大，用int会溢出
12
    public static long result = 0;
13

14
    public static void main(String[] args) throws IOException {
15
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
16
        StreamTokenizer in = new StreamTokenizer(br);
17
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
18

19
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
20
            n = (int) in.nval;
21
            for (int i = 0; i < n; i++) {
22
                in.nextToken();
23
                arr[i] = (int) in.nval;
24
            }
25
            gB(0, n - 1);
26
            out.println(result);
27
            result = 0;
28
        }
29

30
        out.flush();
31
        out.close();
32
        br.close();
33
    }
34

35
    private static void gB(int l, int r) {
36
        if (l == r) return;
37
        int mid = (l + r) >> 1;
38
        gB(l, mid);
39
        gB(mid + 1, r);
40
        smallSum(l, mid, r);
41
    }
42

43
    private static void smallSum(int l, int m, int r) {
44

45
        int left = l, right = m + 1, flag = l;
46
        while (left <= m && right <= r) {
47
            if (arr[left] <= arr[right]) {
48
                result += (long) arr[left] * (r - right + 1);
49
                // 当发现左边区间的值小于右边区间的某值时，此时因为两个区间都是有序的。
50
                // 那么对于右边区间的当前值来说，其右手的所有剩下的值都将大于左边区间的当前值。
51
                // 所以对于其右手的所有剩下的值来说左边区间的当前值就是它们各自小和的一部分。
52
                help[flag++] = arr[left++];
53
            } else {
54
                help[flag++] = arr[right++];
55
            }
56
        }
57

58
        while (left <= m) help[flag++] = arr[left++];
59
        while (right <= r) help[flag++] = arr[right++];
60

61
        for (int i = l; i <= r; i++) {
62
            arr[i] = help[i];
63
        }
64
    }
65
}

1
static int[] help = new int[50100];
2

3
public int reversePairs(int[] nums) {
4
    if (nums.length <= 1) return 0;
5
    return gB(0, nums.length - 1, nums);
6
}
7

8
private int gB(int l, int r, int[] nums) {
9
    if (l == r) {
10
        return 0;
11
    }
12
    int mid = (l + r) / 2;
13
    return gB(l, mid, nums) + gB(mid + 1, r, nums) + merge(l, mid, r, nums);
14
}
15

16
private int merge(int l, int mid, int r, int[] nums) {
17
    int ans = 0;
18

19
    // 统计跨越左右的翻转对数量
20
    for (int i = l, j = mid + 1; i <= mid; i++) {
21
        while (j <= r && (long) nums[i] > (long) nums[j] * 2) j++;
22
        ans += j - mid - 1;
23
    }
24

25
    // 归并排序：合并两个有序区间
26
    int left = l, right = mid + 1, index = l;
27
    while (left <= mid && right <= r) {
28
        if (nums[left] <= nums[right]) help[index++] = nums[left++];
29
        else help[index++] = nums[right++];
30
    }
31

32
    while (left <= mid) help[index++] = nums[left++];
33
    while (right <= r) help[index++] = nums[right++];
34

35
    for (int i = l; i <= r; i++) nums[i] = help[i];
36

37
    return ans;
38
}