离散化+差分/扫描线

1. 常用套路：

:::info TreeMap + 差分
用TreeMap是为了方便求前缀和 ::: :::info 第二种方法是扫描线，利用排序来做 :::

2. 例题

Acwing 1952. 金发姑娘和 N 头牛
思路:
考虑如果温度的范围没那个大的话如何计算？
直接使用差分数组，修改区间，当然这里是有两段区间（这一点和别的题一段区间稍稍有点区别，以前没见过）。然后遍历数组，前缀和就是当前温度下的最大产奶量，找到最大值即可。
考虑本题，温度范围太大，直接用数组存储不现实，但是奶牛的数量有限，故温度的边界是有限的，所有能使用离散化。

把每头奶牛在不同温度下的产奶量列出来，可以构成一个n*T的矩阵，其中n表示奶牛数量，T表示最大温度。就像下面的矩阵一样。
XXXYYYZZZZ
XXYYYZZZZZ
XYYYYZZZZZ
遍历map求前缀和，相当于求当前温度对应的列和。
我们的目标就是要找到和最大的一列的和。
一个问题：能保证只遍历map中的键对应的列就能找到最佳温度吗？
答：能，如果最佳温度不是某个键，说明存在一个距该温度最近的键，该列与最佳温度对应的前缀和应该是一致的。 :::tips 本质：区间修改，单点查询 :::

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            map.merge(-1, x, Integer::sum);
            map.merge(l, y - x, Integer::sum);
            map.merge(r + 1, z - y, Integer::sum);
        }
        int max = 0, sum = 0;
        for (int key : map.keySet()) {
            sum += map.get(key);
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }
}

// 扫描线方法

类似的题目还有：

798. 得分最高的最小轮调
思路：整体考虑很困难(考虑每个区间的得分元素个数)，而分开考虑较为简单(考虑每一个元素的得分区间)
考虑下标为i的元素x(0 <= x < nums.length)在哪段区间内能得分
若x < i 成立，说明得分区间在i的左右两段包括i
此时得分区间的范围是[x, n - 1]，对应于最小轮调为0 <= k <= i - x, i - (n - 1) <= k < 0
若x >= i成立，说明得分区间在i的右半段(可能包括i)
此时得分区间的范围是[x, n - 1]，对应的最小轮调为i - (n - 1) <= k <= i - x
根据x与i的相对大小，需保证k为非负整数(在mod n意义下)

class Solution {
    public int bestRotation(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (nums[i] <= i) {
                diff[0] += 1;
                diff[i - nums[i] + 1] -= 1;
                diff[i + 1] += 1;
                diff[n] -= 1;
            } else {
                diff[i + 1] += 1;
                diff[i - nums[i] + n + 1] -= 1;
            }
        }
        int max = 0, res = -1;
        int s = 0;
        for (int i = 0; i < n; i++) {
            s += diff[i];
            if (s > max) {
                max = s;
                res = i;
            }
        }
        return res;
    }
}