平衡树确实值得一道绿,但这题完全不需要使用平衡树
问题在于:
- 它只贴了个模拟的标签
- 它也不是细节繁多,像P7075这样的大模拟
- 它完全不需要考虑优化, q≤104 ,可以使用 O(n2) 的时间复杂度通过。对于这题,以 O(n2) 的时间复杂度写出一个暴力来,我想至少对于有能力刷绿题的人有首就行吧?
对于这题,我使用 vector 通过本题,每个点运行时间在 70ms 以下
通过记录
在如上代码中,我使用了 lower_bound 函数,仅仅是因为懒得写 O(n2) 的暴力,虽然最坏情况下确实是 O(n2) (见 op==5 暴力插入)
这份代码能通过可能是因为数据水,而非正解,那么好
没有优化的代码的通过记录
虽然我仍然使用了 lower_bound 函数,但请见第 16 行,我对于每次操作,都增加了一个刚好执行 q 次的无意义的计算,并关闭了 O2 ,hack 数据运行了 700ms 左右,但仍能通过本题
综上所述,这道题完全没有绿题的难度,除非 q 的范围改动到至少 105 ,否则该题应评黄