关于 STL 的大常数
  • 板块P1908 逆序对
  • 楼主y_kx_b
  • 当前回复12
  • 已保存回复12
  • 发布时间2023/3/22 10:22
  • 上次更新2023/10/23 20:53:12
查看原帖
关于 STL 的大常数
592895
y_kx_b楼主2023/3/22 10:22

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

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

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

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

T 50pts 代码

2023/3/22 10:22
加载中...