[蓝桥杯][算法提高VIP]分苹果

题目

题目链接

题解

差分。

差分和前缀和是相辅相成的。一般用到差分就要用前缀和。

前缀和应该都知道，就不多说了。

差分就是相邻两个数后面减去前面，dif[i] = a[i] - a[i-1]，i从1开始，dif[0]一般用于存初始值，比如初始a[i]都为3，那么dif[0] = 3，要是并非全都一样，那初始值就不好使了。

也就是说差分数组存的是两个数的差值，根据差值，我们可以计算出每一个数，比如知道dif[0]即初值，和dif[1]即a[1]-a[0]，也可以理解为第1项比第0项大了多少，而第0项的值是保存在dif[0]中的，那么dif[0] + dif[1]就是第1项的值，即dif[0] + dif[1] = a[1]；同理dif[0] + dif[1] + dif[2] = a[1] + dif[2]，即第1项的值加上第2项与第1项的差值，得到的就是第2项的值，即a[2]；以此类推，第i项的值a[i]就是差分数组前i项的和，即前缀和。

差分数组的原理和实现方式讲完了，该讲一下如何使用了。 差分数组适用于“对数组的连续一段进行+或-相同的数操作”的情景。 当需要对a[l~r]进行加c的操作时，我们只需要，对区间的两端位置的数组元素进行操作，即a[l]+=c，a[r+1]-=c，可以理解为第l项比第l-1项在原有的基础上又大了c，而第r+1项比第r项大的少了，这说明a[l]和a[r]变大了，但是仅仅是他们俩变大了吗，因为通过前缀和可以求出每一项的值，因此l~r区间的值都变大了，由于a[r+1]-=c，r项之后的不会变化。

会的同学会发现这就是个模板题。。。。

代码

#include
using namespace std;
const int N = 1e5+10;

int n, m, l, r, c, a[N], sum;

int main()
{
	cin>>n>>m;
	for(int i = 1;i >l>>r>>c; 
		a[l]+=c, a[r+1]-=c;	
	}
	for(int i = 1;i