algorithm-class/算法周更班/class_2022_07_2_week/Code05_LineSweepAlgorithm1.java

package class_2022_07_2_week;

import java.util.Arrays;

// 我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 
// 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标
// (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。
// 计算平面中所有 rectangles 所覆盖的 总面积 。
// 任何被两个或多个矩形覆盖的区域应只计算 一次 。
// 返回 总面积 。因为答案可能太大，返回 10^9 + 7 的 模 。
// 本题测试链接 : https://leetcode.cn/problems/rectangle-area-ii/
public class Code05_LineSweepAlgorithm1 {

	// x y 
	public static int rectangleArea(int[][] rectangles) {
		int n = rectangles.length;
		long[][] arr = new long[n << 1][4];
		long max = 0;
		for (int i = 0; i < n; i++) {
			// x1 y1 左下角点的坐标
			// x2 y2 右上角点的坐标
			// 解释一下y1为啥要+1
			// 比如y1 = 3, y2 = 7
			// 实际的处理的时候，真实的线段认为是闭区间[4,7]的
			// 如果不这么处理会有问题
			// 比如先在y1 = 3, y2 = 7上，都+1
			// 那么此时：
			// value: 0 0 1 1 1 1 1 0
			// index: 1 2 3 4 5 6 7 8
			// 这是不对的！
			// 因为线段[3,7]长度是4啊！而在线段树里，是5个1！
			// 所以，y1 = 3, y2 = 7
			// 我们就是认为是4~7，都+1
			// 那么此时：
			// value: 0 0 0 1 1 1 1 0
			// index: 1 2 3 4 5 6 7 8
			// 线段树上，正好4个1，和我们想要的距离是一致的
			int x1 = rectangles[i][0];
			int y1 = rectangles[i][1] + 1;
			int x2 = rectangles[i][2];
			int y2 = rectangles[i][3];
			arr[i][0] = x1;
			arr[i][1] = y1;
			arr[i][2] = y2;
			arr[i][3] = 1;
			arr[i + n][0] = x2;
			arr[i + n][1] = y1;
			arr[i + n][2] = y2;
			arr[i + n][3] = -1;
			max = Math.max(max, y2);
		}
		return coverArea(arr, n << 1, max);
	}

	public static int coverArea(long[][] arr, int n, long max) {
		// 所有的事件，都在arr里
		// [x, y1, y2, +1/-1]
		// 早 -> 晚
		Arrays.sort(arr, 0, n, (a, b) -> a[0] <= b[0] ? -1 : 1);
		// max y的值，可能的最大值，非常大也支持！
		DynamicSegmentTree dst = new DynamicSegmentTree(max);
		long preX = 0;
		long ans = 0;
		for (int i = 0; i < n; i++) {
			// dst.query() : 开点线段树告诉你！y方向真实的长度！
			ans += dst.query() * (arr[i][0] - preX);
			ans %= 1000000007;
			preX = arr[i][0];
			dst.add(arr[i][1], arr[i][2], arr[i][3]);
		}
		return (int) ans;
	}

	public static class Node {
		public long cover;
		public long len;
		public Node left;
		public Node right;
	}

	public static class DynamicSegmentTree {
		public Node root;
		public long size;

		public DynamicSegmentTree(long max) {
			root = new Node();
			size = max;
		}

		public void add(long L, long R, long cover) {
			add(root, 1, size, L, R, cover);
		}

		private void add(Node cur, long l, long r, long L, long R, long cover) {
			if (L <= l && R >= r) {
				cur.cover += cover;
			} else {
				if (cur.left == null) {
					cur.left = new Node();
				}
				if (cur.right == null) {
					cur.right = new Node();
				}
				long m = l + ((r - l) >> 1);
				if (L <= m) {
					add(cur.left, l, m, L, R, cover);
				}
				if (R > m) {
					add(cur.right, m + 1, r, L, R, cover);
				}
			}
			pushUp(cur, l, r);
		}

		private void pushUp(Node cur, long l, long r) {
			if (cur.cover > 0) {
				cur.len = r - l + 1;
			} else {
				cur.len = (cur.left != null ? cur.left.len : 0) + (cur.right != null ? cur.right.len : 0);
			}
		}

		public long query() {
			return root.len;
		}

	}

}