题解 P1160 【队列安排】
LiRewriter
2017-12-07 16:00:25
嗯...终于找到一道链表模板题，顺便发波题解吧
蒟蒻一直都是用list的orzzzzz
首先，这道题我们看到是对一个数列进行频繁的插入和删除操作，这和链表正好是吻合的。
这里大佬们纷纷用的双向链表...于是想一想也写双向链表好了。
那么就说说其实现细节吧，因为我也纠结了很久。
由于个人喜好问题在下用的是结构体
```cpp
struct node{
int L, R;
}a[100003];
```
来作为链表节点的qwq
先看看删除：
我们把当前节点pos的左边节点a[pos].L的右边节点设置成a[pos.R]，也就是`a[a[pos].L].R = a[pos].R`，对右边节点也同样的处理，即`a[a[pos].R].L = a[pos].L`，这样在遍历这个链表的时候就可以跳过这个节点，最后再将该节点的左、右均设置成-1，就完成了删除操作。
```cpp
inline void del(int x) {
if(a[x].L == -1) return;
a[a[x].L].R = a[x].R;
a[a[x].R].L = a[x].L;
a[x].L = -1;
a[x].R = -1;
}
```
再来看看如何插入节点。
将一个节点i插入pos的左边，
- 将节点i的右边置为pos，即`a[i].R = pos`
- pos的左边节点a[pos].L的右边节点变为当前的i，即`a[a[pos].L].R = i`
- 节点i的左边应该是a[pos].L，即`a[i].L = a[pos].L`
- pos的左边节点修改为i，即`a[pos].L = x`
这样的四步之后就可以实现插入到左边的操作辣！
右边用相反的步骤完成即可。
完整的插入操作：
```cpp
inline void addRight(int x, int pos) { //插入右边
a[x].L = pos;
a[a[pos].R].L = x;
a[x].R = a[pos].R;
a[pos].R = x;
}
inline void addLeft(int x, int pos) { //插入左边
a[x].R = pos;
a[a[pos].L].R = x;
a[x].L = a[pos].L;
a[pos].L = x;
}
```
最后是遍历。一开始我开了个头指针，后来看了题解区的大佬，感觉好厉害w
由于我们的链表是从1开始的，我们不妨将节点0变为一切的开始，也就是将a[0].R=1,a[1].L=0这样的强行插入节点0
显然，在最后的时候i仍然是整个链表的第一个节点，这样还可以避免在插入时遇到链表开头的讨论。
所以遍历输出的代码就是：
```cpp
inline void go() {
int x = a[0].R;
while(1) {
cout<<x<<" ";
if(a[x].R == -1) break;
x = a[x].R;
}
}
```
那么数组模拟双向链表就完成辣！
AC代码：
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int L, R;
}a[100003];
int n, m;
inline void addRight(int x, int pos) { //插入右边
a[x].L = pos;
a[a[pos].R].L = x;
a[x].R = a[pos].R;
a[pos].R = x;
}
inline void addLeft(int x, int pos) { //插入左边
a[x].R = pos;
a[a[pos].L].R = x;
a[x].L = a[pos].L;
a[pos].L = x;
}
inline void del(int x) {
if(a[x].L == -1) return;
a[a[x].L].R = a[x].R;
a[a[x].R].L = a[x].L;
a[x].L = -1;
a[x].R = -1;
}
inline void go() {
int x = a[0].R;
while(1) {
cout<<x<<" ";
if(a[x].R == -1) break;
x = a[x].R;
}
}
inline void init() {
for(int i = 1; i <= n; ++i) a[i].L = a[i].R = -1;
a[1].R = -1; a[1].L = 0; a[0].R = 1;
}
int main() {
scanf("%d", &n);
int cmd1, cmd2;
init();
for(int i = 2; i <= n; ++i) {
scanf("%d %d", &cmd1, &cmd2);
if(!cmd2) addLeft(i, cmd1);
else addRight(i, cmd1);
}
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d", &cmd1);
del(cmd1);
}
go();
return 0;
}
```