y_kx_b @ 2023-03-22 10:22:03
rt，使用了早年自己想出来的 sb 离散化（std::set + std::map），然后发现后一半点全 T 了还都 1.2s（开了 O2 后 700ms 左右）
思路：用 set 去重 + 排序，然后用 map 从原来的值映射到现在的离散化值
应该就用了大概
算了一下不算常数的话操作数大概是
T 50pts 代码
by y_kx_b @ 2023-03-22 10:22:56
违规紫衫
by BFSDFS123 @ 2023-03-22 11:18:02
@y_kx_b 首先膜拜您/bx
但是为什么要用 set 和 map 离散化啊（，可以直接 map 离散化（毕竟 map 是会自动排序的）
by BFSDFS123 @ 2023-03-22 11:30:39
@y_kx_b 试了一下自己的 map 离散化也是 TLE 了，应该 STL 离散化常数比较大。
当然 O2 开了也是过了，应该就是 STL 的问题。。。。。。
code
by ud2_ @ 2023-03-22 11:33:52
用平衡树排序是这样的。换成 sort 跑得飞快。
by reveal @ 2023-03-22 11:34:17
在没有 O2 的前提下讨论 STL 的效率是无意义的
by ud2_ @ 2023-03-22 11:36:04
@reveal 虽然给出的链接中没有 -O2，但帖子中有对 -O2 下效率的描述。
by reveal @ 2023-03-22 11:40:29
@ud2_ 我的意思就是没开 O2 的 STL 没过就不必放上来了。
实际上
by ud2_ @ 2023-03-22 11:52:45
@reveal 这确实。
在评测机上测试，有 ~20% 的时间花在动态内存分配上。如果“差不多这个速度”的手写平衡树使用静态内存池，那么这反而证明标准库常数小。
by y_kx_b @ 2023-03-22 11:57:53
有 ~20% 的时间花在动态内存分配上。
/bx/bx/bx
by Chancylaser @ 2023-03-22 12:07:01
不开O2不要相信STL，用STL的情况下可以把总体时间复杂度先乘个log（，然后再决定是否使用