【BZOJ4458】GTY的OJ


题面

Description

身为IOI金牌的gtyzs有自己的一个OJ,名曰GOJ。GOJ上的题目可谓是高质量而又经典,他在他的OJ里面定义了一个树形的分类目录,且两个相同级别的目录是不会重叠的。比如图论的大目录下可能分为最短路,最小生成树,网络流等低一级的分类目录,这些目录下可能还有更低一级的目录,以此类推。现在gtyzs接到了一个任务,要他为SDTSC出题。他准备在自己的OJ题库中找出M道题作为SDTSC的试题,而他深知SDTSC的童鞋们个个都是神犇,所以gtyzs认为自己出的这M道题中,每道题都应该属于不少于L种分类目录;可他又怕自己的题没有人会做,所以每道题也应该属于不超过R种分类目录,并且这些分类目录应该是连续的,不能出现断层。对了,最重要的是,不存在一道题,它属于两个分类目录且这两个目录不是包含关系。(比如不存在一道题它既是一道DP题,又是一道网络流题)gtyzs怕被骂,所以他希望不存在任意的一对题目(u,v),使得u所属的分类目录与v完全相同。举例来说,gtyzs不能出两道同样的都是动态规划,背包的题,但是却可以出一道属于动态规划,背包和01背包的题和一道属于背包,01背包的题,当然也可以出一个属于图论的题和一个属于数论的题。(注意:一道题所属的分类目录不一定从根开始,如加粗部分所示)
为了让自己的题目变得更加靠谱,他给每一个分类目录都定了一个靠谱值ai,这个值可正可负。一道题的靠谱度为其从属的分类目录靠谱值的加和。我们假设动态规划的靠谱值为10,插头DP的靠谱值为-5,则一道动态规划插头DP的题的靠谱值就是5。gtyzs希望自己出的这M道题,在满足上述前提条件下,靠谱度总和最大。gtyzs当然会做啦,于是你就看到了这个题。

Input

输入的第一行是一个正整数N,代表分类目录的总数。
接下来的一行,共N个正整数,第i个正整数为fi,表示分类目录i被fi所包含。保证一个分类目录只会被一个分类目录所包含,且包含关系不存在环。特别的,fi=0表示它是根节点,我们保证这样的点只存在一个。
接下来的一行,共N个整数,第i个数表示ai。
最后一行,三个正整数M,L,R。
对于100%的数据,1≤N≤500,000,1≤M≤500,000,|ai|≤2,000。保证输入数据有解。
为了方便,所有的测试数据中都有f1=0,且对于任意的i∈[2,N],有fi<i。

Output

一行一个整数,表示最大的靠谱度。

Sample Input

7

0 1 1 2 2 3 3

2 3 4 1 2 3 4

3 3 3

Sample Output

26


简化版本

这题的简化版本:https://www.lydsy.com/JudgeOnline/problem.php?id=2006

我们可以从最大的开始枚举\(k\)个可行区间。

我们用五个信息来维护区间\((x,l,r,q,v)\),\(x\)表示区间右端点,\(l\)表示区间最左边可以到的位置,\(r\)表示区间最右边可以到的位置,\(q\)表示最大区间和在的左边界坐标,\(v\)表示这个可行范围内的最大区间和。

我们先枚举所有的右边界,直接扔到优先队列里维护\(v\)即可。

对于当前取出的区间,我们可以把它分裂成两个区间\((x,l,q-1,q_1,v_1)\),\((x,q+1,r,q_2,v_2)\),即区间位置\(q\)以后的区间,\(q_1,1_2,v_1,v_2\)需要重新计算。


分析

作为上边的加强版,我们只要从叶子结点开始统计\(min\)信息和\(fa\)信息,然后把所有结点作为最底层结点,向上维护,类似于链的形式,维护一个五元的组合。

noi的钢琴那题,贪图方便,上面那份代码时间复杂度是\(O(n\times log^2_2m)\),然后这题就被卡了。

在维护st表的时候,新开一个数组\(ANS\)表示当前位置向上对应的长度,然后不再用二分去探查位置,直接可以得到。

 

You may also like

【BZOJ3545】Peaks

【BZOJ3732】Network

LEAVE A COMMENT

Statistics

  • 0
  • 2,011

Categories

Archive