小明的彩灯（差分）

题目描述

题目在此处查看

题解

差分，注意数组需要Long，否则大部分无法通过

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int N = scan.nextInt();
int Q = scan.nextInt();

        ArrayList<Long> arr = new ArrayList<>();
        ArrayList<Long> diffArr = new ArrayList<>();
        arr.add(0L);
        diffArr.add(0L);
        for (int i = 1; i <= N; i++) {
            arr.add(i,scan.nextLong());
            diffArr.add(i,arr.get(i)-arr.get(i-1));
        }
        
        while (Q-- > 0){
            int l = scan.nextInt();
            int r = scan.nextInt();
            int d = scan.nextInt();

            diffArr.set(l,diffArr.get(l)+d); // 首加

            if(r+1 <= N){
                diffArr.set(r+1,diffArr.get(r+1)-d); // 尾减
            }

        }

        for(int i=1;i<=N;i++){
            arr.set(i,arr.get(i-1)+diffArr.get(i));

            // 若彩灯亮度为负数则输出
            long num = arr.get(i);
            num = num > 0 ? num : 0;

            System.out.print(num+" ");
        }
        scan.close();
    }
}