建议降黄
查看原帖
建议降黄
977904
Zhong_Yixuan楼主2024/12/26 12:31

平衡树确实值得一道绿,但这题完全不需要使用平衡树

问题在于:

  • 它只贴了个模拟的标签
  • 它也不是细节繁多,像P7075这样的大模拟
  • 它完全不需要考虑优化, q104q\le 10^4 ,可以使用 O(n2)O(n^2) 的时间复杂度通过。对于这题,以 O(n2)O(n^2) 的时间复杂度写出一个暴力来,我想至少对于有能力刷绿题的人有首就行吧?

对于这题,我使用 vector 通过本题,每个点运行时间在 70ms 以下

通过记录

在如上代码中,我使用了 lower_bound 函数,仅仅是因为懒得写 O(n2)O(n^2) 的暴力,虽然最坏情况下确实是 O(n2)O(n^2) (见 op==5 暴力插入)

这份代码能通过可能是因为数据水,而非正解,那么好

没有优化的代码的通过记录

虽然我仍然使用了 lower_bound 函数,但请见第 16 行,我对于每次操作,都增加了一个刚好执行 q 次的无意义的计算,并关闭了 O2 ,hack 数据运行了 700ms 左右,但仍能通过本题

综上所述,这道题完全没有绿题的难度,除非 q 的范围改动到至少 10510^5 ,否则该题应评黄

2024/12/26 12:31
加载中...