BZOJ-3267. KC采花

这题是 bzoj-3267 上的题目,原题大概是给一列数,要求支持操作:

  • 修改某个数的值
  • 读入 l、r、k,询问在 [l,r] 内选不相交的不超过 k 个子段,最大的和是多少

然后序列的长度和操作的次数大约都在 10^5 级别的

首先可能会想到 k = 1 的情况,也就是用线段树维护,记录某个区间靠右边的最大值,靠左边的最大值以及答案和区间和,这样的话才可以有足够的信息在线段树中合并两个区间

具体的做法是这样的

对于两个区间,它们合并之后的新区间靠左边的最大值有两种可能,一是原先左边的区间靠左的最大值,二是原先左边的区间的和加上右边区间靠左边的最大值,另外两个部分也是相同的,这样的话一次询问是 \Theta(\log n)

那么,回到原题之后,要求选择 k 个不相交的子段,也会想到用线段树直接维护 k 个这样的东西然后 \Theta(k^2\log n) 维护,但是这题肯定是过不了的

但是,看到这题选出一个最大子区间,会想到一种最长路的做法,也就是建立一个源、一个汇,源向所有点连边权为 0 的边,所有点向汇连边权为自身边权的边,然后每个点向右边的一个点连一条自身边权的边,最后源向汇连一条边权为 0 的边(不取任何区间的时候),然后跑最长路

这样变成 k 个区间的时候改成费用流就可以做了,可是这样做跑得会比暴力还慢

考虑这都有什么操作,一个是增广,一次增广也就是找一段最大的子段,然后是要支持退流,也就等于把找到的最大子段整段权值变为相反数,这样的话前一个操作刚刚的线段树已经有了,至于后面一个操作,因为是线段树,可以直接加上区间取相反数的支持,然后这题复杂度就变为 \Theta(km\log n)

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/12/bzoj-3267

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.