【模板】双向链表

Luogu
IDLGB4324
Time2000ms
Memory512MB
DifficultyP3
链表模板题
给出 $N$ 个结点,编号依次为 $1 \dots N$,初始按编号从小到大排列成一条双向链表。 接下来有 $M$ 条指令,请按要求对链表进行修改。所有操作均保证合法。 | 指令 | 含义 | |:------:|:------:| | $1\ x\ y$ | 将结点 $x$ 插入到 $y$ 的左侧(若 $x = y$ 则忽略本条指令)。 | | $2\ x\ y$ | 将结点 $x$ 插入到 $y$ 的右侧(若 $x = y$ 则忽略本条指令)。 | | $3\ x$ | 删除结点 $x$;若 $x$ 已被删除则忽略本条指令。 | 操作结束后,请按从左到右的顺序输出当前链表中所有结点的编号。 ## Input 第一行输入两个正整数 $N,M$,表示链表初始的结点数和操作指令数。 接下来 $M$ 行,每行一条指令,如题意所述。 ## Output 输出一行,即:操作结束后,按从左到右的顺序输出当前链表中所有结点的编号。如果链表不存在结点,输出 `Empty!`。 [samples] ## Note ### 样例解释 - 初始时,链表为:$1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$; - 第一次操作,将 $2$ 插入到 $3$ 左侧。由于初始时已经符合 $2$ 在 $3$ 左侧,所以链表还是:$1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$; - 第二次操作,将 $4$ 插入到 $5$ 的右侧,链表为:$1\ 2\ 3\ 5\ 4\ 6\ 7\ 8\ 9\ 10$; - 第三次操作,删除结点 $2$,链表为:$1\ 3\ 5\ 4\ 6\ 7\ 8\ 9\ 10$; - 第四次操作,将 $9$ 插入到 $4$ 的左侧,链表为:$1\ 3\ 5\ 9\ 4\ 6\ 7\ 8\ 10$; - 第五次操作,将 $7$ 插入到 $8$ 的右侧,链表为:$1\ 3\ 5\ 9\ 4\ 6\ 8\ 7\ 10$; - 第六次操作,删除结点 $4$,链表为:$1\ 3\ 5\ 9\ 6\ 8\ 7\ 10$; - 第七次操作,删除结点 $10$,链表为:$1\ 3\ 5\ 9\ 6\ 8\ 7$; ### 数据范围 - 对于 $30\%$ 的数据,$1\leq N,M\leq 10$; - 对于 $60\%$ 的数据,$1\leq N,M\leq 3000$; - 对于所有数据,$1\leq N,M\leq 5\times 10^5$;
Samples
Input #1
10 7
1 2 3
2 4 5
3 2
1 9 4
2 7 8
3 4
3 10
Output #1
1 3 5 9 6 8 7
API Response (JSON)
{
  "problem": {
    "name": "【模板】双向链表",
    "description": {
      "content": "给出 $N$ 个结点,编号依次为 $1 \\dots N$,初始按编号从小到大排列成一条双向链表。  接下来有 $M$ 条指令,请按要求对链表进行修改。所有操作均保证合法。   | 指令 | 含义 | |:------:|:------:| | $1\\ x\\ y$ | 将结点 $x$ 插入到 $y$ 的左侧(若 $x = y$ 则忽略本条指令)。 | | $2\\ x\\ y$ | 将结点 $x$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4324"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出 $N$ 个结点,编号依次为 $1 \\dots N$,初始按编号从小到大排列成一条双向链表。 \n\n接下来有 $M$ 条指令,请按要求对链表进行修改。所有操作均保证合法。  \n\n| 指令 | 含义 |\n|:------:|:------:|\n| $1\\ x\\ y$ | 将结点 $x$ 插入到 $y$ 的左侧(若 $x = y$ 则忽略本条指令)。 |\n| $2\\ x\\ y$ | 将结点 $x$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments