图片来源
288 字
1 分钟
警惕 map 陷阱
事情是这样的,今天我被卡常卡傻了,而且很多都是因为 map。
比如离散化,可以这样写
map<LL, int> mp;for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); mp[a[i]];}int m = 0;for (auto &[_, val] : mp) val = ++m;...printf("%lld 的下标是 %d\n", val, mp[val]);也可以这样写
vector<LL> values;int m = 0;for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); values.emplace_back(a[i]);}sort(values.begin(), values.end());int m = unique(values.begin(), values.end()) - values.begin();...printf("%lld 的下标是 %d\n", val, lower_bound(values.begin(), values.begin() + m, val) - values.begin() + 1);第一种做法虽然看着简洁,但是实际上非常的慢!!!
以今天早上刚被卡的上海月赛为例,换到 map 之后 990 → 180,提升巨大。


再看牛客多校第一场的 L 题,一个 log 的权值线段树因为用 map 差 47ms 喜提 TLE,比没用 map 多一个 log 的树状数组还慢了 300ms.

类似的事故之前还发生过很多起,写离散化的时候一定要警惕 map 陷阱,能不用就不用😭😭😭
警惕 map 陷阱!!!
部分信息可能已经过时







