Tallest cow（最高的牛）

题目大意已经很明显了，这里就不再重复

最朴素的做法是首先假设所有牛的高度都是最高高度 $H$，每次输入一个区间 $[A,B]$，就将区间 $[A+1,B-1]$ 内的所有值都减 1，为什么减 1？因为他要求最终可能的最高高度，减多了不合适

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] arr = new int[n + 1];
        int p = cin.nextInt();
        int h = cin.nextInt();
        Arrays.fill(arr, h);
        int m = cin.nextInt();
        Set<String> set = new HashSet<String>();
        int[] op = new int[2];
        for (int i = 0; i < m; i++) {
            op[0] = cin.nextInt(); // A
            op[1] = cin.nextInt(); // B
            Arrays.sort(op);
            if (!set.contains(op[0] + "" + op[1])) {
                set.add(op[0] + "" + op[1]);
                for (int c = op[0] + 1; c < op[1]; c++)
                    arr[c]--;
            }
        }
        for (int i = 1; i <= n; i++)
            System.out.println(arr[i]);
    }
}

这样做的时间复杂度是 $O (n^2)$，可能会 TLE，所以考虑优化

1. 线段树优化，时间复杂度 $O (nlogn)$
2. 差分处理，将开区间 $(A,B)$ 内的所有数减 1，可以转化为差分数组 $d [A+1]--$ 和 $d [B]++$，时间复杂度 O (n)

由于差分时间复杂度更优秀，因此我们选用差分

对差分数组进行操作以后如何求出原数组呢？这里就要利用差分数组的一个性质，差分数组的前缀和是原数组

所以我们可以求出原数组，最终将原数组都加上 $H$ 即可求得答案

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] d = new int[n + 1]; // 差分数组
        int[] sum = new int[n + 1]; // 差分数组的前缀和数组
        int p = cin.nextInt();
        int h = cin.nextInt();
        int m = cin.nextInt();
        Set<String> set = new HashSet<String>();
        int[] op = new int[2];
        for (int i = 0; i < m; i++) {
            op[0] = cin.nextInt(); // A
            op[1] = cin.nextInt(); // B
            Arrays.sort(op);
            if (!set.contains(op[0] + "" + op[1])) {
                set.add(op[0] + "" + op[1]);
                d[op[0] + 1]--;;
                d[op[1]]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + d[i];
            System.out.println(sum[i] + h);
        }
    }
}