完，看到题就想写线段树怎么办

P2367 语文成绩

Infinity_Fantasy @ 2023-10-11 20:54:54

RT

之前就是一个算法题，跟这个很像，求区间最值和区间修改的，想都没想打了线段树，结果被出题人卡成60pts

by youdu666 @ 2023-10-11 20:56:52

@AK_CCF 其实你看一下数据范围就可以了。1e6 左右的用树状数组，以下的用线段树，以上的考虑 O(n) 算法

by Infinity_Fantasy @ 2023-10-11 20:57:22

总结为玩原神玩的学数据结构学傻了

by youdu666 @ 2023-10-11 20:58:25

我也玩原神 @AK_CCF

by Infinity_Fantasy @ 2023-10-11 20:59:00

@youdu666 当时那题的出题人说线段树常数大，最多跑 5e5，可我看线段树模板都是 1e6 啊，/yh

by YiX01 @ 2023-10-11 20:59:15

原来你也玩原神？

by youdu666 @ 2023-10-11 21:00:13

@AK_CCF 可是这题是 5e6 啊，可能操作简单的 1e6 确实可以过

by TulipeNoire @ 2023-10-11 21:18:15

线段树顶多给个 2e6 吧。其实 1e6 以上就可以考虑线性做法了。

|