[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)

发布于 2018-04-17  163 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)

Description

[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)

Tag

线段树,差分

解决思路

一般而言,遇到等差数列的问题,通常是转化为差分数组后,相同的数即可组成一个等差数列。
但,等差数列差分后,第一个数是可以与后面的数不一样的,这就不是很好处理。所以,要把它们分开考虑。
具体来说,用线段树维护区间左右端点的值,然后再维护f00,f01,f10,f11分别表示前后端点选or不选时的最小等差数列个数,0代表不选,1代表选。这里的选指的是是否记录进当前区间的答案。
那么合并两个区间的时候,分情况讨论一下求和。
至于修改,考虑差分后的数组,则是两个端点的单点修改和中间区间的区间修改操作。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1558/Luogu4243][JSOI2009]等差数列(线段树,差分)


HNCJ OIer