nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

bzoj2006

链接

https://acm.taifua.com/bzoj/p/2006.html

题意

        给一个长为n的序列，输入一个询问k,l,r,从中选出k个长度介于[l,r]中的不同的区间，最大化 k个子段和 的和，
        n<5e5  20s 

题解

        先想一个暴力算法，我们把所有长度介于[l,r]的子段的和都求出来，放进一个堆，然后取出前k大
        然后来优化它，我们观察取出前k大的方法，是一个一个取出来的，这就说明了，一次只取出了一个，这就是突破点于是我们这样来做，我们对每一种区间按终点分类，显然可能取出来的，一定是以当前终点为终点的所有区间中最大的那一个，那我们就维护数列f[]
        f[i]代表以i为终点的所有可取且未取区间中区间和最大的那一个，于是我们这样来查询，每次取出f数组的最大值，然后更新f数组，如何更新呢？我们再多记录一个信息，记录当前的f[i]是原先所有以i为终点的所有选择中的第几大，假设现在这个是第k大，当我们取出来之后，只要更新f[i]即可，更新可选择的第k+1大
        我们来加速这个过程，发现f可以用堆来维护,用一个三元组: <EndAt,val,kth>分别代表该区间以EndAt为结尾，区间和为val，此区间是所有以EndAt为终点的可选区间的第kth大，此三元祖按照val建堆即可。