P1160 队列安排——题解

思路

插入和删除都需要快速修改相邻关系，因此使用数组模拟双向链表：

• left[i]：$i$ 左边同学的编号，没有则为 $0$；
• right[i]：$i$ 右边同学的编号，没有则为 $0$；
• head：当前最左边同学；
• removed[i]：$i$ 是否已删除。

插到 k 左边

把新同学 i 接在 left[k] 与 k 之间，并在必要时更新 head。

插到 k 右边

把新同学 i 接在 k 与 right[k] 之间。

删除 x

若尚未删除，就让 x 左边的人直接连接到 x 右边的人；若删除的是队首，还要更新 head。

最后从 head 开始沿 right 数组向右输出即可。

复杂度

每次插入和删除都是 $O(1)$，最终遍历为 $O(N)$，总时间复杂度 $O(N+M)$，空间复杂度 $O(N)$。

参考代码

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

const int N = 100005;
int leftNode[N], rightNode[N];
bool removed[N];

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

    int n;
    cin >> n;
    int head = 1;

    for (int i = 2; i <= n; i++) {
        int k, p;
        cin >> k >> p;
        if (p == 0) {
            leftNode[i] = leftNode[k];
            rightNode[i] = k;
            if (leftNode[k] != 0)
                rightNode[leftNode[k]] = i;
            else
                head = i;
            leftNode[k] = i;
        } else {
            rightNode[i] = rightNode[k];
            leftNode[i] = k;
            if (rightNode[k] != 0)
                leftNode[rightNode[k]] = i;
            rightNode[k] = i;
        }
    }

    int m;
    cin >> m;
    while (m--) {
        int x;
        cin >> x;
        if (removed[x]) continue;
        removed[x] = true;

        if (leftNode[x] != 0)
            rightNode[leftNode[x]] = rightNode[x];
        else
            head = rightNode[x];

        if (rightNode[x] != 0)
            leftNode[rightNode[x]] = leftNode[x];
    }

    bool first = true;
    for (int x = head; x != 0; x = rightNode[x]) {
        if (!first) cout << ' ';
        cout << x;
        first = false;
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; const int N=100005; int leftNode[N],rightNode[N]; bool removed[N]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int head=1; for(int i=2;i<=n;i++){ int k,p; cin>>k>>p; if(p==0){ leftNode[i]=leftNode[k]; rightNode[i]=k; if(leftNode[k]) rightNode[leftNode[k]]=i; else head=i; leftNode[k]=i; }else{ rightNode[i]=rightNode[k]; leftNode[i]=k; if(rightNode[k]) leftNode[rightNode[k]]=i; rightNode[k]=i; } } int m; cin>>m; while(m--){ int x; cin>>x; if(removed[x]) continue; removed[x]=true; if(leftNode[x]) rightNode[leftNode[x]]=rightNode[x]; else head=rightNode[x]; if(rightNode[x]) leftNode[rightNode[x]]=leftNode[x]; } bool first=true; for(int x=head;x;x=rightNode[x]){ if(!first) cout<<' '; cout<<x; first=false; } cout<<'\n'; return 0; }