这一道题显然是一道 RMQ 的题目,用一个三元素组 (o,l,r)表示:左端点为 o,右端点在 l 到 r 的区间内的最大子段,元素组用堆维护。
对于每个和弦的值,用前缀和在 O(1)的时间复杂度求出。
ans累加这个三元组的贡献。由于 t已经被选中,对于这个 o,t已经不能重复选中,但最优解还可能存在于 t左右的两端区间中,所以提取出 (o,l,r)之后,为了避免重复且不丧失其他较优解,我们仍然要把 (o,l,t–1),(o,t+1,r)扔回堆里面去。还要避免重复或错误,即 l=t或 r=t的情况要进行特判。
对于 t的位置,我们直接用 ST 表预处理出即可。
代码:
差不多就是这样了……
4 条评论
XZYQvQ · 2018年12月16日 8:10 下午
emmm 大佬您是哪个学校的呀 QAQ
另外您能加我 QQ 吗?您的那个
649****51
QQ 看起来是您的家长的吧 OrzQiuly · 2018年12月17日 4:50 下午
可以呀,但我不是大佬,我是来自 CSSYZ 信息学集训队的一枚蒟蒻 QAQ
XZYQvQ · 2018年12月17日 6:27 下午
集训队员 Orz %%%%%
Qiuly · 2018年12月17日 4:52 下午
您才是大佬。
您还给我讲过【逛公园】这道题呢 (可是我貌似没打)