CF 2600,但这个理由不充分,毕竟CF DS评分偏高。
我主要是尝试了两种做法:
-
根号重构
能够做到 O(n35),但是显而意见的过不去。
-
平衡树维护 DP
设 fi,j 表示第 i 天温度为 j 第一天温度的取值范围,可以用平衡树维护。平衡树上维护的是一些不交单调区间,要求能够支持一个区间劈开,这个比较难写。
这时候是在没辙了,问了一下同学,同学说 设 fi,j 表示第 1 天温度为 j 第 i 天温度的取值范围,这下才会做,用动态开点线段树维护。
动态开点板子是紫:https://www.luogu.com.cn/problem/CF817F,但是其实这不重要
本题还加上了意识到第一天的初始温度以及今天的温度区间不交且递增,还要想到合理的转化使其能够用动态开点线段树维护,感觉其实难度有紫了。