分类： 数据结构

发布于

[线段树][字符串hash][假算法] bzoj2124 等差子序列

这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F

cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。

正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。

继续阅读“[线段树][字符串hash][假算法] bzoj2124 等差子序列”

发布于

[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array

http://codeforces.com/contest/1042/problem/D

嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。

vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。 继续阅读“[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array”

发布于

[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together

题目：http://codeforces.com/problemset/problem/1030/F

这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！

然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。

对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)

把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)

展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。

wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 继续阅读“[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together”

发布于

[线段树][扫描线][面积交] HDU 1255

这次写了这个题目之后我发现之前对面积并的那个cal计数的意义还是理解还是有一点偏差：这个东西表示的是当前节点对应的线段整体覆盖的情况。为0时没有被全覆盖（注意不等于没有被覆盖），为1时被全覆盖了1次（意为min(l,r)==1，不代表不大于1)，为k时表示min(l,r)==k。而且对应的只是一个节点对应的整个线段，跟只表示当前整段线段的状况，儿子是什么样不知道。。。

这个题也貌似有很多种方法，我参考了一位前辈的博客之后用了Len1表示全覆盖次数≥1的长度，Len2表示全覆盖次数≥2的长度，当然全部都是针对当前节点。Len1的维护方法和面积并的方法完全一样。然后Len2维护的时候就是，如果cnt[o]大于等于2，那么说明当前节点被全覆盖了两次，直接Len2=Len1，如果为1，说明当前节点被全覆盖了一次，那么只需要加上子节点中被全覆盖了一次的Len1就可以了（这样相当于在双亲节点里覆盖了两次），如果是叶子节点，没有孩子，那就直接是0，如果cnt为0，那就只有孩子里面的被全覆盖了两次之和才能更新当前点了。
这里还有一个需要注意的是，如果cnt为0，那么要么说明，当前节点从来没有被计算过，要么说明只计算过子节点，所以不会出现错误。
继续阅读“[线段树][扫描线][面积交] HDU 1255”

发布于

[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形

比赛时候万人题，呵呵，没想到转换成histogram来做。貌似转化之后暴力都可以，n*m^2，气哭aaaaaaaaaaaaaaaaaaa

然后自己写了单调栈n*m做法，需要注意的是要同时保存一段height的左端点和右端点，因为要求数量的话，用单调栈只保存一个的话会忽略掉中间的“高点”，只保存一个端点就无法正确计算了。。。emm，代码写得时候脑子也很乱，还是需要多写写单调数据结构的题目。

继续阅读“[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形”

发布于

[比赛][线段树][模拟] 2018南京网络赛 G Lpl and Energy-saving Lamps

这题真的好鸡儿简单。。。差不多是除了第一题之外最简单的了。比赛的时候没看这个，iSika说很难就没做，唉

题意：给n个房间，当还有房间的灯没有被换成节能灯的时候每个月开始会买入m个节能灯，然后从左向右在列表中找小于m的房间换掉，如果当月的节能灯没有用完的话可以留给下个月。然后给q个询问问d第几个月结束的时候有多少个房间被换成了节能灯，以及手里剩下了多少节能灯。

解法：用value表示当前总共有多少个节能灯，把q个询问都读进来排序后从小到大操作（就是从第一个月开始模拟）。每次都找列表中<=value的最左边的值，找的方法是用线段树维护区间minv 信息，如果左子树minv<=value的话就向左走否则向右，如果小于minv[1]就不找，直接把当月的算出来。找到的话，令找到的房间的计数器+1，value-=找到的值，然后更新线段树这个点的minv为INF就行了。由于每个节点最多被修改一次，修改一次的代价为logn，所以总共的代价为qlogn，case closed！ 继续阅读“[比赛][线段树][模拟] 2018南京网络赛 G Lpl and Energy-saving Lamps”

发布于

[线段树][扫描线][面积并] HDU1542 Atlantis

扫描线第一题，求矩形面积的并。思路很好理解，但是实现上有很多的问题。

1 维护的变量ala[o]代表含义是“当前节点对应区间全覆盖的点数”，举个例子来说，现在的区间各个节点的值如果是2 3 3 3 5 5 2，那么ala就应该是2。这个变量这么做的好处就是，当ala不为0的时候一定可以直接把整个区间的Len算出来：就是x[r]-x[l]，当他为0的时候说明中间有的点为0，那么我们再考虑左右儿子Len之和。这个东西注意是不要pushdown的，如果pushdown了反而会使得问题变得复杂，因为如果你只是往里面+1也要pushdown的话，那等于原来的可以直接得到的Len现在反而要往下走才可以得到。那么不pushdown会不会出现重复加的情况？也不会，因为这个问题里所有的形状都是矩形，有一个上下边使得ala[o]+1，则一定有另外一个边使得他-1，而这中间的呢？因为肯定这一条线段都是还是属于计算范围的，所以也没有多加，一定是对的，这个特点很重要，今早赖床的时候想了下才明白其中的奥妙所在。。。。

引用一位dalao的话描述一下

这里的区间覆盖不需要打懒惰标记。为什么呢？因为很显然，每个下边都有与之对应的上边，它显然不会被比它的长度小的上边给清除。而如果有比它长的上边，也一定有和那个上边对应的下边还存在。所以用那个上边清除下边的时候，一定会先递归到那个更长的下边，还没有递归到它就停止递归了。所以每个上下边是一一对应的，无需下传标记等。

2 这个线段树不是[l,r]，而是[l,r)，因为我们这里离散化之后，如果按照闭区间来算，那[mid,mid+1]这一段就不能被计算到了，所以要用左闭右开，这样的话对应的一开始的区间右边要+1，而这样又会有问题就是原来的整个线段，也就是o==1时候的线段，以及所有的右侧端点为整个线段树右端点的线段，他们的右侧怎么处理，这可是个必须要左闭右闭的啊？我这里用的是在xs离散化数组的后面加上一个和xs[cnt1]相等的元素，这样就可以不用特殊判断了。

继续阅读“[线段树][扫描线][面积并] HDU1542 Atlantis”

发布于

[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence

这个题也是看了一晚上，各种题解各种论文各种ppt emmmmmmm

话说发现真的线段树这东西不能看别人的代码，怎么看怎么看不懂，非得自己写一遍才是。感觉市面上常见的线段树也就两种写法，一种是pushdown以及在update预判返回的时候把维护子节点的事情做了，维护只维护当前节点所以又叫pushup，另一种是pushdown和预判都只改变标记，而所有的维护都交给maintain来做，(⊙﹏⊙)我一直写的是后一种，但是这里写前一种貌似比较方便（🌫）因为update在这里兼具了更新和搜索的功能，所以最好是在pushdown的时候就把维护子节点的事情做了。（感觉自己对pushdown标记的理解之前还是不到位啊emmmm还是得写）
继续阅读“[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence”

发布于

[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers

这个题的官方题解简直玄学，根号5取模，然后转化成等比数列，服气。

还好评论区有人给了更简便的做法：广义斐波那契数列。任意两个广义斐波那契数列相加仍然是斐波那契数列，而且只要知道了前两项的和就可以知道任意一项的和和任意一项的开始的前缀和。比如若第一二项为a,b,那么手推几下就可以发现，fab[n]=af[n-2]+bf[n-1]，然后前缀和是fsum[n]=f[n+2]-f[2]（这个也很容易推出来，甚至奇数项偶数项分别的和都能推出来）,然后这时候就很简单了，对于每一个区间只需要保存其左端点处的a，b就可以了，把ab做成lazy tag就可以实现区间修改了。注意这时候pushdown的时候，对于右孩子要计算出来fibab到这个点是多大才可以。一如既往的，add操作需要在maintain里加单节点特判（我也不知道为什么但是已经习惯了）还有一点注意ta一定是+的第一个，tb一定是+的第二个。

准备再用等比数列方法做一遍吧，看看是怎么个操作。。今天写了一下等比数列的操作方法，感觉比原来的方法简单emmm
继续阅读“[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers”

发布于

[线段树][收敛函数][区间修改]

https://cn.vjudge.net/problem/CodeForces-920F

跟上一道HDU的题目很像，也是求快速收敛函数的和，因为有结论n的约数个数期望为sqrt(n)。每次遇到一个数就将其质因数分解然后求约数个数，这里可以开一个1e6的数组把处理过的n存下来，记忆化，就可以省下来很多时间（大概吧呵呵）。另外一个需要注意的点是收敛的终点可能是1也可能是2，我这里的方法是把读入的1全变成2，然后输出的时候减去前缀和差分就行了，因为1是怎么都不会变的，2也是不会变的，这样可以保证正确。

继续阅读“[线段树][收敛函数][区间修改]”