【洛谷】P1160 队列安排

https://www.luogu.com.cn/problem/P1160

题目描述：
一个学校里老师要将班上 N N N个同学排成一列，同学被编号为 1 ∼ N 1sim N 1∼N，他采取如下的方法：
1、先将 1 1 1号同学安排进队列，这时队列中只有他一个人；
2、 2 − N 2-N 2−N号同学依次入列，编号为 i i i的同学入列方式为：老师指定编号为 i i i的同学站在编号为 1 ∼ ( i − 1 ) 1sim(i-1) 1∼(i−1)中某位同学（即之前已经入列的同学）的左边或右边；
3. 从队列中去掉 M ( M < N ) M(M 在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式：
第 1 1 1行为一个正整数 N N N，表示了有 N N N个同学。
第 2 − N 2-N 2−N行，第 i i i行包含两个整数 k , p k,p k,p，其中 k k k为小于 i i i的正整数， p p p为 0 0 0或者 1 1 1。若 p p p为 0 0 0，则表示将 i i i号同学插入到 k k k号同学的左边， p p p为 1 1 1则表示插入到右边。
第 N + 1 N+1 N+1行为一个正整数 M M M，表示去掉的同学数目。
接下来 M M M行，每行一个正整数 x x x，表示将 x x x号同学从队列中移去，如果 x x x号同学已经不在队列中则忽略这一条指令。

输出格式：
1 1 1行，包含最多 N N N个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。

数据范围：
对于 20 % 20% 20%的数据，有 N ≤ 10 N≤10 N≤10；
对于 40 % 40% 40%的数据，有 N ≤ 1000 N≤1000 N≤1000；
对于 100 % 100% 100%的数据，有 N , M ≤ 100000 N, M≤100000 N,M≤100000。

可以用链表，同时需要开一个迭代器数组 t t t，记录学生 i i i的位置 t [ i ] t[i] t[i]，以便后面的插入和删除。删除的时候，由于有可能要求删已经删过的学生，所以每次删掉后要将迭代器赋值为一个特殊值，可以赋值为链表的尾部迭代器，以供后面判断使用。代码如下：

#include 
#include 
using namespace std;
using lit = list::iterator;

const int N = 1e5 + 10;
int n, m;
list a;
lit it[N];

int main() {
  a.push_front(1);
  it[1] = a.begin();

  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    int k, p;
    scanf("%d%d", &k, &p);
    if (!p) it[i] = a.insert(it[k], i);
    else {
      auto ne = next(it[k]);
      it[i] = a.insert(ne, i);
    }
  }

  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &x);
    if (it[x] != a.end()) {
      a.erase(it[x]);
      // 删了就标记一下
      it[x] = a.end();
    }
  }

  for (auto x: a) printf("%d ", x);
}

时间复杂度 O ( N + M ) O(N+M) O(N+M)，空间 O ( N ) O(N) O(N)。