度度熊学队列

度度熊正在学习双端队列，他对其翻转和合并产生了很大的趣味。

初始时有 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;}