差分总结（c++）（例子：Color the ball ）

输入一个长度为 n 的整数序列。

接下来输入 m个操作，每个操作包含三个整数l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

与前缀和不同的是每次是在一个区间内加一个常数，我们如果想构造原数组a的差分的话，应该先把a数组里的数插进b里去，然后再根据他的操作来依次在lr之间插入数。

因为在操作之前我们需要把a也插进去，所以我们在输入a数组之后有一个insert(i,i,a[i])的操作（注意输入下标从1开始）

for(int i=1;i<=n;i++){
		insert(i,i,a[i]);
	}

插入代码是：

void insert(int x,int y,int c){
	b[x]+=c;
	b[y+1]-=c;
}

因为这个b数组只是我们算的差分数组，所以如果想得到原数组的话就对每个i使b[i]+=b[i-1]就可（注意从1到n）

for(int i=1;i<=n;i++)b[i]+=b[i-1];

最后输出b数组就可，完整代码：

#include<iostream>
using namespace std;
int n,m;
int a[100005]={0},b[100005]={0};
void insert(int l,int r,int c){
	b[l]=b[l]+c;
	b[r+1]=b[r+1]-c;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		insert(i,i,a[i]);
	}
		
	while(m--){
		int l,r,c;
		scanf("%d%d%d",&l,&r,&c);
		insert(l,r,c);
	}
	for(int i=1;i<=n;i++)b[i]+=b[i-1] ;
	for(int i=1;i<=n;i++)printf("%d ",b[i]);
	return 0;
}

N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。 当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Sample

典型算差分数组，直接按上面的模板往里套就行，不过每次的常数是1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int b[100005];
void insert(int x,int y,int c){
	b[x]+=c;
	b[y+1]-=c;
}
int main(){
	int n;
	while(cin>>n){
		if(n==0)break;
		memset(b,0,sizeof b);
		for(int i=0;i<n;i++){
			int x,y;
			cin>>x>>y;
			insert(x,y,1);
		}
		for(int i=1;i<=n;i++){
			b[i]+=b[i-1];
		}
		for(int i=1;i<=n;i++){
			if(i!=1)printf(" ");
			printf("%d",b[i]);
		}
		printf("
");
	}
	
	return 0;
}