JOI 地牢题解

sub1就是thuwc2018d2t1弱化版
贪心策略就是:考虑下一个费用<当前点的点\(x\),可以用单调栈预处理。
如果当前点不能到达x,则加满。
否则加到恰好能够到达\(x\),然后能量值变为0。
sub2似乎可以倍增,但是和标算关系不大。
sub3考虑在\(n+1\)位置增加一个费用为\(-\inf\)的治疗泉。
判定无解显然可以rmq
考虑扫描线。考虑把l从右往左扫,然后用个数据结构维护所有可能的答案。
考虑线段树。根据套路设线段树的下标\(x\)表示能量上限为\(x\)的答案。
设第一种操作为"否则加到恰好能够到达\(x\),然后能量值变为0。",第二种为"如果当前点不能到达x,则加满"
考虑按照第一种操作划分序列,把划分到的每一部分称为"阶段"。
考虑下一次我们进行的操作。
考虑把原序列按照费用划分成连续的递增/递减段。
分类讨论:
1.当前位置\(x\)在递减段,则我们下一次加能量的位置是\(x+1\)
显然线段树上所有下标的答案增量是相同的。
在线段树上全局加即可。
2.否则,随着角色向后走,设下一个第一个<\(x\)的位置为\(p\)。
显然\(x\)到\(p\)的距离\(d\)随着\(x\)的增加而减少。
一定存在一个分界线\(y\),使得当\(x<y\)使用操作1,否则使用操作2。
线段树上下标\(<d\)的部分的分界线位置\(>x\),这些位置增加的费用都是相同的,可以区间加法维护。
否则分界线位置\(\leq x\),这些位置增加的费用都是相同的,也可以区间加法维护
线段树可以用动态开点/离散化维护。
sub4考虑数据结构常见讨论后缀和。

上一篇:P6881 [JOI 2020 Final] 火事 题解


下一篇:题解「JOI 2020 Final」只不过是长的领带