You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

95 lines
2.0 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

package class47;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 利用只支持单点增加 + 范围查询的动态开点线段树累加和解决leetcode 315
public class Problem_0315_CountOfSmallerNumbersAfterSelf {
public static class Node {
public int sum;
public Node left;
public Node right;
}
public static class DynamicSegmentTree {
public Node root;
public int size;
public DynamicSegmentTree(int max) {
root = new Node();
size = max;
}
public void add(int i, int v) {
add(root, 1, size, i, v);
}
private void add(Node c, int l, int r, int i, int v) {
if (l == r) {
c.sum += v;
} else {
int mid = (l + r) / 2;
if (i <= mid) {
if (c.left == null) {
c.left = new Node();
}
add(c.left, l, mid, i, v);
} else {
if (c.right == null) {
c.right = new Node();
}
add(c.right, mid + 1, r, i, v);
}
c.sum = (c.left != null ? c.left.sum : 0) + (c.right != null ? c.right.sum : 0);
}
}
public int query(int s, int e) {
return query(root, 1, size, s, e);
}
private int query(Node c, int l, int r, int s, int e) {
if (c == null) {
return 0;
}
if (s <= l && r <= e) {
return c.sum;
}
int mid = (l + r) / 2;
if (e <= mid) {
return query(c.left, l, mid, s, e);
} else if (s > mid) {
return query(c.right, mid + 1, r, s, e);
} else {
return query(c.left, l, mid, s, e) + query(c.right, mid + 1, r, s, e);
}
}
}
public static List<Integer> countSmaller(int[] nums) {
List<Integer> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
int n = nums.length;
for (int i = 0; i < n; i++) {
ans.add(0);
}
int[][] arr = new int[n][];
for (int i = 0; i < n; i++) {
arr[i] = new int[] { nums[i], i };
}
Arrays.sort(arr, (a, b) -> (a[0] - b[0]));
DynamicSegmentTree dst = new DynamicSegmentTree(n);
for (int[] num : arr) {
ans.set(num[1], dst.query(num[1] + 1, n));
dst.add(num[1] + 1, 1);
}
return ans;
}
}