1 条题解

  • 1
    @ 2026-11-4 14:58:51

    注意到这个题可以带修莫队(划掉)。但是基于莫队的思考可以给我们带来非常重要的性质。

    考虑如果只有一个区间怎么做,显然的想法是先排序,注意到最终答案三个数一定相邻。不妨设 a<b<ca < b < c 满足 a+b>ca+b>c 。若存在 d∈(b,c)d \in (b,c) 则 b,c,d 也合法且更优。

    所以朴素的做法是暴力排序推窗口。

    这时候发现可以用线段树套一个值域结构随便做做,但是太麻烦了。

    可以考虑性质,注意到如果一组不合法意味着 a+b<=ca+b<=c 也就是说 aa 最大为 cc 的一半。你会发现如果不合法的话值域衰减非常快有感觉吗。(类似势能线段树)。然后对每个区间维护最大的50个数暴力跑跑就过了说是。

[2026济南登峰营] D2 P3 三角木棍(sticks) - 文件读写

信息

ID
968
时间
1500ms
内存
256MiB
难度
9
标签
(无)
递交数
76
已通过
4
上传者