题目描述

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

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

2. 接下来有 m 条命令，每条命令包含多个数字：

   • 第一个数字为 1，表示这是一条插入命令，1 后面还有另外两整数 a,b ，表示把编号为 a 的同学插到编号为 b 的同学前面；
   • 第一个数字为 2，表示这是一条插入命令，2 后面还有另外两整数 a,b ，表示把编号为 a 的同学插到编号为 b 的同学后面；
   • 第一个数字为 3，表示这是一条删除命令，后面还会带 1 个整数 a，表示把编号为 a 的同学移出队列。
   • 第一个数字为 4，表示这是一条查询命令，排在队伍中间的同学需要报告自己的编号（当队列人数为偶数的时候，输出中间 2 个人里靠后面的那个人的编号）
   • 第一个数字为 5，表示这是一条查询命令，后面还有另外一个整数 a, 查询队列中第 a 个人是谁。

输入格式

第一行两个整数 $N$, $M$，表示了有 $N$ 个同学，并且接下来有 $M$ 条命令。

第 $2\sim M$ 行，第行有若干数字，数字含义请见题目描述。

数据范围

$1 \le N\leq 10^5$。

$1 \le M\leq 2 \times 10^5$，并且查询命令总数小于等于 $200$。

数据保证是正确的，插入操作中 a 一定不在队列中，b 一定是已经在队列中；删除操作中的 a 一定是在队列中；但是一个人被删除后可以重新进入队列，有一些人可能从来没有进入过队列；查询队列中第 a 个人的时候，队列确保有大于等于 a 个人。

输出格式

若干行，对应的查询结果(如果查询人数是队列为空，输出 0）。

样例

5 10
1 2 1
1 5 2
2 4 1
2 3 4
3 1
2 1 2
3 4
2 4 2
5 4
4

1
4

【样例解释】

最开始，队列里只有 1

前 9 条命令执行完，依次队列情况为：

第 1 条命令，在 1 前面插 2，结果为：2-1

第 2 条命令，在 2 前面插 5，结果为：5-2-1

第 3 条命令，在 1 后面插 4，结果为：5-2-1-4

第 4 条命令，在 4 后面插 3，结果为：5-2-1-4-3

第 5 条命令，删除 1，结果为：5-2-4-3

第 6 条命令，在 2 后面插 1，结果为：5-2-1-4-3

第 7 条命令，删除 4，结果为：5-2-1-3

第 8 条命令，在 2 后面插 4，结果为：5-2-4-1-3

第 9 条命令，查询队列中第 4 个人的编号，输出：1

第 10 条命令，查询队伍中间位置的编号，输出： 4

完成程序

#include<bits/stdc++.h>
using namespace std;
struct Student{
	int p,L,R;
}x[100001];
int n,m,head;
// 在 b 之前插入 a
void pre_insert(int a,int b){
	if(x[b].L==0){ // b 已经是头 
		head = __填空(1)__;
		x[a].R = b;
		x[a].L = 0;
		x[b].L = a;
	}else{
		x[a].L = __填空(2)__;  // a 的左边是 b 之前左边的人
		x[a].R = b;
		__填空(3)__ = a; // b 之前左边的人的右边是 a
		x[b].L = a;
	}
}

// 在 b 之后插入 a
void post_insert(int a,int b){
	if(x[b].R==0){// b 已经是最后一个 
		x[a].L = b;
		x[a].R = 0;
		x[b].R = a;
	}else{
		x[a].R = __填空(4)__; // a 的右边是之前 b 的右边那个人
		x[a].L = b;
		__填空(5)__ = a; // 之前 b 的右边那个人的左边是 a 
		x[b].R = a;
	}
	//printf("post_insert\n");
}

// 删除 a
void Delete(int a){ // delete 是保留字，是c++的命令，所以不能用 delete 命名函数
	if(head==a){
		head = x[head].R;
		x[head].L = 0;
	}else{
		x[x[a].L].R = __填空(6)__; // a 左边的人的右边 是 a 右边的人 
		__填空(7)__ = x[a].L; // a 右边的人的左边是 a 左边的人
	}
}
int Check(){
	int p_quick,p_slow; // 快指针，慢指针
	p_quick = p_slow = head;
	
	while(x[p_quick].R){
		p_slow = x[p_slow].R; // 慢指针一次跳一格
		p_quick = __填空(8)__; //快指针一次跳两格
	}
	return p_slow;
}
int Query(int a){
	int h=head;
	
	for(int i=1;__填空(9)__;i++)
		h = __填空(10)__;
	
	return h;
}
int main()
{
	scanf("%d%d",&n,&m);
	head = 1;
	
	int op,a,b;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&op);
		if(op==1){
			//在 b 前面插入 a
			scanf("%d%d",&a,&b);
			pre_insert(a,b);
		}else if(op==2){
			//在 b 后面插入 a
			scanf("%d%d",&a,&b);
         
			post_insert(a,b);
		}else if(op==3){
			// 删除 a
			scanf("%d",&a);
			Delete(a);
		}else if(op==4){
			// 查询队列中中间那人的编号
			printf("%d\n",Check());
		}else{
			// 查询队列中第 a 个人的编号
			scanf("%d",&a);
			printf("%d\n",Query(a))
		}
	}

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}

填空(9):{{ input(9) }}

填空(10):{{ input(10) }}