题解

本题训练“已知结点后的插入、查询和删除”。

由于结点值互不相同且不超过 $10^6$，可以使用：

Node* pos[value];

直接保存每个值对应的结点地址，这样能在 $O(1)$ 时间找到 x。

插入

Node* node = new Node{y, pos[x]->next};
pos[x]->next = node;
pos[y] = node;

查询

查看：

pos[x]->next

为空则输出 0。

删除

先保存被删除结点，再让 x 绕过它：

Node* t = pos[x]->next;
pos[x]->next = t->next;
pos[t->data] = nullptr;
delete t;

总时间复杂度 $O(n+q)$。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* pos[1000005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q;
    cin >> n >> q;

    Node* head=nullptr;
    Node* tail=nullptr;

    for (int i=0;i<n;++i) {
        int x; cin >> x;
        Node* node=new Node{x,nullptr};
        pos[x]=node;
        if (!head) head=tail=node;
        else {
            tail->next=node;
            tail=node;
        }
    }

    while (q--) {
        int op,x;
        cin >> op >> x;

        if (op==1) {
            int y; cin >> y;
            Node* node=new Node{y,pos[x]->next};
            pos[x]->next=node;
            pos[y]=node;
        } else if (op==2) {
            if (pos[x]->next) cout << pos[x]->next->data << '\n';
            else cout << 0 << '\n';
        } else {
            Node* t=pos[x]->next;
            if (t) {
                pos[x]->next=t->next;
                pos[t->data]=nullptr;
                delete t;
            }
        }
    }

    while (head) {
        Node* t=head;
        head=head->next;
        delete t;
    }
    return 0;
}