本题数据已加强

P1440 求m区间内的最小值

yummy @ 2024-08-30 14:22:24

之前有同学反馈声称 O(nm) 算法通过了此题——“只要如果 i 对应的 min 不等于 a_{i-m}，那么 i+1 的 min 就等于 i 对应的 min”。

所以我猜测原来的出题人数据是随机生成的，而仅仅通过开大数据范围来完成卡常，是一种不负责任的行为。希望之后的出题人能够仔细思考，使用构造数据区分不同算法。

by qinshi0308 @ 2024-08-30 14:30:33

等下，本题正解是单调队列，我用了线段树

by I_Love_DS @ 2024-08-30 14:31:49

以后不能随机生成数据了呜呜

by I_Love_DS @ 2024-08-30 14:32:17

能否卡掉 O(n\log n) 的 st 表

by 奈芙蓮 @ 2024-08-30 14:32:35

by T_TLucas_Yin @ 2024-08-30 14:32:49

by AKPC @ 2024-08-30 14:38:07

不是这也要卡？？

by lucasincyber @ 2024-08-30 15:04:19

by OutsideR_ @ 2024-08-30 15:04:33

qpzc

by zjj2024 @ 2024-08-30 15:26:24

前情

by Xuancheng_Mao @ 2024-08-30 15:42:48