信息
- ID
- 968
- 时间
- 1500ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 76
- 已通过
- 4
- 上传者
注意到这个题可以带修莫队(划掉)。但是基于莫队的思考可以给我们带来非常重要的性质。
考虑如果只有一个区间怎么做,显然的想法是先排序,注意到最终答案三个数一定相邻。不妨设 a<b<c 满足 a+b>c 。若存在 d∈(b,c) 则 b,c,d 也合法且更优。
所以朴素的做法是暴力排序推窗口。
这时候发现可以用线段树套一个值域结构随便做做,但是太麻烦了。
可以考虑性质,注意到如果一组不合法意味着 a+b<=c 也就是说 a 最大为 c 的一半。你会发现如果不合法的话值域衰减非常快有感觉吗。(类似势能线段树)。然后对每个区间维护最大的50个数暴力跑跑就过了说是。
但每次拿取最大然后暂时删掉,从代码难度和时空复杂度上都是更优的
然后注意逗号的运算优先级高于三目运算符