1.B3631 单向链表 - 洛谷

我当时读这题目的时候第一反应都点懵   我先把代码给出来

#include<iostream>
using namespace std;

// 数组大小：操作最多1e5次，数值最大1e6
const int N=1e5+10,M=1e6+10;

// 数组模拟单向链表核心变量
int e[N];    // e[i] = 编号为 i 的节点 存储的【数字】
int ne[N];   // ne[i] = 编号为 i 的节点 的【下一个节点编号】
int h;       // 头节点（本题没用上）
int id;      // 当前分配到的节点编号（给新元素开房间用）

int mp[M];   // 最重要！mp[数字] = 这个数字对应的节点编号（房间号）
             // 作用：通过数字快速找到它在数组里的位置

int main(){
    int q;        // q 表示操作次数
    cin>>q;       // 读入操作次数
    
    int op,x,y;   // op：操作类型  x/y：题目中的数字
    
    // 初始化：链表最开始只有一个元素 1
    id++;                    // 分配第一个房间（房间号1）
    e[id] = 1;               // 房间1里存数字 1
    mp[1] = id;              // 记录：数字1 住在 房间1
    
    // 循环执行 q 次操作
    while(q--){
        cin>>op>>x;  // 每次读入：操作类型 + 要操作的数字x
        
        // 操作1：在数字x的后面插入y
        if(op == 1){
            cin>>y;          // 读入要插入的数字y
            id++;            // 给y分配一个新房间（编号自增）
            mp[y] = id;      // 记录：数字y 住在 新房间id
            e[id] = y;       // 把y存进新房间
            
            ne[id] = ne[mp[x]];  // 新节点的下一个 = x原来的下一个
            ne[mp[x]] = id;      // x的下一个 指向 新节点（插入完成）
        }
        
        // 操作2：查询x后面的数字是什么，并输出
        else if(op == 2){
            // ne[mp[x]] → x后面的房间号
            // e[房间号]   → 这个房间里的数字
            cout << e[ne[mp[x]]] << endl;
        }
        
        // 操作3：删除x后面的那个数字
        else{
            // 让x的下一个 直接指向 x的下下个
            // 相当于跳过了x后面的那个数，完成删除
            ne[mp[x]] = ne[ne[mp[x]]];
        }
    }
    return 0;
}

我一开始的痛点是没反应过来给的是x，y是元素不是位置。 

痛点

我当时写插入的时候一直想的都是直接用位置。直接就是pppp

我是在问了ai之后才懂的

🔍 先看你这段代码里的问题

你这段代码里有一个关键错误：

cpp

运行

ne[x] = ne[p];  // ❌ 这里写错了！

这里的 x 是要插入的数字，而 ne[] 只能接收房间号（节点编号），所以这行应该写成：

cpp

运行

ne[id] = ne[p];  // ✅ 正确写法

---

✅ 为什么这段代码 “看起来” 可以用 ne[x]？

其实根本不能用 ne[x]，你现在看到的 ne[x] 是笔误！

我们逐行拆解这段 insert 函数：

cpp

运行

// 在位置 p（房间号）之后插入元素 x（数字）
void insert(int p, int x) {
    id++;          // 开一个新房间，编号是 id
    e[id] = x;     // 新房间里存数字 x
    mp[x] = id;    // 记录：数字 x 住在 id 号房间

    ne[id] = ne[p];// 新房间的下一个 = p 原来的下一个房间
    ne[p] = id;    // p 的下一个 = 新房间
}

• p 是房间号：函数参数里的 p 已经是节点编号了，所以可以直接写 ne[p]
• x 是数字：不能写 ne[x]，必须用 ne[id]，因为 id 才是 x 对应的房间号

---

🧠 核心区别总结

表格

写法	含义	正确 / 错误
ne[p]	p 是房间号，直接访问该房间的下一个	✅ 正确
ne[id]	id 是新房间号，访问新房间的下一个	✅ 正确
ne[x]	x 是数字，不是房间号，访问越界	❌ 错误

---

📌 一句话总结

• 函数参数里的 p 已经是房间号了，所以可以直接 ne[p]
• 新元素 x 对应的房间号是 id，所以必须用 ne[id]，不能用 ne[x]
• 你图里的 ne[x] 是手滑写错，正确应该是 ne[id]

然后在这道题的时候也是一开始用的是ne[x] 

所以才一直不对

我也一直不太懂mp[N]到底是怎么用的 然后我问了ai

我们先规定两件事

1. 数字：就是题目里的 1、99、50、75 这些值
2. 房间号（节点编号）：程序里 id 分配的编号，e[]、ne[] 的下标

---

现在构造一条链表

数字顺序：

1 → 99 → 75 → 50

程序给它们分配的房间号是：

• 数字 1 住在 房间 1
• 数字 99 住在 房间 2
• 数字 75 住在 房间 3
• 数字 50 住在 房间 4

所以数组里是这样：

plaintext

e[1] = 1      房间1 放数字 1
e[2] = 99     房间2 放数字 99
e[3] = 75     房间3 放数字 75
e[4] = 50     房间4 放数字 50

ne[1] = 2     房间1 的下一个是 房间2
ne[2] = 3     房间2 的下一个是 房间3
ne[3] = 4     房间3 的下一个是 房间4
ne[4] = 0     房间4 后面没人

mp[1] = 1     数字1 在房间1
mp[99] = 2    数字99 在房间2
mp[75] = 3    数字75 在房间3
mp[50] = 4    数字50 在房间4

---

现在题目让你查：99 后面是谁？

你错误写法：

cpp

运行

ne[99]   ❌

意思是：去看房间 99 的下一个是谁但我们根本没有房间 99！只有房间 1、2、3、4！

程序直接乱掉、越界、崩溃。

---

正确写法：

第一步：通过数字 99 找房间

cpp

运行

p = mp[99] = 2

第二步：看这个房间的下一个

cpp

运行

ne[p] = ne[2] = 3

第三步：房间 3 里存的数字就是答案

cpp

运行

e[3] = 75

---

一张图总结

plaintext

数字：     1    →    99     →     75     →     50
           ↑           ↑            ↑            ↑
房间：     1          2             3            4

mp[数字] = 房间号
ne[房间号] = 下一个房间号
e[房间号]  = 这个房间里的数字

所以：

• ne 里面只能放房间号
• 不能直接放数字
• 必须先用 mp[x] 把数字转成房间号

---

最关键一句背下来：

**ne [房间号]

e [房间号]

mp [数字] = 房间号 **

你现在彻底懂了吗？