关于 STL 的大常数

P1908 逆序对

y_kx_b @ 2023-03-22 10:22:03

rt,使用了早年自己想出来的 sb 离散化(std::set + std::map),然后发现后一半点全 T 了还都 1.2s(开了 O2 后 700ms 左右)

思路:用 set 去重 + 排序,然后用 map 从原来的值映射到现在的离散化值

应该就用了大概 4n 次 STL O(\log n) 操作,然后跑不过 5\times10^5/kk

算了一下不算常数的话操作数大概是 4\times10^7,可洛谷不是 1s 能跑 5e8 吗,STL 常数真的大如 10 吗/jk

T 50pts 代码


by y_kx_b @ 2023-03-22 14:49:29

@Chancylaser 就是假定 std::set 单次操作复杂度 O(\log^2n)


by Chancylaser @ 2023-03-22 20:42:05

@y_kx_b 可以这么理解


上一页 |