搜狗后端笔试第二场

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int i = 1;
        int result = 0;
        List<Integer[]> lr = new ArrayList<>(M);
        Map<Integer,Integer> finished = new HashMap<>(M);
        while(i<=M){
            Integer[] tmp = new Integer[2];
            tmp[0] = in.nextInt();
            tmp[1] = in.nextInt();
            lr.add(tmp);
            i++;
        }
        //最后一轮修改的值逆着往回倒，已修改过的即为最终值，加入map中，之后不再修改
        for(i = M-1;i>=0;i--){
            int L = lr.get(i)[0];
            int R = lr.get(i)[1];
            for(int j=L;j<=R;j++){
                if(!finished.containsKey(j)){
                    result += (i+1)*j;
                    finished.put(j,0);
                }
            }
        }
        result = result % 100000009;
        System.out.println(result);
    }
}