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);
        }
    }
}