题解 | #校门外的树#

一、暴力解法

import java.util.Scanner;

public class Main {
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []shuzu = new int [n+1];
        int sum = 0;
        for(int i=0;i<m;i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            
            for(int j = start;j<=end;j++){
                if(shuzu[j]==0){
                    shuzu[j]=1;
                    sum += 1;
                }
            }

        }
        System.out.println(n-sum+1);
    }
}

二、前缀和解法

其中前缀和解法需要注意两点

(1)sum[0]==a[0];

(2)使a[start]==1，a[end+1]==-1当出现end相同的时候会出现前缀和不能等于0；

正确写法是a[start]--，a[end+1]++；

import java.util.Scanner;
public class Main {
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int n = sc.nextInt();
        int []a = new int[N+1];
        int []sum = new int[N+1];
        for(int i = 0;i<n;i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            a[start]++;
            if(end+1<=N){
            a[end+1]--;
            }
        }

        int count = 0;
        sum[0]=a[0];
        for(int i = 1;i<=N;i++){
            sum[i]= sum[i-1]+a[i];
            if(sum[i]==0){
                count++;
            }
        }
        if(a[0]==0){
            count++;
        }
        System.out.println(count);
    }
}