德语不可分前缀,根据学号前缀差大学

北京信息科技大学第十一届程序设计竞赛重现赛-I：andy种树

链接：https://ac.nowcoder.com/acm/contest/940/I
来源：牛客网

题目描述

andy在他的庄园里种了n棵树，排列成一排，标号为1到n。最开始的时候n棵树的高度都是0，也就是种子刚刚被埋下，树还没有长出来。

andy会一种魔法，他每使用一次魔法，就可以让树标号落在连续区间[l, r]里的树的高度增加1。他可以使用q次这种魔法，然后他很好奇，在使用了q次魔法之后，他的所有树的高度分别是多少呢？

输入描述:

第一行输入两个整数n，q。(1<= n, q <= 1e5)

接下来q行，每行输入两个整数l, r(l <= r)，表示andy让标号落在区间[l, r]里的数高度都加1

输出描述:

输出有一行n个整数，每个整数后面有空格。输出末尾没有换行

第i个数表示第i棵树的高度

示例1

输入
10 3
1 3
2 4
3 3

输出

1 2 3 1 0 0 0 0 0 0

说明

andy种了10棵树

第一次使用魔法使得1、2、3棵树的高度增加1,

所有树的高度为

1 1 1 0 0 0 0 0 0 0

第二次使用魔法使得2、3、4棵树的高度增加1，

所有树的高度为

1 2 2 1 0 0 0 0 0 0

第三次使用魔法使得第3棵树的高度增加1

所有树的高度为

1 2 3 1 0 0 0 0 0 0

题解：当然xsdtn的我一开始看到这题就觉得应该可以暴力8，于是一顿猛操作，结果TLE。。。。
赛后看题解时，说巨巨门店们说差分+前缀和，于是就就问了下度娘（还是看的OI巨巨选手的博客，自愧不如），学习了下差分，这里给出链接：
https://www.cnblogs.com/cjoierljl/p/8728110.html
于是后面用前缀和维护下即可，tcl。。。。

代码如下：

/**差分+前缀和*/#include<bits/stdc++.h>using namespace std;int a[100010];int main(){ memset(a,0,sizeof(a)); int n,q; scanf("%d%d",&n,&q); while(q--) { int l,r; scanf("%d%d",&l,&r); a[l]++; a[r+1]--; } for(int i=1;i<=n;i++) { a[i]+=a[i-1]; printf("%d ",a[i]); } return 0;}