关于信息学奥赛中的一些做题思路
观前须知
Sugar_Cube的博客园主页
背景介绍
本文记录了笔者在刷题或比赛中运用到的一些做题思路
可以适当参考
正文
Luogu P2048 超级钢琴
首先显然有 \(\mathcal {O}(n^2)\) 暴力枚举每个子段，然后选择其中前k大的
那么可以发现有贪心策略：
选择k次最大值
那么考虑怎样求最大值
想到可以枚举每个起始位置，想办法计算从该位置开始符合要求的字段最大值
将字段长度符合要求转换为终止位置在区间内
由于连续，记前缀和 \(sum_i\)
则对于一个三元组 \((lx,l,r)\) 表示从 \(lx\) 起始，合法终止位置在 \([l,r]\) 区间内
它的最优答案是 \(max\{sum_t-sum_{lx-1} | t\in [l,r] \}\)
即 \(max\{sum_t | t\in [l,r] \} - sum_{lx-1}\)
求最大的 \(sum_t\) 不就是一个RMQ问题吗
注意到，一个起始位置算完后，仍然有别的终止位置可以使用
则分裂原三元组为 \((lx,l,t-1)\) 与 \((lx,t+1,r)\)
并将新的三元组放到堆中继续维护最大值
细节：
为了计算 \(t\) 要在st表中维护最大值对应的下标
注意判新的三元组的合法性
一句话思路：
暴力->贪心->求最大值->计算子段和->RMQ->分裂三元组用堆维护