01删除标记思想：队列安排

队列安排

题目描述

一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$，他采取如下的方法：

1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；

2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 $N$，表示了有 $N$ 个同学。

第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。

第 $N+1$ 行为一个整数 $M$，表示去掉的同学数目。

接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

样例 #1

样例输入 #1

4
1 0
2 1
1 0
2
3
3

样例输出 #1

2 4 1

提示

【样例解释】

将同学 $2$ 插入至同学 $1$ 左边，此时队列为：

2 1

将同学 $3$ 插入至同学 $2$ 右边，此时队列为：

2 3 1

将同学 $4$ 插入至同学 $1$ 左边，此时队列为：

2 3 4 1

将同学 $3$ 从队列中移出，此时队列为：

2 4 1

同学 $3$ 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 $20\%$ 的数据，$1\leq N\leq 10$。

对于 $40\%$ 的数据，$1\leq N\leq 1000$。

对于 $100\%$ 的数据，$1<M\leq N\leq 10^5$。

Vector做法：在删除（O（n）不够方便）部分运用桶的思想，删除时“标记删除”

注：以下的queue仅仅为动态数组的名字，并不是队列，和队列没半毛钱关系

添加部分代码

int n,k,p,end,x,m,k0=0,k1=0,flag=0;
vector<int>::iterator iter;
cin>>n;
vector<int> queue(1,1);
int del[100005]    ={0};

for (int i=2;i<=n;i++)
{
    cin>>k>>p;
    for(iter=queue.begin();iter!=queue.end();iter++)
    {

        if(*iter==k)break;//iter为迭代器，用于遍历queue，寻找k号同学
        k0++;//这个循环相当于find函数
     } 
    if(p==0)
    {
        queue.insert(queue.begin()+k0,i);
        k0=0;
    }
    else if(p==1)
    {
        queue.insert(queue.begin()+k0+1,i);
        k0=0;
    }

}

重头戏：删除部分代码，看网友大佬如何用桶思想实现标记删除（在桶中标记所有现有的元素，然后用桶标记要删除的元素，实则在queue中并没有将该元素删除，而是在输出时候检测桶中这个元素是否已经被删除了，考虑是否输出，时间复杂度骤降，但只适用于每个元素只出现一次的情况，好处是与此同时可以实现删除时候的去重）

cin>>m;

for (int i=1;i<=n;i++)
{
    del[i]=1;//由上一段代码可知，del是一个全为0的桶，此处赋值所有已存在在queue中的内容
}

for (int i=0;i<m;i++)
{
    cin>>x;
    del[x]=0;//用标记法“删除”元素x
}
for (iter=queue.begin();iter!=queue.end();iter++)
{
    if(del[*iter]==1)//标记删除的元素不输出
    {
        cout<<*iter<<" ";
    }
}
cout<<endl;
return 0;

需要的头文件：

#include<iostream>
#include<vector> 

注意：本做法在www.luogu.com中仅开启吸氧O2才能通过，因此没有这么完美

List做法：在查找方面用索引的做法，记录每号同学的位置

索引查找仅限于用于链表，因为只有链表插入时是不改变其他同学的地址信息的，也就是说pos[?]的位置不用再一一修订。

以下片段为插入部分

const int maxN = 1e5 + 10;
Iter pos[maxN];
list<int> queList;
bool erased[maxN];
int N;
queList.push_front(1);
pos[1] = queList.begin();

  for (int i = 2; i <= N; i++)
  {
      int k, p;
      scanf("%d%d", &k, &p);
      if (p == 0)
      {
          pos[i] = queList.insert(pos[k], i); //left
      }
      else
      {
          auto nextIter = next(pos[k]);
          pos[i] = queList.insert(nextIter, i); //right
      }
  }

pos[n]为索引数组，其内容为n的位置

在删除方面，直接使用内置函数即可，因为erase在list之中的复杂度较低，直接用没什么问题。

int M;
  scanf("%d", &M);
  for (int x, i = 1; i <= M; i++)
  {
      scanf("%d", &x);
      if (!erased[x])
      {
          queList.erase(pos[x]);
      }
      erased[x] = true;
  }
}