共计 3877 个字符，预计需要花费 10 分钟才能阅读完成。
度度熊学队列
度度熊正在学习双端队列，他对其翻转和合并产生了很大的趣味。
初始时有 N 个空的双端队列（编号为 1 到 N），你要反对度度熊的 Q 次操作。
①1 u w val 在编号为 u 的队列里退出一个权值为 val 的元素。（w=0 示意加在最后面，w=1 示意加在最初面）。
②2 u w 询问编号为 u 的队列里的某个元素并删除它。（w=0 示意询问并操作最后面的元素，w=1 示意最初面）
③3 u v w 把编号为 v 的队列“接在”编号为 u 的队列的最初面。w=0 示意程序接（队列 v 的结尾和队列 u 的结尾连在一起，队列 v 的结尾作为新队列的结尾）, w=1 示意逆序接（先将队列 v 翻转，再程序接在队列 u 前面）。且该操作实现后，队列 v 被清空。
Input
有多组数据。
对于每一组数据，第一行读入两个数 N 和 Q。
接下来有 Q 行，每行 3~4 个数，意义如上。
N≤150000,Q≤400000
1≤u,v≤N,0≤w≤1,1≤val≤100000
所有数据里 Q 的和不超过 500000
Output
对于每组数据的每一个操作②，输入一行示意答案。
留神，如果操作②的队列是空的，就输入−1 且不执行删除操作。
Sample Input
2 10
1 1 1 23
1 1 0 233
2 1 1
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1
Sample Output
23
-1
2333
233
23333
提醒
因为读入过大，C/C++ 选手倡议应用读入优化。
一个简略的例子：
void read(int &x){char ch = getchar();x = 0;
for (; ch < '0' || ch > '9'; ch = getchar());
for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack>
#include<deque>
using namespace std;
deque<int >que[150010];
//#include<bits/stdc++.h>// 万能头文件
//deque<int >que[150010];// 定义双端队列
int main(){
int n = 0, q = 0;
while(scanf("%d %d",&n,&q)!= EOF){for(int i = 0; i <= n; i++){que[i].clear();}
int a = 0,u = 0,v = 0,w = 0,val = 0;
for(int i = 0; i <q; i++){// 进行 q 此操作
scanf("%d",&a);
if(a == 1){scanf("%d %d %d",&u,&w,&val);
if(w == 1){que[u].push_back(val);
}else{que[u].push_front(val);
}
}else if(a == 2){scanf("%d %d",&u,&w);
if(!que[u].empty()){if(w == 1){// int len = (int)que[u].size();
printf("%d\n",que[u].back());
// printf("%d\n",que[u][len - 1]);
que[u].pop_back();}else{printf("%d\n",que[u].front());
// printf("%d\n",que[u][0]);
que[u].pop_front();}
}else{printf("-1\n");
}
}else{//a == 3 的状况
scanf("%d %d %d",&u,&v,&w);
if(w == 1 && que[v].size() >= 2){reverse(que[v].begin(),que[v].end());
}
while(!que[v].empty()){// 循环的作用是将队列 v 从前到后全副接在队列 v 前面
que[u].push_back(que[v].front());// 把 v 队头接到 u 队尾
que[v].pop_front();// 从头开始一个一个删除 v 队头}
}
}
}
return 0;
}
看病要排队
看病要排队这个是地球人都晓得的常识。
不过通过仔细的 0068 的察看，他发现了医院里排队还是有考究的。0068 所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能依据简略的先来先服务的准则。所以医院对每种病情规定了 10 种不同的优先级。级别为 10 的优先权最高，级别为 1 的优先权最低。医生在看病时，则会在他的队伍外面抉择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则抉择最早来排队的病人。
当初就请你帮忙医院模仿这个看病过程。
Input
输出数据蕴含多组测试，请解决到文件完结。
每组数据第一行有一个正整数 N(0<N<2000)示意产生事件的数目。
接下来有 N 行别离示意产生的事件。
一共有两种事件：
1:”IN A B”, 示意有一个领有优先级 B 的病人要求医生 A 诊治。(0<A<=3,0<B<=10)
2:”OUT A”, 示意医生 A 进行了一次诊治，诊治结束后，病人入院。(0<A<=3)
Output
对于每个 ”OUT A” 事件，请在一行外面输入被诊治人的编号 ID。如果该事件时无病人须要诊治，则输入 ”EMPTY”。
诊治人的编号 ID 的定义为：在一组测试中，”IN A B” 事件产生第 K 次时，进来的病人 ID 即为 K。从 1 开始编号。
Sample Input
7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1
Sample Output
2
EMPTY
3
1
1
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack>
#include<deque>
using namespace std;
//#include<bits/stdc++.h>// 万能头文件
// 优先队列 priority_queue<node >q[]
/*
struct node{
int x,y,val;
friend bool operator <(node a,node b){// 重载 < 运算符（就是它判断小于的条件）return a.val>b.val;// 而这个判断的条件就是 a.val > b.val，该条件满足时，< 重载胜利，节点 a 自身 < 节点 b 自身
}// 故构造体在优先队列 q 的排序中 b 先入队，a 再入队，a < b，所以 q 中的元素就变成按 val 从小到大排序了
}
运算符重载的示例剖析优先队列是从大到小排序的，咱们要想变成从小到大排序，需扭转一下它判断小于的条件(故重载 < 运算符)
如下面这个例子，*/
struct node{// 病人的信息封装在构造体里
int value,id;// 病人的优先级，id
bool operator < (const node &b)const{// 运算符重载固定格局(此处重载 <),const node &b 是用援用传递，比按值传递 node b 效率更高，成果是一样的
if(value == b.value){
return id > b.id;// 定义一种规定，value 相等就依据 id 判断条件进行重载 <，id > b.id 成立返回 1，则重载 < 胜利；// 即 id 的前主体反而要 < b.id 的主体 b 自身，故在优先队列中 id 小的新传入 b 排在 id 大的原主体 的前边(插队到入队程序的后面)
// b 在优先队列 q[]中从大到小入队，先入的 b 其 id 就小，则优先队列 q[]依照 id 则是由小到大排列
}else{
return value < b.value;// 定义一种规定，依据 value 排列，value 小的其主体也小；// 因为此时 value < b.value, 故 前主体 < 传入的新主体 b, 在优先队列 q[]里 新传入的 b 自身 就插队到了队后面(插队到入队程序的后面)
// value 值大的 b 先入队，value 值小的 b 后入队，则优先队列 q[]依照 value 值从大到小排列}
}
};
int main(){
int t = 0;
while(scanf("%d",&t)!= EOF){
node p;
priority_queue<node >q[4];// 定义一个优先队列，容量为 10，从 0 开始到 9，为医生数量
int time;
time = 1;
string s;
while(t--){// 共 t 次操作(含 IN 和 OUT)
cin >> s;
if(s == "IN"){
int a;
cin >> a >> p.value;// 此处别离输出进入的医生 A 和的来的病人优先级 B.value
p.id = time;// 给来的病人编号
time ++;// 编号自增
q[a - 1].push(p);// 将该组进来的病人 B 封装进医生 (a - 1) 的救治名单中，进队，a - 1 是从 0 开始，构造体变量增加到优先队列
}else{// 此时为 out, 输出的医生 A 要医治其优先级最高的病人，而后让其入院
int a;
cin >> a;
if(q[a - 1].empty()){// 如果给医生未接管到病人
cout << "EMPTY" << endl;
}else{// 优先队列.top()示意返回具备最高优先级的元素值, 但不删除，而.pop 示意删除最高优先级的元素
cout << q[a - 1].top().id << endl;// 让该医生优先级最高的病人医治入院，此处题目要求输入其 ID
q[a - 1].pop();// 删除医生 a - 1 的最高优先级的元素(病人)
}
}
}
}
return 0;
}
