题号 NC20177
名称 等差数列
来源 [JSOI2009]
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

3月2日的每日一题里出现了线段树维护区间加等差数列的问题，这个题则更进一步——还需要回答区间最少能分成几个等差数列的询问，也就是说关注的重点为：涉及到两个子区间合并起来的时候，怎么把等差数列的个数维护出来？
如果左区间的最右边有一段长度不为1的等差数列，右区间的最左边有一段长度不为1的等差数列，那么判断他们两个公差是不是相等且能不能接起来即可。如果有一边是孤零零的一个数呢（比如左区间最后一个数和前面的不是等差数列），那么和另外一边合并时也只需要看能不能接上，如果两边都是一个孤零零的数，那么他俩则肯定可以两个一组成为一个等差数列。
所以我们需要维护：
这个区间由多少个等差数列组成
这个区间的左右两端各自有没有零散的数字（有同学也表示为区间去掉左/右/左+右端点的时候的等差数列个数，其实都是为了把区间端点位置的数拿去和相邻区间拼合）
这个区间最左边的等差数列公差和第一项是什么
这个区间最右边的等差数列公差和最后一项是什么
维护的细节比较多，需要想清楚再写。
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目3月15日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴