关于空间的疑惑
  • 板块学术版
  • 楼主Dyd本人
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/6/14 10:24
  • 上次更新2023/10/27 23:20:28
查看原帖
关于空间的疑惑
141393
Dyd本人楼主2022/6/14 10:24

rt,蒟蒻在尝试用 Skip List 过普通平衡树加强版(这和本问题无关),打了这样一段代码:

const int N = 1e6 + 5;
namespace SL //Skip List
{
    const int D = 15;
    std::mt19937 rud(114514);
    struct Node
    {
        Node *nx = nullptr, *dw = nullptr;
        int v, si, lvl; 
    } pool[N << 2], *upd[D + 1], *rt; 
    int tot = 0;
	...    
}

万分不幸,它 MLE 了,而且交到未加强版和 loj 都显示它的空间大的一比(约 100200MB100 \sim 200 MB ),这显然不符合理论计算,且应该不是后面代码调用越界的问题,因为我把后面全注释了只留下这段开空间也 MLE 了

于是蒟蒻到处贺,在一番极其痛苦的乱改后,改成了:

const int N = 1e6 + 5;
namespace SL //Skip List
{
    const int D = 15;
    std::mt19937 rud(114514);
    struct Node
    {
        Node *nx = nullptr, *dw = nullptr;
        int v = 0, si = 0, lvl = 0; 
    } pool[N << 2], *upd[D + 1], *rt; 
    int tot = 0;
	...    
}

然后……就过了

为什么啊,我不李姐!求巨佬解惑

2022/6/14 10:24
加载中...