新生培训之 前缀和与差分 ----差分篇

之前文章说过，前缀和可以用来求区间和，差分可以用于高效进行区间修改，它通过维护相邻元素的差值来快速进行区间操作。

这篇我就来说一下差分

我们现在给定一个arr[0,0,0,0,0,0],如果先我要给1,3区间都加上1，那我们是不是要遍历一遍，然后给这些范围都加上1，但差分就是让你在1这个地方加1,4这个地方-1，然后我们进行求前缀和，得到的就变成arr[0,1,1,1,0,0],这就是差分的高效性

但是呢，如果arr[0,1,0,0,0,0]，同样要给1,3区间加1，然后按上面给1位置加1,4位置-1，那我们得到的就是arr[0,2,2,2,1,1],而不是arr[0,2,1,1,0,0]因为初始值有个1，他会污染后面的值，所以这时候我们引入一个diff数组也就是差分数组，来维护

差分数组定义

对于原数组 arr，差分数组 diff 定义为：

diff[0] = arr[0] diff[i] = arr[i] - arr[i-1] (i ≥ 1)

为啥这样写可以呢，我们这时候就要用上之前讲的前缀和了，看我下面写的过程就能看出来了

这个过程看看差不多就懂了，下面我写代码

#include<bits/stdc++.h>
using namespace std;
int diff[10000];
int arr[10000];
int prefix[10000]; 
void change_arr(int l,int r,int c){
	diff[l]+=c;
	diff[r+1]-=c;
}
int main(){
	int n;
	cin>>n;
	//原数组 
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	//得到差分数组 
	for(int i=1;i<=n;i++){
		diff[i]=arr[i]-arr[i-1];
	}
	//修改过程
	int m,l,r,c;//修改次数,l,r修改区间,修改大小
	cin>>m; 
	for(int i=0;i<m;i++){
		 cin>>l>>r>>c;
		 change_arr(l,r,c);
	} 
	for(int i=1;i<=n;i++){
		prefix[i]=prefix[i-1]+diff[i];
	}
	for(int i=1;i<=n;i++){
		cout<<prefix[i]<<' ';
	}
}

这就是基本的差分过程了，下面我们去做点题

练习

P2367 语文成绩

P2367 语文成绩 - 洛谷

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 n，p，代表学生数与增加分数的次数。

第二行有 n 个数，a1​∼an​，代表各个学生的初始成绩。

接下来 p 行，每行有三个数，x，y，z，代表给第 x 个到第 y 个学生每人增加 z 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例

输入 #1复制

3 2
1 1 1
1 2 1
2 3 1

输出 #1复制

2

说明/提示

对于 40% 的数据，有 n≤103。

对于 60% 的数据，有 n≤104。

对于 80% 的数据，有 n≤105。

对于 100% 的数据，有 n≤5×106，p≤n，学生初始成绩 ≤100，z≤100。

思路

这就几乎模板了，我就直接在上面那个代码上面改一下了

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int diff[N];
int arr[N];
int prefix[N]; 
void change_arr(int l,int r,int c){
	diff[l]+=c;
	diff[r+1]-=c;
}
int main(){
	int n,p;
	cin>>n>>p;
	//原数组 
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	//得到差分数组 
	for(int i=1;i<=n;i++){
		diff[i]=arr[i]-arr[i-1];
	}
	//修改过程
	int l,r,c;//修改次数,l,r修改区间,修改大小 
	for(int i=0;i<p;i++){
		 cin>>l>>r>>c;
		 change_arr(l,r,c);
	} 
	for(int i=1;i<=n;i++){
		prefix[i]=prefix[i-1]+diff[i];
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		ans=min(ans,prefix[i]);
	}
	cout<<ans;
}

P11853 [CSP-J2022 山东] 植树节

P11853 [CSP-J2022 山东] 植树节 - 洛谷

题目背景

受疫情影响，山东省取消了 CSP-J 2022 认证活动，并于次年三月重新命题，在省内补办比赛。

题目描述

植树节快要到了，学校要组织志愿者去给树苗浇水。

有一排树苗，编号依次是 0,1,2,…。

现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [ai​,bi​] ，表示第 i 个志愿者将 [ai​,bi​] 这一区间内的每一棵树都浇一次水。

如某个志愿者选择的浇水区间为 [4,9] ，表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。

当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。

请你求出浇水最多的树苗被浇了多少次。

输入格式

第 1 行，一个整数 n ，表示志愿者的人数。

第 2 行到第 n+1 行，每行两个整数 ai​,bi​（i=0,1,2,…n−1），表示志愿者 i 选择的浇水区间。

输出格式

输出 1 行， 1 个整数，表示浇水最多的树苗被浇水的次数。

输入输出样例

输入 #1复制

4
0 2
2 4
1 4
6 7

输出 #1复制

3

输入 #2复制

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

输出 #2复制

4

说明/提示

数据范围

• 对于所有的数据： n≤105；0≤ai​≤bi​≤106。

附件下载

CSP-J2022入门组二轮补赛试题（山东）.pdf1.58MB

思路 :这个也很简单直接看代码就行

#include<iostream>
using namespace std;
int n;
const int N=1e6+10;
int arr[N];
void f(int a,int b){
	arr[a]+=1;
	arr[b+1]-=1;
}
int main(){
	cin>>n;
	int B=0; 
	for(int i=0;i<n;i++){
		int a,b;
		cin>>a>>b;
		f(a,b);
		B=max(B,b);
	}
	for(int i=1;i<=B+1;i++){
		arr[i]=arr[i-1]+arr[i];
	}
	int ans=0;
	for(int i=0;i<=B+1;i++){
		if(arr[i]>ans){
			ans=arr[i];
		}
	}
	cout<<ans;
}

P9094 [PA 2020] Mieszanie kolorów

题目描述

题目译自 PA 2020 Runda 1 Mieszanie kolorów

Byteasar 正准备给栅栏涂漆。他已经准备了 n 罐白色油漆，他把这些油漆排列成一排，从 1 到 n 编号。他想用这些油漆，但他不想把栅栏涂成白色。他委托了调色专家，调色专家有三种颜料：黄色、蓝色和红色。专家进行了 m 次操作，其中第 i 次操作是向编号在 li​ 到 ri​ 之间（包括两端）的所有罐子中加入某种颜料。

油漆的最终颜色取决于被添加到其中的颜料。添加的颜料按照下表和图示进行混合。

Byteasar 想要给栅栏涂成一种颜色。思来想去，他选择了绿色，因为绿色代表了你常会在算法竞赛中看到的 Accepted。他想知道现在有多少罐油漆是绿色的，请帮他数数。

输入格式

第一行两个整数 n,m，分别表示油漆的罐数和专家进行的操作数。

接下来 m 行，每行三个整数 li​,ri​,ki​，表示在第 i 次操作中向编号在 li​ 到 ri​ 之间（包括两端）的罐子中加入颜料。加入的颜料是黄色（ki​=1），蓝色（ki​=2）或红色（ki​=3）中的一种。

输出格式

输出一行一个整数，表示在所有操作之后绿色油漆的罐数。

输入输出样例

输入 #1复制

9 5
2 8 1
4 5 2
6 7 3
5 6 2
1 2 2

输出 #1复制

3

说明/提示

样例 1 解释

操作结束后，这些油漆分别是蓝色、绿色、黄色、绿色、绿色、棕色、橙色、黄色和白色的。因此，只有三罐油漆是绿色。

数据范围

本题采用捆绑测试

对于 100% 的数据，保证 1≤n,m≤106，1≤li​≤ri​≤n，1≤ki​≤3。

思路

这个也没啥讲的，就是弄仨数组，分别是黄蓝红，然后用前缀和弄一下，再最后判断一下哪些范围是绿色就行

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int blue[N],yellow[N],red[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		if(k==1) yellow[l]++,yellow[r+1]--;
		if(k==2) blue[l]++,blue[r+1]--;
		if(k==3) red[l]++,red[r+1]--;
	}
	for(int i=1;i<=n;i++){
		yellow[i]+=yellow[i-1];
		blue[i]+=blue[i-1];
		red[i]+=red[i-1];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(blue[i]&&yellow[i]&&!red[i]) ans++;
	}
	cout<<ans;
}