志愿者选拔（单调队列）

志愿者选拔

 世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）
作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。

Input

输入数据第一行为一整数T，表示有T组输入数据。 
每组数据第一行为”START”，表示面试开始
接下来的数据中有三种情况：
    输入  含义
1   C NAME RP_VALUE     名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2   G   排在面试队伍最前面的同学面试结束离开考场。
3   Q   主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。
最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过1,000,000

Output

对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。

Sample Input

2
START
C Tiny 1000000000
C Lina 0
Q
G
Q
END
START
Q
C ccQ 200
C cxw 100
Q
G
Q
C wzc 500
Q
END

Sample Output

1000000000
0
-1
200
100
500

Hint
数据较大建议使用scanf,printf 不推荐使用STL

分析：

这道题是一道使用单调队列的例题，其中包含了，维护最大值，插入元素，查询最大值

因为查询最大值，所以维护一个单调递减的队列，每次查询取队首即可

删除最先来人out，因为队列中只存单调性的值，而out值是从0开始一个一个递增的，所以要判断只有删到队首的元素编号时，才把队首元素删掉

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
int rp[maxn],que[maxn];
char name[10],op[10];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int l = 0,n = 0,out = 0,r = -1;
        while(scanf("%s",op),op[0] != 'E'){
            if(op[0] == 'C'){
                ++n;
                scanf("%s%d",name,&rp[n]);
                while(l <= r && rp[que[r]] < rp[n]) r--;
                que[++r] = n;
            }
            if(op[0] == 'G') (++out >= que[l]) ? l++ : l;
            if(op[0] == 'Q') printf("%d\n",out < n ? rp[que[l]] : -1);
        }
    }
    return 0;
}