Michael_Bryant的复活

高考结束 虽说Michael_Bryant大学大概率不会学习计算机相关专业 但是Michael_Bryant打算将算法作为自己的业余爱好继续进行下去
所以 Michael_Bryant从今天开始在此博客正式复活 并将带来更多题的题解
至于高考分数 想问的出门左拐
去的大学的话 录取通知书下来以后会有所提及

题目链接

bzoj挂了 爷青结
放luogu的链接吧
传送门

题目大意

luogu不太资瓷复制整个题目 就说一下题目大意吧
题目大意是对一个数列进行两种操作
第一种是对区间加等差数列
第二种是单点询问

题解

这个题如果是区间加相同的数果断线段树
但是我们加的是等差数列 显然不能算出每个点加多少然后再加
所以我们考虑差分
我们对于[L,R]区间进行如下差分数组的操作
1.sum[L]=sum[L]+a1
2.sum[L+1,R]=sum[L+1,R]+d
3.sum[R+1]=sum[R+1]-a1-(R-L)*d

然后我们发现这个查分数组可以用线段树来维护
至于查询的话 a[o]=a[o]+sum[1]+..sum[o]
正确性的话自己算算就可以了
大概描述一下的话就是差分数组记录了首项和许多个公差

代码