小和问题

image.png

  1. public static int process(int[] arr, int l, int r) {
  2.     if (l == r) {
  3.         return 0;
  4.     }
  5.     int mid = l + ((r - l) >> 1);
  6.     return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
  7. }
  9. public static int merge(int[] arr, int L, int m, int r) {
  10.     int[] help = new int[r - L + 1];
  11.     int i = 0;
  12.     int p1 = L;
  13.     int p2 = m + 1;
  14.     int res = 0;
  15.     while (p1 <= m && p2 <= r) {
  16.         res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
  17.         help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  18.     }
  19.     while (p1 <= m) {
  20.         help[i++] = arr[p1++];
  21.     }
  22.     while (p2 <= r) {
  23.         help[i++] = arr[p2++];
  24.     }
  25.     for (i = 0; i < help.length; i++) {
  26.         arr[L + i] = help[i];
  27.     }
  28.     return res;
  29. }