algorithm-class/算法周更班/class_2023_03_3_week/Code05_QueryGreaterThanOrEqualTo3Stores.java

package class_2023_03_3_week;

import java.util.Arrays;

// 来自学员问题，大厂笔试面经帖子
// 假设一共有M个车库，编号1~M，时间点从早到晚是从1~T
// 一共有N个记录，每一条记录如下{a, b, c}
// 表示一辆车在b时间点进入a车库，在c时间点从a车库出去
// 一共有K个查询，每个查询只有一个数字X，表示请问在X时刻，
// 有多少个车库包含车的数量>=3，请返回K个查询的答案
// 1 <= M, N, K <= 10^5
// 1 <= T <= 10^9
public class Code05_QueryGreaterThanOrEqualTo3Stores {

	// 暴力方法
	// 为了验证
	public static int[] getAns1(int m, int[][] records, int[] queries) {
		int maxT = 0;
		for (int[] r : records) {
			maxT = Math.max(maxT, Math.max(r[1], r[2]));
		}
		for (int t : queries) {
			maxT = Math.max(maxT, t);
		}
		int[][] stores = new int[m + 1][maxT + 1];
		for (int[] record : records) {
			int s = record[0];
			int l = record[1];
			int r = record[2] - 1;
			for (int i = l; i <= r; i++) {
				stores[s][i]++;
			}
		}
		int k = queries.length;
		int[] ans = new int[k];
		for (int i = 0; i < k; i++) {
			int curAns = 0;
			for (int j = 1; j <= m; j++) {
				if (stores[j][queries[i]] >= 3) {
					curAns++;
				}
			}
			ans[i] = curAns;
		}
		return ans;
	}

	// 正式方法
	// O((N + K)*log(N + K))
	public static int[] getAns2(int m, int[][] records, int[] queries) {
		int n = records.length;
		int k = queries.length;
		// n*2 + k
		int tn = (n << 1) + k;
		int[] times = new int[tn + 1];
		int ti = 1;
		for (int[] record : records) {
			times[ti++] = record[1];
			times[ti++] = record[2] - 1;
		}
		for (int query : queries) {
			times[ti++] = query;
		}
		Arrays.sort(times);
		for (int[] record : records) {
			record[1] = rank(times, record[1]);
			record[2] = rank(times, record[2] - 1);
		}
		for (int i = 0; i < k; i++) {
			queries[i] = rank(times, queries[i]);
		}
		// 所有记录，根据车库编号排序，相同车库的记录就在一起了
		// record  车库   入库时间    出库时间-1
		//         0      1          2
		Arrays.sort(records, (a, b) -> a[0] - b[0]);
		SegmentTree st = new SegmentTree(tn);
		for (int l = 0; l < n;) {
			int r = l;
			while (r < n && records[l][0] == records[r][0]) {
				r++;
			}
			// 同一个车库的记录，records[l.....r-1] l......  l.......
			countRange(records, l, r - 1, st);
			l = r;
		}
		int[] ans = new int[k];
		for (int i = 0; i < k; i++) {
			ans[i] = st.query(queries[i]);
		}
		return ans;
	}

	// records[l.....r]
	// 上面的记录都属于当前的车库
	// 找到哪些时间段，车的数量是 >= 3的
	// 改写线段树!
	public static void countRange(int[][] records, int l, int r, SegmentTree st) {
		int n = r - l + 1;
		int[][] help = new int[n << 1][2];
		int size = 0;
		for (int i = l; i <= r; i++) {
			if (records[i][1] <= records[i][2]) {
				help[size][0] = records[i][1];
				help[size++][1] = 1;
				help[size][0] = records[i][2];
				help[size++][1] = -1;
			}
		}
		Arrays.sort(help, 0, size, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (b[1] - a[1]));
		int count = 0;
		int start = -1;
		for (int i = 0; i < size; i++) {
			int point = help[i][0];
			int status = help[i][1];
			if (status == 1) {
				if (++count >= 3) {
					start = start == -1 ? point : start;
				}
			} else {
				if (start != -1 && start <= point) {
					st.add(start, point);
				}
				if (--count >= 3) {
					start = point + 1;
				} else {
					start = -1;
				}
			}
		}
	}

	// 所有的时间点，在sorted数组中排好序了
	// 给我一个其中的时间点，v
	// 返回，离散化之后的编号！
	public static int rank(int[] sorted, int v) {
		int l = 1;
		int r = sorted.length;
		int m = 0;
		int ans = 0;
		while (l <= r) {
			m = (l + r) / 2;
			if (sorted[m] >= v) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	// 线段树
	// 维持任何时刻存车数量>=3的车库有几个
	// 支持范围时刻的增加
	// 支持单点时刻的查询
	public static class SegmentTree {
		private int tn;
		private int[] sum;
		private int[] lazy;

		public SegmentTree(int n) {
			tn = n;
			sum = new int[(tn + 1) << 2];
			lazy = new int[(tn + 1) << 2];
		}

		private void pushUp(int rt) {
			sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
		}

		private void pushDown(int rt, int ln, int rn) {
			if (lazy[rt] != 0) {
				lazy[rt << 1] += lazy[rt];
				sum[rt << 1] += lazy[rt] * ln;
				lazy[rt << 1 | 1] += lazy[rt];
				sum[rt << 1 | 1] += lazy[rt] * rn;
				lazy[rt] = 0;
			}
		}

		// l...r范围上每个时刻对应的数值+1
		public void add(int l, int r) {
			add(l, r, 1, tn, 1);
		}

		private void add(int L, int R, int l, int r, int rt) {
			if (L <= l && r <= R) {
				sum[rt] += r - l + 1;
				lazy[rt] += 1;
				return;
			}
			int mid = (l + r) >> 1;
			pushDown(rt, mid - l + 1, r - mid);
			if (L <= mid) {
				add(L, R, l, mid, rt << 1);
			}
			if (R > mid) {
				add(L, R, mid + 1, r, rt << 1 | 1);
			}
			pushUp(rt);
		}

		// 查询单点时刻存车数量>=3的车库有几个
		public int query(int index) {
			return query(index, 1, tn, 1);
		}

		private int query(int index, int l, int r, int rt) {
			if (l == r) {
				return sum[rt];
			}
			int m = (l + r) >> 1;
			pushDown(rt, m - l + 1, r - m);
			int ans = 0;
			if (index <= m) {
				ans = query(index, l, m, rt << 1);
			} else {
				ans = query(index, m + 1, r, rt << 1 | 1);
			}
			return ans;
		}

	}

	// 为了测试
	public static int[][] randomRecords(int n, int m, int t) {
		int[][] records = new int[n][3];
		for (int i = 0; i < n; i++) {
			records[i][0] = (int) (Math.random() * m) + 1;
			int a = (int) (Math.random() * t) + 1;
			int b = (int) (Math.random() * t) + 1;
			records[i][1] = Math.min(a, b);
			records[i][2] = Math.max(a, b);
		}
		return records;
	}

	// 为了测试
	public static int[] randomQueries(int k, int t) {
		int[] queries = new int[k];
		for (int i = 0; i < k; i++) {
			queries[i] = (int) (Math.random() * t) + 1;
		}
		return queries;
	}

	// 为了测试
	public static boolean same(int[] ans1, int[] ans2) {
		for (int i = 0; i < ans1.length; i++) {
			if (ans1[i] != ans2[i]) {
				return false;
			}
		}
		return true;
	}

	// 为了测试
	public static void main(String[] args) {
		int M = 20;
		int N = 300;
		int K = 500;
		int T = 5000;
		int testTimes = 5000;
		System.out.println("功能测试开始");
		for (int i = 0; i < testTimes; i++) {
			int m = (int) (Math.random() * M) + 1;
			int n = (int) (Math.random() * N) + 1;
			int k = (int) (Math.random() * K) + 1;
			int t = (int) (Math.random() * T) + 1;
			int[][] records = randomRecords(n, m, t);
			int[] queries = randomQueries(k, t);
			int[] ans1 = getAns1(m, records, queries);
			int[] ans2 = getAns2(m, records, queries);
			if (!same(ans1, ans2)) {
				System.out.println("出错了!");
				break;
			}
		}
		System.out.println("功能测试结束");

		System.out.println("性能测试开始");
		int m = 100000;
		int n = 100000;
		int k = 100000;
		int t = 1000000000;
		int[][] records = randomRecords(n, m, t);
		int[] queries = randomQueries(k, t);
		System.out.println("车库规模 : " + m);
		System.out.println("记录规模 : " + n);
		System.out.println("查询条数 : " + k);
		System.out.println("时间范围 : " + t);
		long start = System.currentTimeMillis();
		getAns2(m, records, queries);
		long end = System.currentTimeMillis();
		System.out.println("运行时间 : " + (end - start) + " 毫秒");
		System.out.println("性能测试结束");
	}
}