[SCOI2007]降雨量

这可真是一道毒瘤QAQ

首先要离散化。我用了个map

接着就是毒瘤的分类讨论了:

true:只有当左右端点已知,且左端点大于等于右端点的值,中间年份最大值已知,且小于右端点的值,且年份连续

maybe:

1:左右端点都不知

2:左端点已知,右端点未知,中间最大值小于左端点值

3:右端点已知,左端点未知,中间最大值小于右端点值

4:中间最大值未知,左端点值大于右端点值

5:只有当左右端点已知,且左端点大于等于右端点的值,中间年份最大值已知,且小于右端点的值,但年份不连续

求最大值的话rmq/线段树

最重要是要细心,考虑周全

代码懒得给

原文地址:https://www.cnblogs.com/mimiorz/p/9742639.html