关于此题数据和题解

P3806 【模板】点分治 1

Froggy @ 2020-02-08 16:59:50

  1. 最后几页题解还有很多 \mathcal{O}(n^2) 的没有撤掉

  2. 很多题解当询问距离为0时会因为没有特判而WA掉,(bzoj1316)

  3. 此题的数据范围珂以加强到 0\leq c,K\leq 10^9 (根本无需开桶,珂以用双指针扫)

希望管理员接着加强数据!^_^

by Froggy @ 2020-02-08 17:00:23

@StudyingFather

by Froggy @ 2020-02-08 17:02:21

@一扶苏一 有无需开桶的做法

by 茅场晶彦 @ 2020-02-08 17:03:44

%%%

by 一扶苏一 @ 2020-02-08 17:05:51

@Froggy 询问距离这个属于数据范围没有标清楚产生的历史遗留问题吧，这属于题面不严谨，大概不应该对这个去卡代码？

加强数据范围的话所有题解都要撤掉，这不是这个题本意想要考察的所以意义不大？

by 一扶苏一 @ 2020-02-08 17:07:35

然后撤题解这个事我没权限（等sf来搞叭

by Froggy @ 2020-02-08 17:22:54

@小粉兔

by panyf @ 2020-02-08 17:39:48

不开桶开一个unordered_set似乎也行

by 一扶苏一 @ 2020-02-08 19:59:59

@Froggy O(n^2) 的题解已经撤了

by Froggy @ 2020-02-08 20:03:52

@AK新手村 好像是的

by exzang @ 2020-02-08 22:46:57

@Froggy

对于第3点有疑问：

双指针法要用排序，是O(n log n)的，而开桶（用map实现）也是O(n log n)的，这样加强好像只能起到卡常作用？

| 下一页