[BZOJ4355]Play with sequence(线段树)

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


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

本文链接地址:[BZOJ4355]Play with sequence(线段树)

Description

维护一个长度为N的序列a,现在有三种操作:
1)给出参数U,V,C,将a[U],a[U+1],...,a[V-1],a[V]都赋值为C。
2)给出参数U,V,C,对于区间[U,V]里的每个数i,将a[i]赋值为max(a[i]+C,0)。
3)给出参数U,V,输出a[U],a[U+1],...,a[V-1],a[V]里值为0的数字个数。

Tag

线段树

解决思路

观察题目给出的数据范围,发现在任意时刻,任意序列中的最小值是非负的,也就是说0若存在一定是序列的最小值。所以题目中较好处理的是1,3两个操作,第一个可以直接标记覆盖,而第三个可以通过维护最小值和最小值出现的次数来实现。
那么关键是第二个操作如何处理。考虑把第二个操作分成两步,先区间加法,再区间取max。区间加法也比较好实现,用区间加标记就好。但要注意区间加标记与区间覆盖标记的操作顺序。当区间覆盖的时候,要清空区间加标记;而若区间加的时候,如果有区间覆盖标记,就直接加到区间覆盖标记上。
所以问题在于区间取max的操作。一个自然的想法就是维护区间最小值,若区间最小值都大于当前要取max的值,那么就不向下修改,否则递归左右分别处理。这样最坏可以达到\(O(nq)\)的复杂度。
吉老师线段树这里,我们得到一种更优的操作,那就是在维护区间最小和区间最小的个数的同时,再维护区间次小。当取max的值小于最小时,不操作;当大于区间最小而小于区间次小时,只修改区间最小;当大于区间次小时,递归处理。这样可以证明复杂度是\(O(nlogn)\)的。

代码

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

本文链接地址:[BZOJ4355]Play with sequence(线段树)


HNCJ OIer