问题描述：（虽然中计了....）

$给定一个长度为$ n $的序列$ a $。$

$再给定 𝑚 m 组操作$

$每次操作给定3个正整数𝑙,𝑟,𝑑$

$表示对 𝑙 ∼ 𝑟​中的所有数增加 𝑑 。$

$最终输出操作结束后的序列 𝑎 。$

$输入格式 第一行输入两个正整数𝑛,𝑚。$ $（ 1 ≤ 𝑛 , 𝑚 ≤ 2 × 10 5 1≤n,m≤2×10 5 ）$ $第二行输入 𝑛 n 个正整数 𝑎 𝑖 （ 1 ≤ 𝑖 ≤ 𝑛 , 1 ≤ 𝑎 𝑖 ≤ 10 4 ）。$

$接下来 𝑚 m 行，$ $ 每行输入 3 3 个正整数 𝑙 , 𝑟 , 𝑑 l,r,d。

$（ 1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛 , − 10 4 ≤ 𝑑 ≤ 10 4 1≤l≤r≤n,−10 4 ≤d≤10 4 ）。

第一眼

暴力！！！

#include<bits/stdc++.h>
using namespace std;
void out(){
	cout<<" ";
}
int main(){
	int n,m;
	cin>>n>>m;
	int a[10005];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		while(m--){
			int l,r,d;
			cin>>l>>r>>d;
			for(int j=l;j<=r;j++){
				a[j]+=d;
			} 
		}
	} 
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
	out();
}

Yeah

喜提WA

等一下

标签

差分....

我想

*****************************

回归正题：

差分代码

(复制的是GAY)

code:

#include<bits/stdc++.h>
using namespace std;
void out(){
	cout<<" ";
}
int main(){
	int n,m;
	cin>>n>>m;
	vector<long long> a(n+2,0);
	vector<long long> d(n+2,0);//差分数组
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
	} 
	for(int i=1;i<=m;i++){
		int l,r,dd;
		cin>>l>>r>>dd;
		d[l]+=dd;
		d[r+1]-=dd;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		cnt+=d[i];
		a[i]+=cnt;
		cout<<a[i]<<" ";
	}
	return 0;
	out();
}

最后，给个视频：

import java.util.*;
import java.io.*;

public class Main{  
  //下面这个是一种更轻量化的输入方法
  //用的内存和时间都更少 可以记一下
  //老大网站上的题解我模仿着写会部分超时
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static int nextInt() throws IOException{
        in.nextToken();
        return (int) in.nval;
    }
    public static void main(String [] args) throws IOException{

        int n =nextInt();
        int m =nextInt();
        long [] a = new long [n+1];
        long [] D = new long [n+2];
        for(int i=1;i<=n;i++){
            a[i]=1l*nextInt();
            D[i]=a[i]-a[i-1];
        }
        for(int i=1;i<=m;i++){
            int l =nextInt();
            int r =nextInt();
            int d =nextInt();
            D[l]+=d;
            D[r+1]-=d;
        }
        //将对差分数组的操作还原成对原数组的操作
        for(int i=1;i<=n;i++){
            D[i]=D[i]+D[i-1];
            System.out.print(D[i]+" ");
        }
    }
}

蓝桥云课AC JAVA代码:

import java.util.*;
import java.util.StringTokenizer;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		int n=in.nextInt();
		int m=in.nextInt();
		int[] arr=new int[n+10];//原始数组
		int[] b=new int[n+10];//差分数组
		//数据读入
		for(int i=1;i<=n;i++){
			arr[i]=in.nextInt();
			b[i]=arr[i]-arr[i-1];
		}

		while(m-->0){
			int l=in.nextInt();
			int r=in.nextInt();
			int d=in.nextInt();
			b[l]+=d;
			b[r+1]-=d;
		}
		
		//还原数组
		for(int i=1;i<=n;i++){
			arr[i]=arr[i-1]+b[i];
			out.print(arr[i]+" ");
		}
         out.close();
	}
	
	

	static FastReader in=new FastReader();
	static PrintWriter out=new PrintWriter(System.out);
	static class FastReader{
		static BufferedReader br;
		static StringTokenizer st;
		FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			String str="";
			while(st==null||!st.hasMoreElements()) {
				try {
					str=br.readLine();
				}catch(IOException e) {
					throw new RuntimeException(e);
				}
				st=new StringTokenizer(str);
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
}