Mobile wallpaper 1Mobile wallpaper 2Mobile wallpaper 3Mobile wallpaper 4Mobile wallpaper 5
288 字
1 分钟
警惕 map 陷阱
2025-07-28
统计加载中...

事情是这样的,今天我被卡常卡傻了,而且很多都是因为 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.

牛客多校1 - L

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

警惕 map 陷阱!!!

警惕 map 陷阱
https://starlab.top/posts/be-aware-of-map/
作者
Star
发布于
2025-07-28
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时