一维差分

题目描述

题目在此处查看

题解

import java.util.*;
public class 一维差分 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Integer> diff = new ArrayList<>();
        arr.add(0);
        diff.add(0);
        for (int i=1;i<=n;i++) {
            arr.add(i,sc.nextInt()); // 计算原数组
            diff.add(i,arr.get(i)-arr.get(i-1)); // 计算差分数组
        }

        int l,r,d;
        for(int i=1;i<=m;i++){
            l = sc.nextInt();
            r = sc.nextInt();
            d = sc.nextInt();

            diff.set(l,diff.get(l)+d); // 首加
            if (r + 1 <= n) {
                diff.set(r + 1, diff.get(r + 1) - d);// 尾减
            }
        }

        for(int i=1;i<=n;i++){
            arr.set(i,diff.get(i)+arr.get(i-1));
            System.out.print(arr.get(i)+" ");
        }
    }
}